Project Euler Problem 57 Solution

Project Euler Problem 57 Statement

It is possible to show that the square root of two can be expressed as an infinite continued fraction.

$\sqrt 2 =1+ \frac 1 {2+ \frac 1 {2 +\frac 1 {2+ \dots}}}$

By expanding this for the first four iterations, we get:

$1 + \frac 1 2 = \frac 32 = 1.5$
$1 + \frac 1 {2 + \frac 1 2} = \frac 7 5 = 1.4$
$1 + \frac 1 {2 + \frac 1 {2+\frac 1 2}} = \frac {17}{12} = 1.41666 \dots$
$1 + \frac 1 {2 + \frac 1 {2+\frac 1 {2+\frac 1 2}}} = \frac {41}{29} = 1.41379 \dots$

The next three expansions are $\frac {99}{70}$, $\frac {239}{169}$, and $\frac {577}{408}$, but the eighth expansion, $\frac {1393}{985}$, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than the denominator?

Python Source Code

import math
n, d, N = 3, 2, int(input())

for i in range(2, N+1):
    n, d = n + d*2, n + d
    if int(math.log10(n)) > int(math.log10(d)): 
        print(i)

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 57

HackerRank Project Euler 57: In the first $N$, $8≤ N ≤ 10^4$ expansions, print the iteration numbers where the fractions contain a numerator with more digits than denominator.

Solution

Project Euler Problem 57 and the HackerRank version focuses on the continued fraction expansions of the square root of 2, denoted $\sqrt{2}.$ We know that $$\sqrt{2} = 1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \dots}}}.$$

When you convert these successive continued fractions into rational approximations, you get a sequence of fractions $\tfrac{n}{d}$. The problem asks: among the first $ N $ of these fractions, how many have a numerator with more digits than the denominator?

A known result is that these convergents $\tfrac{n}{d}$ satisfy the recurrences:

$$n_{k+1} = n_k + 2\,d_k \quad,\quad d_{k+1} = n_k + d_k,$$

starting from $\tfrac{3}{2}$. This corresponds to the second convergent if you count $\tfrac{1}{1}$ as the first. We check whether the numerator $n$ has more digits than the denominator $d$. If $\lfloor \log_{10}(n) \rfloor$ is greater than $\lfloor \log_{10}(d) \rfloor,$ then $n$ has strictly more digits than $d$.

In Summary

Our Python code above reads an integer input $N$, uses the recurrences to update $n$ and $d$, and prints the iteration index, i, whenever the numerator's digit count exceeds the denominator's digit count. The original Project Euler problem only wants the number of time this condition occurs.

Last Word

We could have also compared string lengths of n and d instead, but using logs is faster by quite a bit.

Another way I've seen the recurrence relation for each expansion explained: $$ \frac{n_{\text{new}}}{d_{\text{new}}} = 1 + \frac{1}{2 + \frac{1}{\frac{n}{d}}} = \frac{n + 2d}{n + d} $$