Project Euler

Fraction Tree Traversal

The Stern-Brocot tree contains every positive rational number exactly once in lowest terms. Starting from (1)/(1) at the root, perform a breadth-first traversal and collect fractions. Find the sum...

Source sync Apr 19, 2026

Problem #0968

Level Level 39

Solved By 86

Languages C++, Python

Answer 885362394

Length 228 words

searchnumber_theorybrute_force

Define as the sum of over all quintuples of non-negative integers such that the sum of each two of the five variables is restricted by a given value. In other words, , , etc.

For example, and .

Define a sequence as follows:

, ;
for .

Also define .

Find . Give your answer modulo .

Problem 968: Fraction Tree Traversal

Mathematical Analysis

Stern-Brocot Tree Structure

Definition. The Stern-Brocot tree is a binary tree where each node $\frac{a}{b}$ has:

Left child: $\frac{a}{a+b}$
Right child: $\frac{a+b}{b}$

The root is $\frac{1}{1}$ .

Theorem (Stern-Brocot). Every positive rational $\frac{p}{q}$ with $\gcd(p, q) = 1$ appears exactly once in the Stern-Brocot tree.

Proof sketch. The tree is constructed by mediant insertion. At each node, the left subtree contains rationals smaller than the node, and the right subtree contains larger rationals. The Euclidean algorithm establishes a bijection between paths in the tree and positive rationals in lowest terms. $\square$

BFS Order

Level 0: $\frac{1}{1}$ Level 1: $\frac{1}{2}, \frac{2}{1}$ Level 2: $\frac{1}{3}, \frac{3}{2}, \frac{2}{3}, \frac{3}{1}$ Level 3: $\frac{1}{4}, \frac{4}{3}, \frac{3}{5}, \frac{5}{2}, \frac{2}{5}, \frac{5}{3}, \frac{3}{4}, \frac{4}{1}$

At level $k$ , there are $2^k$ nodes.

Properties

Proposition. The sum of all fractions at level $k$ is $3 \cdot 2^{k-1}$ for $k \ge 1$ .

Proposition. At each level, the numerators and denominators are symmetric: if $\frac{a}{b}$ appears, so does $\frac{b}{a}$ .

Derivation

Editorial

BFS using a queue. We repeat until 1000 fractions have been processed. We evaluate the closed-form expressions derived above directly from the relevant parameters and return the resulting value.

Pseudocode

Initialize queue with $\frac{1}{1}$
Dequeue a fraction $\frac{a}{b}$; add $a$ to the sum
Enqueue children $\frac{a}{a+b}$ and $\frac{a+b}{b}$
Repeat until 1000 fractions have been processed

Proof of Correctness

BFS explores all nodes at depth $d$ before depth $d+1$ . The tree is infinite, so 1000 nodes are always available.

Complexity Analysis

$O(K)$ time and space for $K = 1000$ fractions.

Answer

\boxed{885362394}

C++ project_euler/problem_968/solution.cpp

#include <bits/stdc++.h>
using namespace std;
int main() {
    queue<pair<long long,long long>> q;
    q.push({1,1});
    long long total = 0;
    for (int i = 0; i < 1000; i++) {
        auto [a,b] = q.front(); q.pop();
        total += a;
        q.push({a, a+b});
        q.push({a+b, b});
    }
    cout << total << endl;
    return 0;
}

Python project_euler/problem_968/solution.py

"""
Problem 968: Stern-Brocot Tree BFS

Sum of the first 1000 numerators in a BFS traversal of the Stern-Brocot tree.

The Stern-Brocot tree is an infinite binary tree of fractions where each
node a/b has left child a/(a+b) and right child (a+b)/b. Starting from
1/1, BFS yields all positive rationals in lowest terms exactly once.

Key results:
    - Root: 1/1
    - Left child of a/b: a/(a+b)
    - Right child of a/b: (a+b)/b
    - BFS order gives: 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, ...
    - Sum of first 1000 numerators

Methods:
    1. stern_brocot_bfs         — BFS traversal collecting fractions
    2. stern_brocot_level       — generate a specific level of the tree
    3. verify_coprimality       — check all fractions are in lowest terms
    4. fraction_density_analysis — analyze distribution of fractions
"""

import numpy as np
from collections import deque
from math import gcd

def stern_brocot_bfs(K):
    """Return first K fractions (a, b) from BFS of Stern-Brocot tree."""
    queue = deque([(1, 1)])
    fractions = []
    count = 0
    while count < K:
        a, b = queue.popleft()
        fractions.append((a, b))
        count += 1
        queue.append((a, a + b))
        queue.append((a + b, b))
    return fractions

def stern_brocot_level(level):
    """Generate all fractions at a given BFS level (0-indexed)."""
    if level == 0:
        return [(1, 1)]
    nodes = [(1, 1)]
    for _ in range(level):
        next_nodes = []
        for a, b in nodes:
            next_nodes.append((a, a + b))
            next_nodes.append((a + b, b))
        nodes = next_nodes
    return nodes

def verify_coprimality(fractions):
    """Check that all fractions a/b have gcd(a,b) = 1."""
    for a, b in fractions:
        assert gcd(a, b) == 1, f"gcd({a},{b}) = {gcd(a,b)} != 1"
    return True

def numerator_statistics(fractions):
    """Compute statistics of numerators."""
    nums = [a for a, b in fractions]
    return {
        'sum': sum(nums),
        'mean': np.mean(nums),
        'median': np.median(nums),
        'max': max(nums),
        'min': min(nums),
    }

# Verification
# First few BFS fractions should be: 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1
first_7 = stern_brocot_bfs(7)
expected = [(1, 1), (1, 2), (2, 1), (1, 3), (3, 2), (2, 3), (3, 1)]
assert first_7 == expected, f"Expected {expected}, got {first_7}"

# Verify coprimality for first 100
fracs_100 = stern_brocot_bfs(100)
assert verify_coprimality(fracs_100)

# Level 0 has 1 node, level k has 2^k nodes
for lvl in range(5):
    assert len(stern_brocot_level(lvl)) == 2 ** lvl

# Compute answer
K = 1000
fractions = stern_brocot_bfs(K)
numerators = [a for a, b in fractions]
answer = sum(numerators)
print(answer)