Detailed mathematical approach

Problem Summary

The continued fraction for \(\sqrt{2}\) is

$\sqrt{2}=1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cdots}}}=[1;2,2,2,\dots].$

If we truncate this infinite expression after finitely many layers, we obtain the convergents \(3/2, 7/5, 17/12, 41/29, \dots\). The problem asks how many of the first 1000 convergents have a numerator with more decimal digits than the denominator.

The key point is that we never need a floating-point approximation of \(\sqrt{2}\). Each convergent can be generated exactly from the previous one using only integer arithmetic.

Mathematical Approach

Let the \(k\)-th convergent be

$x_k=\frac{n_k}{d_k}, \qquad x_1=\frac{3}{2}.$

We want to count the indices \(k \le 1000\) for which \(n_k\) has more decimal digits than \(d_k\).

Turning the continued fraction into a one-step update

If \(x_k\) is one convergent, then adding one more layer of the continued fraction gives

$x_{k+1}=1+\frac{1}{1+x_k}.$

Now substitute \(x_k=n_k/d_k\):

$x_{k+1}=1+\frac{1}{1+n_k/d_k}=1+\frac{d_k}{n_k+d_k}=\frac{n_k+2d_k}{n_k+d_k}.$

Therefore the exact integer update is

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

This is the central object in the solution. The implementations keep only the current pair \((n_k,d_k)\) and repeatedly apply this map.

The equivalent Pell-style recurrence

The one-step map can be rewritten as a second-order recurrence. Eliminating \(d_k\) gives

$n_{k+2}=2n_{k+1}+n_k,$

and eliminating \(n_k\) gives

$d_{k+2}=2d_{k+1}+d_k.$

So the numerators and denominators follow the same linear recurrence as the companion Pell numbers and the Pell numbers. This already explains why the numbers grow quickly but still remain easy to generate: every step uses only additions.

Invariants that explain why the convergents are so good

The recurrence preserves several useful facts.

First,

$n_{k+1}-d_{k+1}=d_k>0,$

so every convergent is bigger than \(1\).

Second, the fractions stay reduced, because

$\gcd(n_k+2d_k,n_k+d_k)=\gcd(d_k,n_k+d_k)=\gcd(n_k,d_k).$

Starting from \(\gcd(3,2)=1\), every later pair is also coprime.

Most importantly, the Pell-type invariant alternates sign:

$n_k^2-2d_k^2=(-1)^{k+1}.$

This follows from the update, since

$\left(n_k+2d_k\right)^2-2\left(n_k+d_k\right)^2=-(n_k^2-2d_k^2).$

Because the initial pair \((3,2)\) gives \(3^2-2\cdot 2^2=1\), the sign flips at every step. As a consequence, the convergents alternate around \(\sqrt{2}\), and the error is

$\left|\frac{n_k}{d_k}-\sqrt{2}\right|=\frac{1}{d_k\left(n_k+d_k\sqrt{2}\right)}.$

That is why these rational approximations become accurate very quickly.

Why the digit comparison is the whole counting problem

A positive integer \(m\) has

$\lfloor \log_{10} m \rfloor + 1$

decimal digits. Therefore the condition in the problem is simply

$\lfloor \log_{10} n_k \rfloor > \lfloor \log_{10} d_k \rfloor.$

Since \(n_k/d_k \to \sqrt{2}\), numerator and denominator usually have almost the same size. A hit occurs exactly when the numerator has crossed a power of ten but the denominator has not yet done so. The code does not need logarithms, though; it can compare decimal lengths directly.

Worked example

Starting from \((n_1,d_1)=(3,2)\), the recurrence gives

$ (3,2)\to(7,5)\to(17,12)\to(41,29)\to(99,70)\to(239,169)\to(577,408)\to(1393,985). $

The first seven listed convergents have matching digit counts in numerator and denominator. The eighth one, \(1393/985\), has 4 digits in the numerator and 3 in the denominator, so it is the first success. This is exactly the checkpoint used by the implementations: among the first 8 expansions, the count is 1.

How the Code Works

Start from the first expansion

The C++, Python, and Java implementations begin with the first convergent \(3/2\). They store the current numerator, the current denominator, and a counter for successful cases.

Apply the exact recurrence 1000 times

Each loop iteration checks whether the current numerator has more decimal digits than the current denominator. After that, it updates the pair by

$ (n,d)\mapsto(n+2d,\;n+d). $

No division is required, and there is no risk of floating-point rounding error because the whole computation stays in exact integer arithmetic.

Use arbitrary-precision integers and a checkpoint

After 1000 expansions the numbers have far more than 64 bits, so the implementations rely on arbitrary-precision integers. That is still inexpensive here because each step performs only a doubling, two additions, and two decimal-length checks. They also verify the known checkpoint that the first 8 expansions produce exactly 1 success, which validates both the recurrence and the counting logic.

Complexity Analysis

For a general limit of \(N\) expansions, the convergents grow like \((1+\sqrt{2})^N\), so the largest numerator and denominator have \(\Theta(N)\) decimal digits. One loop iteration therefore costs \(\Theta(k)\) digit work when the current values have \(k\) digits.

Summing over all iterations gives \(\Theta(N^2)\) time in digit operations. The memory usage is \(\Theta(N)\) digits, because the algorithm stores only the current pair and a few temporary big integers. For the concrete case \(N=1000\), the numbers are only about 383 digits long, so the program is comfortably fast.

Footnotes and References

1. Problem page: Project Euler 57
2. Continued fraction of \(\sqrt{2}\): Wikipedia - Square root of 2
3. Convergents of continued fractions: Wikipedia - Convergent (continued fraction)
4. Pell numbers: Wikipedia - Pell number
5. OEIS Pell sequence: OEIS A000129
6. OEIS companion Pell sequence: OEIS A001333