Project Euler

Continued Fraction Convergents

The continued fraction expansion of sqrt(2) is [1; 2, 2, 2,...]. Let p_n/q_n denote the n -th convergent. Find p_100 + q_100 mod 10^9+7.

Source sync Apr 19, 2026

Problem #0925

Level Level 36

Solved By 179

Languages C++, Python

Answer 400034379

Length 282 words

modular_arithmeticsequencelinear_algebra

Let $B(n)$ be the smallest number larger than $n$ that can be formed by rearranging digits of $n$, or $0$ if no such number exists. For example, $B(245) = 254$ and $B(542) = 0$.

Define $\displaystyle T(N) = \sum _{n=1}^N B(n^2)$. You are given $T(10)=270$ and $T(100)=335316$.

Problem 925: Continued Fraction Convergents

Mathematical Foundation

Theorem 1 (Convergent Recurrence). Let $[a_0; a_1, a_2, \ldots]$ be a simple continued fraction. Define $p_{-1} = 1$ , $p_0 = a_0$ , $q_{-1} = 0$ , $q_0 = 1$ , and for $n \geq 1$ :

p_n = a_n p_{n-1} + p_{n-2}, \qquad q_n = a_n q_{n-1} + q_{n-2}.

Then $p_n / q_n$ is the $n$ -th convergent.

Proof. We prove by induction that

\begin{pmatrix} p_n & p_{n-1} \\ q_n & q_{n-1} \end{pmatrix} = \prod_{i=0}^{n} \begin{pmatrix} a_i & 1 \\ 1 & 0 \end{pmatrix}. \tag{M}

Base case ( $n = 0$ ): The right side is $\begin{pmatrix} a_0 & 1 \\ 1 & 0 \end{pmatrix}$ , matching $(p_0, p_{-1}; q_0, q_{-1}) = (a_0, 1; 1, 0)$ .

Inductive step: Assuming (M) holds for $n-1$ , multiply on the right by $\begin{pmatrix} a_n & 1 \\ 1 & 0 \end{pmatrix}$ :

\begin{pmatrix} p_{n-1} & p_{n-2} \\ q_{n-1} & q_{n-2} \end{pmatrix} \begin{pmatrix} a_n & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} a_n p_{n-1} + p_{n-2} & p_{n-1} \\ a_n q_{n-1} + q_{n-2} & q_{n-1} \end{pmatrix} = \begin{pmatrix} p_n & p_{n-1} \\ q_n & q_{n-1} \end{pmatrix}.

That $p_n/q_n$ equals the $n$ -th convergent follows from the standard theory of continued fractions (the finite truncation $[a_0; a_1, \ldots, a_n]$ evaluates to $p_n/q_n$ ). $\square$

Theorem 2 (Determinant Identity / Pell Connection). For all $n \geq 0$ :

p_n q_{n-1} - p_{n-1} q_n = (-1)^{n+1}.

In particular, for $\sqrt{2}$ : $p_n^2 - 2 q_n^2 = (-1)^{n+1}$ .

Proof. Taking the determinant of both sides of (M):

p_n q_{n-1} - p_{n-1} q_n = \det\begin{pmatrix} p_n & p_{n-1} \\ q_n & q_{n-1} \end{pmatrix} = \prod_{i=0}^{n} \det\begin{pmatrix} a_i & 1 \\ 1 & 0 \end{pmatrix} = \prod_{i=0}^{n}(-1) = (-1)^{n+1}.

For $\sqrt{2}$ , the Pell identity $p_n^2 - 2q_n^2 = (-1)^{n+1}$ follows from the fact that $p_n/q_n \to \sqrt{2}$ and the determinant identity, combined with the recurrence structure. Specifically, one proves by induction that $(p_n, q_n)$ satisfies $x^2 - 2y^2 = (-1)^{n+1}$ . $\square$

Lemma 1 (Specialization to $\sqrt{2}$ ). For $\sqrt{2} = [1; 2, 2, 2, \ldots]$ , we have $a_0 = 1$ and $a_n = 2$ for $n \geq 1$ , giving:

p_n = 2p_{n-1} + p_{n-2}, \quad q_n = 2q_{n-1} + q_{n-2},

with $p_0 = 1, p_1 = 3, q_0 = 1, q_1 = 2$ .

Proof. Direct substitution: $p_1 = a_1 p_0 + p_{-1} = 2 \cdot 1 + 1 = 3$ and $q_1 = a_1 q_0 + q_{-1} = 2 \cdot 1 + 0 = 2$ . For $n \geq 2$ , the recurrence with $a_n = 2$ gives the stated formulas. $\square$

Theorem 3 (Matrix Exponentiation). For $n \geq 1$ :

\begin{pmatrix} p_n \\ p_{n-1} \end{pmatrix} = \begin{pmatrix} 2 & 1 \\ 1 & 0 \end{pmatrix}^{n-1} \begin{pmatrix} 3 \\ 1 \end{pmatrix},

enabling $O(\log n)$ computation via repeated squaring.

Proof. Rewrite $p_n = 2p_{n-1} + p_{n-2}$ as $\begin{pmatrix} p_n \\ p_{n-1} \end{pmatrix} = \begin{pmatrix} 2 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} p_{n-1} \\ p_{n-2} \end{pmatrix}$ . Iterating from the initial vector $(p_1, p_0)^T = (3, 1)^T$ yields the formula. The same applies to $q_n$ with initial vector $(2, 1)^T$ . $\square$

Lemma 2 (Growth Rate). The sequences $p_n$ and $q_n$ grow as $\Theta((1+\sqrt{2})^n)$ . Precisely, $q_n = \frac{(1+\sqrt{2})^{n+1} - (1-\sqrt{2})^{n+1}}{2\sqrt{2}}$ .

Proof. The characteristic equation of $x_n = 2x_{n-1} + x_{n-2}$ is $\lambda^2 - 2\lambda - 1 = 0$ , with roots $\lambda = 1 \pm \sqrt{2}$ . Solving with initial conditions $q_0 = 1, q_1 = 2$ gives the closed form. Since $|1 - \sqrt{2}| < 1$ , the second term vanishes exponentially. $\square$

Editorial

Compute p_n and q_n for the continued fraction expansion of sqrt(2), with recurrence p_n = 2p_{n-1} + p_{n-2}, q_n = 2q_{n-1} + q_{n-2}, starting from p_0=1, p_1=3, q_0=1, q_1=2. Return (p_n + q_n) mod 10^9+7. Key ideas:. We iterative approach: O(n) time.

Pseudocode

    Iterative approach: O(n) time
    p_prev = 1 // p_0
    p_curr = 3 // p_1
    q_prev = 1 // q_0
    q_curr = 2 // q_1

    For i from 2 to target_n:
        p_next = (2 * p_curr + p_prev) mod MOD
        p_prev = p_curr
        p_curr = p_next

        q_next = (2 * q_curr + q_prev) mod MOD
        q_prev = q_curr
        q_curr = q_next

    Return (p_curr + q_curr) mod MOD

Complexity Analysis

Time: $O(n)$ for the iterative approach; $O(\log n)$ via $2 \times 2$ matrix exponentiation.
Space: $O(1)$ for the iterative approach; $O(\log n)$ stack space for recursive matrix exponentiation, or $O(1)$ for iterative matrix exponentiation.

Answer

\boxed{400034379}

C++ project_euler/problem_925/solution.cpp

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 925: Continued Fraction Convergents
 *
 * sqrt(2) = [1; 2, 2, 2, ...]. Find p_100 + q_100 mod 10^9+7.
 *
 * Convergent recurrence: p_n = 2*p_{n-1} + p_{n-2}, same for q.
 * Initial: p_0=1, p_1=3, q_0=1, q_1=2.
 *
 * Key results:
 *   - Pell equation: p_n^2 - 2*q_n^2 = (-1)^{n+1}
 *   - Best approximation: |sqrt(2) - p_n/q_n| < 1/(q_n * q_{n+1})
 *   - Growth: q_n ~ (1+sqrt(2))^n / (2*sqrt(2))
 *   - Matrix form: [p_n; p_{n-1}] = [[2,1],[1,0]]^{n-1} * [3;1]
 *
 * Complexity: O(n) iterative, O(log n) via matrix exponentiation.
 */

int main() {
    long long MOD = 1000000007;
    long long p0 = 1, p1 = 3, q0 = 1, q1 = 2;
    for (int i = 2; i <= 100; i++) {
        long long np = (2 * p1 % MOD + p0) % MOD;
        long long nq = (2 * q1 % MOD + q0) % MOD;
        p0 = p1; p1 = np;
        q0 = q1; q1 = nq;
    }
    cout << (p1 + q1) % MOD << endl;

    // Verify Pell equation for small n (without mod)
    long long pp0 = 1, pp1 = 3, qq0 = 1, qq1 = 2;
    for (int i = 2; i <= 10; i++) {
        long long npp = 2*pp1 + pp0;
        long long nqq = 2*qq1 + qq0;
        pp0 = pp1; pp1 = npp;
        qq0 = qq1; qq1 = nqq;
    }
    // p_10^2 - 2*q_10^2 should be +/- 1
    assert(abs(pp1*pp1 - 2*qq1*qq1) == 1);

    return 0;
}

Python project_euler/problem_925/solution.py

"""
Problem 925: Continued Fraction Convergents

Compute p_n and q_n for the continued fraction expansion of sqrt(2),
with recurrence p_n = 2*p_{n-1} + p_{n-2}, q_n = 2*q_{n-1} + q_{n-2},
starting from p_0=1, p_1=3, q_0=1, q_1=2. Return (p_n + q_n) mod 10^9+7.

Key ideas:
    - sqrt(2) = [1; 2, 2, 2, ...] has all partial quotients = 2 after the first.
    - Convergents p_n/q_n approach sqrt(2) exponentially fast.
    - The recurrence is a linear second-order relation.
    - Ratio p_n/q_n oscillates above and below sqrt(2).

Methods:
    1. Modular arithmetic recurrence for large n
    2. Exact integer convergents for small n
    3. Convergence rate analysis
    4. Ratio of consecutive convergents (approaches 1 + sqrt(2))
"""

import numpy as np

def solve(n=100):
    """Compute (p_n + q_n) mod 10^9+7 via linear recurrence."""
    MOD = 10**9 + 7
    p0, p1 = 1, 3
    q0, q1 = 1, 2
    for i in range(2, n + 1):
        p0, p1 = p1, (2 * p1 + p0) % MOD
        q0, q1 = q1, (2 * q1 + q0) % MOD
    return (p1 + q1) % MOD

def convergents(n):
    """Return lists of exact (p_k, q_k) for k = 0..n."""
    ps = [1, 3]
    qs = [1, 2]
    for i in range(2, n + 1):
        ps.append(2 * ps[-1] + ps[-2])
        qs.append(2 * qs[-1] + qs[-2])
    return ps, qs

def convergence_errors(n):
    """Compute |p_k/q_k - sqrt(2)| for k = 0..n."""
    ps, qs = convergents(n)
    sqrt2 = np.sqrt(2)
    return [abs(ps[i] / qs[i] - sqrt2) for i in range(n + 1)]

def denominator_growth_ratio(n):
    """Compute q_{k+1}/q_k for k = 0..n-1, should approach 1+sqrt(2)."""
    _, qs = convergents(n)
    return [qs[i + 1] / qs[i] for i in range(n)]

# Solve and verify
answer = solve()

# Verify convergents approach sqrt(2) - errors decrease monotonically
ps, qs = convergents(20)
sqrt2 = np.sqrt(2)
errors_v = [abs(ps[i] / qs[i] - sqrt2) for i in range(1, 15)]
for i in range(len(errors_v) - 1):
    assert errors_v[i + 1] < errors_v[i], "Errors should decrease monotonically"

# Verify alternating property: even convergents < sqrt(2), odd > sqrt(2)
for i in range(2, 10):
    # Use integer comparison: p_i^2 vs 2*q_i^2
    if i % 2 == 0:
        assert ps[i]**2 < 2 * qs[i]**2, f"Even convergent {i} should be below sqrt(2)"
    else:
        assert ps[i]**2 > 2 * qs[i]**2, f"Odd convergent {i} should be above sqrt(2)"

# Verify determinant property: p_n*q_{n-1} - p_{n-1}*q_n = (-1)^(n+1)
for i in range(1, 20):
    det = ps[i] * qs[i - 1] - ps[i - 1] * qs[i]
    assert det == (-1)**(i + 1), f"Determinant property failed at {i}"

print(answer)