Problem statement

Problem Statement

This archive keeps the full statement, math, and original media on the page.

Given a pair of coprime odd positive integers, define the function It can be seen that , , and for all strictly between and .

Given two such pairs and , paths of infinitesimal width traverse the unit cube internally through every point such that . Remarkably, it can be shown that the point is always connected to the opposite corner . Furthermore, with the additional condition , it can be shown that there is exactly one path connecting the two points.

Shown above are two examples, as viewed from above the cube. That is, we see the paths projected onto the -plane, with corresponding values indicated with varying colour. In the second example some paths are coloured grey to indicate that, while they exist, they do not form part of the path from to .

Define to be the sum of the absolute changes in height (or -coordinate) over all uphill and downhill sections of the path from to . In the first example above, the path climbs over eleven uphill sections, and descends over ten downhill sections, giving . You are also given .

Let be the sum of over all pairs of primes, . You are given .

Find giving your answer rounded to five digits after the decimal point.

Problem 975 content is attributed to Project Euler and included here under the CC BY-NC-SA 4.0 license.

Open official problem License details

Problem 975: Zeckendorf Representation Uniqueness

Mathematical Foundation

Definition 1 (Fibonacci Numbers). Define $F_1 = 1, F_2 = 2$, and $F_k = F_{k-1} + F_{k-2}$ for $k \ge 3$. (Equivalently, in the standard indexing: $F_k$ here equals $F_{k+1}$ in the $F_1=F_2=1$ convention.)

Theorem 1 (Zeckendorf, 1972). Every positive integer $n$ can be uniquely written as

Proof.

Existence (by strong induction on $n$): For $n = 1 = F_1$, the representation is trivial. Suppose all integers less than $n$ have a valid representation. Let $F_m$ be the largest Fibonacci number with $F_m \le n$. If $F_m = n$, we are done. Otherwise $0 < n - F_m < F_m$. Since $F_m \le n < F_{m+1} = F_m + F_{m-1}$, we have $n - F_m < F_{m-1}$. By the inductive hypothesis, $n - F_m$ has a Zeckendorf representation using Fibonacci numbers at most $F_{m-2}$ (since $n - F_m < F_{m-1}$ implies the largest term is at most $F_{m-2}$). Prepending $F_m$ gives a valid non-consecutive representation of $n$.

Uniqueness (by strong induction on $n$): Suppose $n = F_{k_1} + \cdots + F_{k_r} = F_{\ell_1} + \cdots + F_{\ell_s}$ are two valid representations with $k_1 > \cdots > k_r$ and $\ell_1 > \cdots > \ell_s$ (all indices differing by at least 2). We claim $k_1 = \ell_1$. If $k_1 > \ell_1$, then:

But by the identity $F_m + F_{m-2} + F_{m-4} + \cdots = F_{m+1} - 1$ (telescoping from $F_j = F_{j+1} - F_{j-1}$), the right side is at most $F_{\ell_1+1} - 1 < F_{\ell_1+1} \le F_{k_1}$. This contradicts $n \ge F_{k_1}$. By symmetry, $\ell_1 > k_1$ is also impossible, so $k_1 = \ell_1$. Canceling and applying the inductive hypothesis to $n - F_{k_1}$ gives $r = s$ and $k_i = \ell_i$ for all $i$. $\square$

Lemma 1 (Greedy Algorithm Correctness). The greedy algorithm --- repeatedly subtracting the largest Fibonacci number not exceeding the remainder --- produces the Zeckendorf representation.

Proof. The existence proof above is constructive via the greedy algorithm. By uniqueness (Theorem 1), this must yield the Zeckendorf representation. $\square$

Theorem 2 (Average Number of Terms). Let $\phi = (1+\sqrt{5})/2$. The average value of $z(n)$ for $1 \le n \le F_m - 1$ satisfies

as $m \to \infty$.

Proof. (Sketch.) The Zeckendorf representation induces a bijection between $\{1, \ldots, F_m - 1\}$ and binary strings of length $m - 1$ with no consecutive 1s (the “Fibonacci numeral system”). The number of 1-bits in a random such string has mean $\sim m/(\phi+2)$ by transfer matrix eigenvalue analysis. Since $F_m \approx \phi^m/\sqrt{5}$, we get $m \approx \log_\phi(F_m\sqrt{5})$, giving the stated asymptotic. $\square$

Editorial

Compute the sum of z(n) for n = 1 to 10^6, where z(n) is the number of terms in the Zeckendorf (greedy Fibonacci) representation of n. Every positive integer has a unique representation as a sum of non-consecutive Fibonacci numbers (Zeckendorf’s theorem). z(n) counts how many Fibonacci numbers are used. We precompute Fibonacci numbers up to N. We then fib = [1, 2, 3, 5, 8, 13, …] with fib[last] >= N. Finally, find largest fib[k] <= remainder.

Pseudocode

Precompute Fibonacci numbers up to N
fib = [1, 2, 3, 5, 8, 13, ...] with fib[last] >= N
Find largest fib[k] <= remainder

Complexity Analysis

• Time: $O(N \log_\phi N)$. For each of the $N$ integers, the greedy decomposition uses at most $O(\log_\phi N)$ steps. For $N = 10^6$, $\log_\phi(10^6) \approx 29$.
• Space: $O(\log_\phi N)$ for the Fibonacci table (about 30 entries for $N = 10^6$).

Answer

#include <bits/stdc++.h>
using namespace std;
int main() {
    const int N = 1000000;
    vector<long long> fibs = {1, 2};
    while (fibs.back() < N) fibs.push_back(fibs[fibs.size()-1]+fibs[fibs.size()-2]);
    long long total = 0;
    for (int n = 1; n <= N; n++) {
        int rem = n, cnt = 0;
        for (int i = fibs.size()-1; i >= 0; i--)
            if (fibs[i] <= rem) { rem -= fibs[i]; cnt++; }
        total += cnt;
    }
    cout << total << endl;
    return 0;
}

"""
Problem 975: Zeckendorf Representation

Compute the sum of z(n) for n = 1 to 10^6, where z(n) is the number of terms
in the Zeckendorf (greedy Fibonacci) representation of n.

Every positive integer has a unique representation as a sum of non-consecutive
Fibonacci numbers (Zeckendorf's theorem). z(n) counts how many Fibonacci numbers
are used.

Key results:
    - Greedy algorithm: subtract largest Fibonacci number <= n, repeat
    - The representation never uses two consecutive Fibonacci numbers
    - z(n) grows roughly as log_phi(n) on average
    - answer = sum of z(n) for n = 1..10^6

Methods:
    1. build_fibonacci       — generate Fibonacci numbers up to N
    2. zeckendorf_count      — greedy Fibonacci decomposition, return term count
    3. zeckendorf_decompose  — full decomposition returning the Fibonacci terms
    4. average_z_by_range    — mean z(n) over ranges for growth analysis
"""

from collections import Counter

def build_fibonacci(N):
    """Return list of Fibonacci numbers (starting 1, 2, 3, 5, ...) up to N."""
    fibs = [1, 2]
    while fibs[-1] < N:
        fibs.append(fibs[-1] + fibs[-2])
    return fibs

def zeckendorf_count(n, fibs):
    """Number of Fibonacci numbers in Zeckendorf representation of n."""
    c = 0
    for f in reversed(fibs):
        if f <= n:
            n -= f
            c += 1
    return c

def zeckendorf_decompose(n, fibs):
    """Return the list of Fibonacci numbers used in the Zeckendorf representation."""
    terms = []
    for f in reversed(fibs):
        if f <= n:
            n -= f
            terms.append(f)
    return terms

def average_z_by_range(N, fibs, num_bins=50):
    """Compute mean z(n) in equal-sized bins across [1, N]."""
    bin_size = N // num_bins
    bin_centers = []
    bin_means = []
    for i in range(num_bins):
        lo = i * bin_size + 1
        hi = (i + 1) * bin_size
        total = sum(zeckendorf_count(n, fibs) for n in range(lo, hi + 1))
        bin_centers.append((lo + hi) / 2)
        bin_means.append(total / bin_size)
    return bin_centers, bin_means

#  Verification
_fibs = build_fibonacci(100)
# 1 = F(1): z=1; 2 = F(2): z=1; 3 = F(3): z=1; 4 = F(3)+F(1) = 3+1: z=2
# 5 = F(4): z=1; 6 = F(4)+F(1) = 5+1: z=2; 7 = F(4)+F(2) = 5+2: z=2
# 8 = F(5): z=1; 10 = 8+2: z=2; 11 = 8+3: z=2; 12 = 8+3+1: z=3
assert zeckendorf_count(1, _fibs) == 1
assert zeckendorf_count(4, _fibs) == 2
assert zeckendorf_count(8, _fibs) == 1
assert zeckendorf_count(12, _fibs) == 3
assert zeckendorf_decompose(12, _fibs) == [8, 3, 1]

# No consecutive Fibonacci numbers in decomposition
for test_n in [20, 50, 99]:
    terms = zeckendorf_decompose(test_n, _fibs)
    fib_set = set(_fibs)
    for i in range(len(terms) - 1):
        idx_a = _fibs.index(terms[i])
        idx_b = _fibs.index(terms[i + 1])
        assert abs(idx_a - idx_b) >= 2, f"Consecutive Fibs in decomposition of {test_n}"

#  Main computation
N = 10 ** 6
fibs = build_fibonacci(N)
total = sum(zeckendorf_count(n, fibs) for n in range(1, N + 1))
print(total)

#  Visualization — 4-panel figure