Problem 297: Zeckendorf Representation

Mathematical Foundation

We use the Fibonacci sequence $F_1 = 1, F_2 = 2, F_3 = 3, F_4 = 5, F_5 = 8, \ldots$ defined by $F_k = F_{k-1} + F_{k-2}$ with $F_1 = 1, F_2 = 2$.

Theorem 1 (Zeckendorf’s Theorem). Every positive integer $n$ has a unique representation $n = \sum_{i \in S} F_i$ where $S \subset \mathbb{N}$ and $S$ contains no two consecutive indices.

Proof. (Existence) By strong induction. For $n = 1 = F_1$, the result holds. For $n > 1$, let $F_k$ be the largest Fibonacci number $\leq n$. Then $0 \leq n - F_k < F_{k-1}$ (since $F_{k+1} = F_k + F_{k-1} > n$). By induction, $n - F_k$ has a Zeckendorf representation using Fibonacci numbers $\leq F_{k-2}$ (no $F_{k-1}$ appears because $n - F_k < F_{k-1}$), so the representation is non-consecutive.

(Uniqueness) Suppose $n = \sum_{i \in S} F_i = \sum_{j \in T} F_j$ with $S \neq T$. Let $k$ be the largest index in $S \triangle T$. WLOG $k \in S \setminus T$. Then $\sum_{j \in T, j > k} F_j = 0$ (since $k$ is the largest in the symmetric difference and elements $> k$ match). But $\sum_{j \in T, j \leq k-2} F_j \leq F_{k-2} + F_{k-4} + \cdots < F_k$ (by a standard Fibonacci identity), a contradiction since the $T$-sum must account for $F_k$. $\square$

Theorem 2 (Recurrence for $S(N)$ at Fibonacci Boundaries). Define $S(N) = \sum_{n=1}^{N-1} z(n)$. Then

Proof. The integers in $[1, F_{k+1})$ split into $[1, F_k)$ and $[F_k, F_{k+1})$. The first group contributes $S(F_k)$.

For the second group: each integer $n \in [F_k, F_{k+1})$ can be written uniquely as $n = F_k + m$ where $0 \leq m < F_{k-1}$. Since $n \geq F_k$ and $n < F_{k+1} = F_k + F_{k-1}$, we have $m = n - F_k \in [0, F_{k-1})$. The Zeckendorf representation of $n$ is $F_k$ plus the Zeckendorf representation of $m$ (which uses only $F_1, \ldots, F_{k-2}$ since $m < F_{k-1}$, ensuring no consecutive indices with $F_k$).

Thus $z(n) = 1 + z(m)$ for $m > 0$, and $z(F_k) = 1$ (when $m = 0$). The total contribution is:

Hence $S(F_{k+1}) = S(F_k) + F_{k-1} + S(F_{k-1})$. $\square$

Theorem 3 (General Recursion). For $F_k \leq N < F_{k+1}$:

Proof. Split $[1, N)$ into $[1, F_k)$ and $[F_k, N)$. The first contributes $S(F_k)$. For the second, each $n \in [F_k, N)$ has $z(n) = 1 + z(n - F_k)$ as above. There are $N - F_k$ such integers, each contributing the extra $1$ for the $F_k$ term, plus $z(n - F_k)$. The residuals $n - F_k$ range over $[0, N - F_k)$, contributing $S(N - F_k)$. $\square$

Lemma 1 (Recursion Depth). The recursion in Theorem 3 terminates in $O(\log_\varphi N)$ steps, where $\varphi = (1+\sqrt{5})/2$.

Proof. At each step, $N$ is replaced by $N - F_k$ where $F_k \geq N/\varphi$ (since $F_k > N - F_{k-1} \geq N - N/\varphi = N/\varphi^2$, and actually $F_k \geq N/\varphi$ follows from $F_{k+1} > N$ and $F_{k+1}/F_k \to \varphi$). Thus $N - F_k \leq N(1 - 1/\varphi) = N/\varphi^2$, and after $j$ steps, $N$ is reduced to at most $N/\varphi^{2j}$. The recursion terminates when $N < F_2 = 2$, requiring $O(\log_\varphi N)$ steps. $\square$

Editorial

Fibonacci: F[0]=1, F[1]=2, F[2]=3, F[3]=5, … S(N) = sum of z(n) for n in [1, N). At Fibonacci boundaries: S(F[k+1]) = S(F[k]) + S(F[k-1]) + F[k-1] General recursion (F[k] <= N < F[k+1]): S(N) = S(F[k]) + (N - F[k]) + S(N - F[k]). We precompute Fibonacci numbers and S(F_k). Finally, recursive computation of S(N).

Pseudocode

Precompute Fibonacci numbers and S(F_k)
Recursive computation of S(N)

Complexity Analysis

• Time: $O(\log N)$ for precomputing $\sim \log_\varphi N \approx 83$ Fibonacci numbers and their $S$-values, plus $O(\log N)$ recursive steps.
• Space: $O(\log N)$ for storing Fibonacci numbers and $S(F_k)$ values (about 83 entries for $N = 10^{17}$).

Answer

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

// Problem 297: Zeckendorf Representation
//
// Find sum of z(n) for 0 < n < 10^17, where z(n) = number of terms
// in the Zeckendorf representation of n.
//
// Fibonacci: F[1]=1, F[2]=2, F[3]=3, F[4]=5, ...
//
// S(N) = sum of z(n) for n in [1, N).
//
// At Fibonacci boundaries:
//   S(F[k+1]) = S(F[k]) + S(F[k-1]) + F[k-1]
//
// General recursion (for F[k] <= N < F[k+1]):
//   S(N) = S(F[k]) + (N - F[k]) + S(N - F[k])
//
// Each recursive call reduces N, and the sequence of remainders follows
// a Zeckendorf-like decomposition, terminating in O(log N) steps.

int main(){
    long long N = 100000000000000000LL; // 10^17

    // Generate Fibonacci numbers: F[1]=1, F[2]=2, F[3]=3, ...
    vector<long long> F;
    F.push_back(1);
    F.push_back(2);
    while (F.back() < N) {
        F.push_back(F[F.size()-1] + F[F.size()-2]);
    }
    int M = F.size(); // F[0]..F[M-1] = F_1..F_M

    // Precompute S(F[k]) for k = 1..M
    // S(F[1]) = S(1) = 0 (sum over empty range [1,1))
    // S(F[2]) = S(2) = z(1) = 1
    // S(F[k+1]) = S(F[k]) + S(F[k-1]) + F[k-1]
    // Using 0-indexed: S_fib[i] = S(F[i])
    vector<long long> SF(M + 1, 0);
    // SF[0] = S(F[0]) = S(1) = 0
    // SF[1] = S(F[1]) = S(2) = z(1) = 1
    SF[0] = 0;
    if (M >= 2) SF[1] = 1;
    for (int i = 2; i < M; i++) {
        // S(F[i]) = S(F[i-1]) + S(F[i-2]) + F[i-2]
        // In 0-indexed: F[i] corresponds to F_{i+1}, F[i-2] = F_{i-1}
        // Wait, let me re-index carefully.
        // F[0] = F_1 = 1, F[1] = F_2 = 2, F[2] = F_3 = 3, ...
        // S(F_{k+1}) = S(F_k) + S(F_{k-1}) + F_{k-1}
        // In 0-indexed: S(F[i]) = S(F[i-1]) + S(F[i-2]) + F[i-2]
        SF[i] = SF[i-1] + SF[i-2] + F[i-2];
    }

    // Now compute S(N) recursively
    // S(N): find largest F[k] <= N, then S(N) = SF[k] + (N - F[k]) + S(N - F[k])
    // where k is 0-indexed into F array.
    // Note: N - F[k] < F[k-1], so recursion terminates.

    function<long long(long long)> S = [&](long long n) -> long long {
        if (n <= 1) return 0; // S(1) = 0, S(0) = 0
        // Find largest F[k] <= n
        // F is sorted, use upper_bound
        int k = (int)(upper_bound(F.begin(), F.end(), n) - F.begin()) - 1;
        // F[k] <= n < F[k+1]
        if (F[k] == n) return SF[k];
        return SF[k] + (n - F[k]) + S(n - F[k]);
    };

    cout << S(N) << endl;
    return 0;
}

"""
Project Euler Problem 297: Zeckendorf Representation

Find sum of z(n) for 0 < n < 10^17, where z(n) = number of terms
in the Zeckendorf representation of n.

Fibonacci: F[0]=1, F[1]=2, F[2]=3, F[3]=5, ...

S(N) = sum of z(n) for n in [1, N).

At Fibonacci boundaries:
  S(F[k+1]) = S(F[k]) + S(F[k-1]) + F[k-1]

General recursion (F[k] <= N < F[k+1]):
  S(N) = S(F[k]) + (N - F[k]) + S(N - F[k])
"""
import bisect

def solve():
    N = 10**17

    # Generate Fibonacci: F[0]=1, F[1]=2, F[2]=3, F[3]=5, ...
    F = [1, 2]
    while F[-1] < N:
        F.append(F[-1] + F[-2])
    M = len(F)

    # Precompute S(F[k]) for k = 0..M-1
    SF = [0] * M
    SF[0] = 0  # S(1) = 0
    if M >= 2:
        SF[1] = 1  # S(2) = z(1) = 1
    for i in range(2, M):
        SF[i] = SF[i-1] + SF[i-2] + F[i-2]

    def S(n):
        if n <= 1:
            return 0
        k = bisect.bisect_right(F, n) - 1
        if F[k] == n:
            return SF[k]
        return SF[k] + (n - F[k]) + S(n - F[k])

    print(S(N))

if __name__ == "__main__":
    solve()