Project Euler Problem 64

Solution

Answer: 1322

For a non-square integer $N$, the continued fraction expansion of $\sqrt N$ is periodic. The standard algorithm for generating the continued fraction is:

$$a_0=\lfloor \sqrt N \rfloor$$

and then recursively

$$m_{k+1}=d_k a_k-m_k$$

$$d_{k+1}=\frac{N-m_{k+1}^2}{d_k}$$

$$a_{k+1}=\left\lfloor \frac{a_0+m_{k+1}}{d_{k+1}} \right\rfloor$$

with initial values

$$m_0=0,\qquad d_0=1,\qquad a_0=\lfloor\sqrt N\rfloor.$$

The sequence of $a_k$ eventually repeats. For square roots, a classical theorem states that the period ends precisely when

$$a_k = 2a_0.$$

So for each non-square $N$, we can generate terms until $a_k=2a_0$, and count how many steps occurred. That count is the period length.

We need to count how many $N \le 10000$ have an odd period length.

Mathematical derivation

The continued fraction algorithm comes from repeatedly rationalizing expressions of the form

$$\frac1{\sqrt N - m}.$$

Suppose at some step we have

$$\frac{\sqrt N + m_k}{d_k}.$$

We separate the integer part:

$$a_k = \left\lfloor \frac{a_0+m_k}{d_k}\right\rfloor,$$

and rewrite:

$$\frac{\sqrt N + m_k}{d_k} = a_k + \frac{\sqrt N - m_{k+1}}{d_{k+1}},$$

which yields the recurrence formulas above.

For quadratic irrationals such as $\sqrt N$, the state pair $(m_k,d_k)$ must eventually repeat, hence the continued fraction is periodic.

A useful property specific to square roots is:

$$\text{period ends when } a_k = 2a_0.$$

Therefore, computing the period is straightforward.

Python implementation

import math

def continued_fraction_period(n):
    """
    Return the period length of the continued fraction
    expansion of sqrt(n).
    """
    
    a0 = int(math.isqrt(n))
    
    # Perfect squares have no periodic continued fraction
    if a0 * a0 == n:
        return 0
    
    m = 0
    d = 1
    a = a0
    
    period = 0
    
    while True:
        # Recurrence relations
        m = d * a - m
        d = (n - m * m) // d
        a = (a0 + m) // d
        
        period += 1
        
        # For square roots, the period completes at 2*a0
        if a == 2 * a0:
            break
    
    return period

count = 0

for n in range(2, 10001):
    if continued_fraction_period(n) % 2 == 1:
        count += 1

print(count)

Code walkthrough

Function setup

a0 = int(math.isqrt(n))

Computes the integer part of $\sqrt n$.

Perfect square check

if a0 * a0 == n:
    return 0

Perfect squares have terminating expansions, not periodic irrational ones.

Initial state

m = 0
d = 1
a = a0

These are the standard initial values for the recurrence.

Main recurrence

m = d * a - m
d = (n - m * m) // d
a = (a0 + m) // d

This generates the next continued-fraction term.

Period counting

period += 1

Each iteration adds one term to the repeating block.

Detecting completion

if a == 2 * a0:
    break

For square roots, this marks the end of one full period.

Checking the small example

For $N \le 13$:

Odd periods occur for:
$\sqrt2$ (period 1)
$\sqrt5$ (period 1)
$\sqrt{10}$ (period 1)
$\sqrt{13}$ (period 5)

Exactly $4$, matching the problem statement.

Final verification

The algorithm runs efficiently because each $N$ requires only a short period computation, typically $O(\sqrt N)$ steps or less.

Running the code gives:

$$1322$$

This is the known correct Project Euler result for Problem 64.

Answer: 1322