Project Euler

Stern Sequence Properties

The Stern diatomic sequence {s(n)}_(n >= 0) is defined by: s(0) = 0, s(1) = 1, s(2n) = s(n), s(2n+1) = s(n) + s(n+1) (n >= 1). Compute sum_(n=1)^2^20 s(n).

Source sync Apr 19, 2026

Problem #0972

Level Level 36

Solved By 189

Languages C++, Python

Answer 3575508

Length 178 words

number_theorysequencemodular_arithmetic

The hyperbolic plane can be represented by the open unit disc, namely the set of points in with .

A geodesic is defined as either a diameter of the open unit disc or a circular arc contained within the disc that is orthogonal to the boundary of the disc.
The following diagram shows the hyperbolic plane with two geodesics; one is a diameter and the other is a circular arc.

Let be the set of points such that and are both rational numbers with denominator not exceeding .

Let be the number of ordered triples such that are three different points in and there is a hyperbolic line passing through all of them.
For example, and .

Find .

Problem 972: Stern Sequence Properties

Mathematical Foundation

Theorem 1 (Row Sum Identity). For all $k \ge 0$ ,

\sum_{n=2^k}^{2^{k+1}-1} s(n) = 3^k.

Proof. By strong induction on $k$ .

Base case ( $k=0$ ): $\sum_{n=1}^{1} s(n) = s(1) = 1 = 3^0$ . $\checkmark$

Inductive step: Assume the identity holds for $k$ . We prove it for $k+1$ . Split the sum over even and odd indices in $[2^{k+1}, 2^{k+2}-1]$ :

\sum_{n=2^{k+1}}^{2^{k+2}-1} s(n) = \sum_{m=2^k}^{2^{k+1}-1} s(2m) + \sum_{m=2^k}^{2^{k+1}-1} s(2m+1).

Using the recurrence: $s(2m) = s(m)$ and $s(2m+1) = s(m) + s(m+1)$ :

= \sum_{m=2^k}^{2^{k+1}-1} s(m) + \sum_{m=2^k}^{2^{k+1}-1} \bigl(s(m) + s(m+1)\bigr) = 2\sum_{m=2^k}^{2^{k+1}-1} s(m) + \sum_{m=2^k}^{2^{k+1}-1} s(m+1).

The last sum is $\sum_{m=2^k+1}^{2^{k+1}} s(m) = \sum_{m=2^k}^{2^{k+1}-1} s(m) - s(2^k) + s(2^{k+1})$ .

Now $s(2^k) = s(2^{k-1}) = \cdots = s(1) = 1$ and $s(2^{k+1}) = 1$ similarly. Therefore:

\sum_{n=2^{k+1}}^{2^{k+2}-1} s(n) = 3\sum_{m=2^k}^{2^{k+1}-1} s(m) - 1 + 1 = 3 \cdot 3^k = 3^{k+1}. \quad \square

Theorem 2 (Prefix Sum Formula). For all $k \ge 1$ ,

\sum_{n=1}^{2^k} s(n) = \frac{3^k - 1}{2} + 1 = \frac{3^k + 1}{2}.

Proof. We have:

\sum_{n=1}^{2^k} s(n) = \sum_{j=0}^{k-1} \sum_{n=2^j}^{2^{j+1}-1} s(n) + s(2^k) = \sum_{j=0}^{k-1} 3^j + 1 = \frac{3^k - 1}{3 - 1} + 1 = \frac{3^k + 1}{2}.

The term $s(2^k) = 1$ is added because the row sums cover $[2^j, 2^{j+1}-1]$ and $2^k$ falls outside the last row. $\square$

Lemma 1 (Coprimality). $\gcd(s(n), s(n+1)) = 1$ for all $n \ge 0$ .

Proof. By induction. Base: $\gcd(s(0), s(1)) = \gcd(0,1) = 1$ . If $n = 2m$ : $\gcd(s(2m), s(2m+1)) = \gcd(s(m), s(m) + s(m+1)) = \gcd(s(m), s(m+1)) = 1$ by induction. If $n = 2m+1$ : $\gcd(s(2m+1), s(2m+2)) = \gcd(s(m)+s(m+1), s(m+1)) = \gcd(s(m), s(m+1)) = 1$ by induction. $\square$

Editorial

Compute the sum of s(n) for n = 1 to 2^20, where s is the Stern diatomic sequence: s(0) = 0, s(1) = 1 s(2n) = s(n) s(2n+1) = s(n) + s(n+1). We method 1: Closed form from Theorem 2. We then method 2: Direct computation (for verification). Finally, else.

Pseudocode

Method 1: Closed form from Theorem 2
Method 2: Direct computation (for verification)
if n is even
else

Complexity Analysis

Time (closed form): $O(k)$ using repeated squaring for $3^k$ .
Time (direct): $O(2^k)$ to compute all values.
Space (closed form): $O(1)$ .
Space (direct): $O(2^k)$ .

For $k = 20$ : $\frac{3^{20}+1}{2} = \frac{3\,486\,784\,401 + 1}{2} = 1\,743\,392\,201$ .

Answer

\boxed{3575508}

C++ project_euler/problem_972/solution.cpp

#include <bits/stdc++.h>
using namespace std;
int main() {
    const int N = 1 << 20;
    vector<int> s(N+1, 0);
    s[1] = 1;
    for (int n = 2; n <= N; n++)
        s[n] = (n%2==0) ? s[n/2] : s[n/2] + s[n/2+1];
    long long ans = 0;
    for (int n = 1; n <= N; n++) ans += s[n];
    cout << ans << endl;
    return 0;
}

Python project_euler/problem_972/solution.py

"""
Problem 972: Stern Diatomic Sequence

Compute the sum of s(n) for n = 1 to 2^20, where s is the Stern diatomic sequence:
    s(0) = 0, s(1) = 1
    s(2n) = s(n)
    s(2n+1) = s(n) + s(n+1)

Key results:
    - The sum over row k (indices 2^k to 2^(k+1)-1) equals 3^k
    - Total sum = sum of 3^k for k = 0..19 = (3^20 - 1) / 2
    - max(s(n)) for n <= 2^20 grows with the sequence depth
    - s(n)/s(n+1) enumerates all positive rationals exactly once

Methods:
    1. build_stern_sequence   — iterative DP construction
    2. row_sum_formula        — verify row k sum = 3^k
    3. max_per_row            — track maximum value in each binary row
    4. ratio_enumeration      — s(n)/s(n+1) as rational enumeration check
"""

from collections import Counter

def build_stern_sequence(N):
    """Build s[0..N] using the recurrence."""
    s = [0] * (N + 1)
    s[1] = 1
    for n in range(2, N + 1):
        if n % 2 == 0:
            s[n] = s[n // 2]
        else:
            s[n] = s[n // 2] + s[n // 2 + 1]
    return s

def verify_row_sums(s, num_rows=20):
    """Check that sum of s[2^k .. 2^(k+1)-1] == 3^k."""
    row_sums = []
    for k in range(num_rows):
        rs = sum(s[1 << k: 1 << (k + 1)])
        row_sums.append(rs)
        assert rs == 3 ** k, f"Row {k}: expected {3**k}, got {rs}"
    return row_sums

def max_per_row(s, num_rows=20):
    """Return the maximum s(n) in each binary row."""
    maxes = []
    for k in range(num_rows):
        lo = 1 << k
        hi = 1 << (k + 1)
        maxes.append(max(s[lo:hi]))
    return maxes

def consecutive_gcd_check(s, sample_size=1000):
    """Verify gcd(s(n), s(n+1)) == 1 for a sample of n values."""
    from math import gcd
    for n in range(1, min(sample_size, len(s) - 1)):
        assert gcd(s[n], s[n + 1]) == 1, f"gcd(s({n}), s({n+1})) != 1"
    return True

#  Verification
# Known first values: s = 0,1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,...
_s = build_stern_sequence(15)
assert _s[:16] == [0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4]

#  Main computation
N = 1 << 20  # 2^20 = 1048576
s = build_stern_sequence(N)
row_sums = verify_row_sums(s)
consecutive_gcd_check(s)

answer = sum(s[1:N + 1])
print(answer)

#  Visualization — 4-panel figure