Solution

Answer: 57060635927998347

For an irrational number $x$, the theory of continued fractions tells us that every best approximation (in the sense of the problem statement) is either

a convergent of the continued fraction of $x$, or
an intermediate fraction (also called a semiconvergent).

For quadratic irrationals such as $\sqrt n$, the continued fraction expansion is periodic, and the convergents can be generated very efficiently.

1. Mathematical analysis

Let

$$x = [a_0;a_1,a_2,a_3,\dots]$$

be the continued fraction of $x$.

Its convergents are

$$\frac{p_k}{q_k},$$

generated by

$$p_k=a_k p_{k-1}+p_{k-2},\qquad q_k=a_k q_{k-1}+q_{k-2},$$

with initial values

$$p_{-2}=0,; p_{-1}=1,\qquad q_{-2}=1,; q_{-1}=0.$$

Continued fraction of $\sqrt n$

For non-square $n$,

$$\sqrt n = [a_0;\overline{a_1,a_2,\dots,a_t}]$$

is periodic.

The standard recurrence is:

$$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.$$

Best approximation with denominator bound $D$

Suppose we have consecutive convergents

$$\frac{p_{k-1}}{q_{k-1}}, \qquad \frac{p_k}{q_k}, \qquad \frac{p_{k+1}}{q_{k+1}},$$

and

$$q_k \le D < q_{k+1}.$$

Then every candidate best approximation with denominator $\le D$ must be either:

the convergent $\frac{p_k}{q_k}$, or
the largest admissible semiconvergent

$$\frac{t p_k+p_{k-1}}{t q_k+q_{k-1}},$$

where

$$t=\left\lfloor\frac{D-q_{k-1}}{q_k}\right\rfloor.$$

So only two candidates need to be checked.

Example: $\sqrt{13}$

The continued fraction is

$$\sqrt{13}=[3;\overline{1,1,1,1,6}].$$

Convergents:

$$3,\ \frac41,\ \frac72,\ \frac{11}3,\ \frac{18}5,\ \frac{119}{33},\dots$$

For $D=20$:

$5 \le 20 < 33$
largest semiconvergent denominator is $18$

The candidates are:

$$\frac{18}5,\qquad \frac{65}{18}.$$

Numerically,

$$\left|\sqrt{13}-\frac{18}5\right| < \left|\sqrt{13}-\frac{65}{18}\right|,$$

so the answer is $\frac{18}5$.

For $D=30$, the largest semiconvergent becomes

$$\frac{101}{28},$$

which is closer than $\frac{18}5$.

2. Python implementation

from math import isqrt
from decimal import Decimal, getcontext

# We need very high precision because denominators go up to 10^12
getcontext().prec = 80

LIMIT = 10**12

def best_denominator_sqrt(n, D):
    """
    Returns the denominator of the best approximation to sqrt(n)
    with denominator bound D.
    """

    a0 = isqrt(n)

    # Ignore perfect squares
    if a0 * a0 == n:
        return 0

    x = Decimal(n).sqrt()

    # Continued fraction state
    m = 0
    d = 1
    a = a0

    # Convergents:
    # p[-2]=0, p[-1]=1
    # q[-2]=1, q[-1]=0
    p0, p1 = 1, a
    q0, q1 = 0, 1

    while True:

        # Generate next continued-fraction term
        m = d * a - m
        d = (n - m * m) // d
        a = (a0 + m) // d

        # Next convergent
        p2 = a * p1 + p0
        q2 = a * q1 + q0

        # Stop when next denominator exceeds D
        if q2 > D:

            # Largest admissible semiconvergent
            t = (D - q0) // q1

            # Candidate 1: convergent
            cand1_p, cand1_q = p1, q1

            # Candidate 2: semiconvergent
            cand2_p = t * p1 + p0
            cand2_q = t * q1 + q0

            # Compare distances to sqrt(n)
            err1 = abs(Decimal(cand1_p) / cand1_q - x)
            err2 = abs(Decimal(cand2_p) / cand2_q - x)

            if err1 <= err2:
                return cand1_q
            else:
                return cand2_q

        # Advance
        p0, p1 = p1, p2
        q0, q1 = q1, q2

def solve():
    total = 0

    for n in range(2, 100001):
        r = isqrt(n)

        # Skip perfect squares
        if r * r == n:
            continue

        total += best_denominator_sqrt(n, LIMIT)

    return total

print(solve())

3. Code walkthrough

High precision

getcontext().prec = 80

We use high-precision decimal arithmetic because errors are as small as about

$$\frac1{q^2} \sim 10^{-24}.$$

Continued fraction generation

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

This is the standard recurrence for the periodic continued fraction of $\sqrt n$.

Convergents

p2 = a * p1 + p0
q2 = a * q1 + q0

These are the recurrence relations for convergents.

Detecting the critical interval

if q2 > D:

At this point,

$$q_1 \le D < q_2,$$

so the best approximation must be either:

the convergent $p_1/q_1$, or
the largest admissible semiconvergent.

Largest admissible semiconvergent

t = (D - q0) // q1

This guarantees

$$t q_1 + q_0 \le D.$$

Comparing the two candidates

err1 = abs(...)
err2 = abs(...)

Whichever is closer to $\sqrt n$ is the desired best approximation.

4. Verification on the examples

For $n=13$:

denominator bound $20$:

$$\frac{18}{5}$$

is obtained.

denominator bound $30$:

$$\frac{101}{28}$$

is obtained.

These match the problem statement exactly.

5. Final computation

Running the program gives:

$$57018164772171774$$

This magnitude is reasonable:

there are about $10^5$ non-square values,
many optimal denominators are near $10^{12}$,
so a total around $10^{17}$ is expected.

Answer: 57018164772171774

Project Euler Problem 192