Solution

Answer: 153

The continued fraction expansion for $\sqrt2$ is

$$\sqrt2 = 1 + \cfrac1{2+\cfrac1{2+\cfrac1{2+\cdots}}}.$$

We are asked:

Among the first 1000 convergents (expansions), how many fractions have a numerator with more digits than the denominator?

Mathematical analysis

The convergents are:

$$\frac32,\ \frac75,\ \frac{17}{12},\ \frac{41}{29},\dots$$

We need a systematic way to generate them.

1. Deriving the recurrence

Let the $n$-th convergent be

$$\frac{p_n}{q_n}.$$

Observe the pattern:

$$\frac32,\ \frac75,\ \frac{17}{12},\ \frac{41}{29}.$$

The continued fraction structure gives:

$$x_{n+1} = 1 + \frac1{1+x_n}.$$

But there is an even cleaner recurrence directly for numerators and denominators.

Starting with

$$\frac{p_n}{q_n},$$

the next expansion is

$$1+\frac1{1+\frac{p_n}{q_n}} = 1+\frac{q_n}{p_n+q_n} = \frac{p_n+2q_n}{p_n+q_n}.$$

Therefore,

$$p_{n+1}=p_n+2q_n,$$

$$q_{n+1}=p_n+q_n.$$

Initial values:

$$p_1=3,\qquad q_1=2.$$

2. Checking the recurrence

From $\frac32$:

$$p_2 = 3 + 2\cdot2 = 7,$$

$$q_2 = 3+2 = 5.$$

So we get $\frac75$.

$$p_3 = 7 + 2\cdot5 = 17,$$

$$q_3 = 7+5 = 12.$$

Correct again.

3. Digit comparison

We must count how many times

$$\text{digits}(p_n) > \text{digits}(q_n).$$

The number of digits of a positive integer $x$ is

$$\lfloor \log_{10}(x)\rfloor + 1,$$

but in Python we can simply compare:

len(str(p)) > len(str(q))

Since there are only 1000 iterations, this is perfectly efficient.

Python implementation

# Project Euler Problem 57

# Initial convergent of sqrt(2)
p = 3  # numerator
q = 2  # denominator

count = 0

# Check the first 1000 expansions
for _ in range(1000):

    # Count cases where numerator has more digits
    if len(str(p)) > len(str(q)):
        count += 1

    # Generate next convergent:
    # p_{n+1} = p_n + 2*q_n
    # q_{n+1} = p_n + q_n
    p, q = p + 2*q, p + q

print(count)

Code walkthrough

p = 3
q = 2

We start with the first expansion:

$$\frac32.$$

count = 0

This will store the number of qualifying fractions.

for _ in range(1000):

We iterate through the first 1000 convergents.

if len(str(p)) > len(str(q)):
    count += 1

Convert numerator and denominator to strings and compare digit lengths.

Example:

$1393$ has 4 digits
$985$ has 3 digits

so this convergent is counted.

p, q = p + 2*q, p + q

This applies the recurrence relation derived earlier.

If current fraction is

$$\frac{p}{q},$$

the next one becomes

$$\frac{p+2q}{p+q}.$$

Verification on small cases

The first few convergents generated are:

$$\frac32,\ \frac75,\ \frac{17}{12},\ \frac{41}{29}, \frac{99}{70},\ \frac{239}{169},\ \frac{577}{408},\ \frac{1393}{985}.$$

The 8th convergent is indeed the first where numerator digits exceed denominator digits:

$1393$: 4 digits
$985$: 3 digits

So the recurrence is correct.

Running the full computation for 1000 expansions gives:

$$153$$

The result is reasonable: such digit overflows happen occasionally but not extremely rarely.

Answer: 153