Project Euler Solution 57: Square root convergents

Problem 57: Square root convergents is a fun one. One needs to simplify nested fractions.

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?

We can use the examples to give us material for a test case. I want to write a generator which generates these fractions. Taking the first four ones must match the examples given. This is the test:

def test_square_root_sequence() -> None:
    elems = list(itertools.islice(square_root_sequence(), 4))
    assert elems == [(3, 2), (7, 5), (17, 12), (41, 29)]

And it is not that hard to implement. One can take a look at the fractions and see how they repeat. Actually one could write this as the following: $$ \sqrt 2 = 1 + \frac{1 + \sqrt 2} \,. $$

You can simplify this expression by doing $-1$ on both sides, multiplying through and you get $(\sqrt 2 - 1)(\sqrt 2 + 1) = 1$. That indeed holds, the left side is $2 - 1 = 1$, so this works out.

If in this sequence we are at the point $\frac nd$, we can get to the next iteration by simplifying $$ 1 + \frac{1}{1 + \frac nd} = 1 + \frac{1}{\frac dd + \frac nd} = 1 + \frac{1}{\frac{n + d}{d}} = 1 + \frac{d}{n + d} = \frac{n + 2 * d}{n + d} $$ and then using $n' := n + 2 d$ and $d' := n + d$. We then need to cancel out the greatest common denominator, where we can take the implementation from Solution 33: Digit cancelling fractions.

Or we write it a bit differently in the code, explicitly the adding of one and the inversion in muliple steps:

def square_root_sequence() -> Iterator[tuple[int, int]]:
    n, d = 3, 2
    while True:
        yield n, d
        # Add 1.
        n += d
        # Invert.
        n, d = d, n
        # Add 1.
        n += d
        # Cancel.
        gcd = greatest_common_denominator(n, d)
        n //= gcd
        d //= gcd

The terms of interest are then easily found by just taking the first 1000 elements of the sequence and taking the ones where the numerator has more digits than the denominator:

def solution() -> int:
    terms_of_interest = list(
        filter(
            lambda term: len(str(term[0])) > len(str(term[1])),
            itertools.islice(square_root_sequence(), 1000),
        )
    )
    return len(terms_of_interest)

This solves the problem in 77 ms.