Problem 957: Diophantine Approximation

Mathematical Analysis

Continued Fraction of $\sqrt{2}$

The continued fraction expansion of $\sqrt{2}$ is purely periodic after the integer part:

This is one of the simplest infinite continued fractions. The partial quotients are all 2 (except the first, which is 1).

Convergent Recurrence

The convergents $p_k/q_k$ satisfy the standard recurrence:

with $a_0 = 1$, $a_k = 2$ for $k \ge 1$, and initial conditions $p_{-1} = 1, p_0 = 1$ (or equivalently $p_{-2} = 0, p_{-1} = 1$).

The first several convergents are:

The Fundamental Identity

Theorem. For all $k \ge 0$:

Proof by induction.

Base cases: $p_0^2 - 2q_0^2 = 1 - 2 = -1 = (-1)^1$. $p_1^2 - 2q_1^2 = 9 - 8 = 1 = (-1)^2$. Both check out.

Inductive step: Assume $p_{k-1}^2 - 2q_{k-1}^2 = (-1)^k$ and $p_{k-2}^2 - 2q_{k-2}^2 = (-1)^{k-1}$. Using $p_k = 2p_{k-1} + p_{k-2}$ and $q_k = 2q_{k-1} + q_{k-2}$:

By a separate identity for convergents: $p_{k-1}p_{k-2} - 2q_{k-1}q_{k-2}$ satisfies $p_k q_{k-1} - p_{k-1} q_k = (-1)^{k+1}$, and after algebraic manipulation:

Connection to Pell’s Equation

The identity $p_k^2 - 2q_k^2 = (-1)^{k+1}$ means that the convergents $(p_k, q_k)$ provide all solutions to the Pell equations $x^2 - 2y^2 = \pm 1$. Specifically:

• Even $k$: $(p_k, q_k)$ solves $x^2 - 2y^2 = -1$ (the negative Pell equation).
• Odd $k$: $(p_k, q_k)$ solves $x^2 - 2y^2 = +1$ (the positive Pell equation).

Computing the Sum

For $k = 0, 1, \ldots, 50$ (51 terms):

• $k$ even ($k = 0, 2, 4, \ldots, 50$): 26 terms, each contributing $(-1)^{k+1} = -1$.
• $k$ odd ($k = 1, 3, 5, \ldots, 49$): 25 terms, each contributing $(-1)^{k+1} = +1$.

Derivation

Editorial

Method 1 (closed form): By the identity, the sum is $\sum_{k=0}^{50} (-1)^{k+1} = -1$.

Method 2 (verification): Compute convergents using the recurrence and verify each $p_k^2 - 2q_k^2 = (-1)^{k+1}$ directly.

Proof of Correctness

Theorem. For the continued fraction $\sqrt{2} = [1; \overline{2}]$ with convergents $p_k/q_k$, the identity $p_k^2 - 2q_k^2 = (-1)^{k+1}$ holds for all $k \ge 0$.

The proof is given above by strong induction on $k$.

Corollary. $\sum_{k=0}^{N} (p_k^2 - 2q_k^2) = \sum_{k=0}^{N} (-1)^{k+1}$, which equals $-1$ if $N$ is even and $0$ if $N$ is odd.

Proof. For even $N$, there are $(N/2 + 1)$ even values of $k$ and $N/2$ odd values. The sum is $-(N/2 + 1) + N/2 = -1$. For odd $N$, there are $(N+1)/2$ terms of each sign, summing to $0$. $\square$

Complexity Analysis

$O(1)$ with the closed-form result. $O(N)$ with explicit computation of convergents (using $O(\log(\phi^N))$-digit arithmetic for the exact convergent values).

Answer

/*
 * Problem 957: Diophantine Approximation
 *
 * Convergents of sqrt(2) = [1; 2, 2, ...] satisfy p_k^2 - 2*q_k^2 = (-1)^{k+1}.
 * Sum for k = 0..50 = -1 (closed form).
 *
 * Verification: compute convergents using arbitrary-precision integers
 * (or just use the closed-form answer).
 *
 * Complexity: O(1) closed form, O(N) with verification.
 */

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

int main() {
    // Closed-form: sum_{k=0}^{50} (-1)^{k+1}
    // 26 even k's contribute -1, 25 odd k's contribute +1
    // Total = -26 + 25 = -1

    // Verification with __int128 (convergents grow as (1+sqrt(2))^k)
    __int128 p_prev = 0, p_curr = 1;
    __int128 q_prev = 1, q_curr = 1;
    long long total = 0;

    // k = 0
    __int128 val = p_curr * p_curr - 2 * q_curr * q_curr;
    total += (long long)val;

    for (int k = 1; k <= 50; k++) {
        __int128 p_next = 2 * p_curr + p_prev;
        __int128 q_next = 2 * q_curr + q_prev;
        p_prev = p_curr; p_curr = p_next;
        q_prev = q_curr; q_curr = q_next;

        val = p_curr * p_curr - 2 * q_curr * q_curr;
        total += (long long)val;
    }

    cout << total << endl;
    return 0;
}

"""
Problem 957: Diophantine Approximation

Convergents p_k/q_k of sqrt(2) = [1; 2, 2, 2, ...] satisfy p_k^2 - 2*q_k^2 = (-1)^{k+1}.
Sum for k=0..50: sum of (-1)^{k+1} = -1 (26 terms of -1, 25 terms of +1).

Verification by direct computation of convergents.
"""

def convergents_sqrt2(N: int) -> list[tuple[int, int]]:
    """Compute convergents p_k/q_k of sqrt(2) for k = 0, 1, ..., N."""
    result = []
    p_prev, p_curr = 0, 1  # p_{-1}, p_0
    q_prev, q_curr = 1, 1  # q_{-1}, q_0
    # a_0 = 1, so p_0 = 1, q_0 = 1
    result.append((p_curr, q_curr))
    for k in range(1, N + 1):
        a_k = 2
        p_next = a_k * p_curr + p_prev
        q_next = a_k * q_curr + q_prev
        p_prev, p_curr = p_curr, p_next
        q_prev, q_curr = q_curr, q_next
        result.append((p_curr, q_curr))
    return result

def solve(N: int = 50) -> int:
    """Compute sum of (p_k^2 - 2*q_k^2) for k = 0 to N."""
    convs = convergents_sqrt2(N)
    return sum(p * p - 2 * q * q for p, q in convs)

# --- Compute answer ---
N = 50
convs = convergents_sqrt2(N)

# Verify identity p_k^2 - 2*q_k^2 = (-1)^{k+1}
for k, (p, q) in enumerate(convs):
    val = p * p - 2 * q * q
    expected = (-1) ** (k + 1)
    assert val == expected, f"k={k}: {val} != {expected}"

answer = sum(p * p - 2 * q * q for p, q in convs)
# Closed form check
assert answer == -1, f"Expected -1, got {answer}"

print(answer)