Open Source · 7 Languages · 900+ Problems

Project Euler Solutions

Complete solutions in C++, Python & Java — with step-by-step mathematical explanations

All Problems

Problem 297: Zeckendorf Representation

Project Euler Problem 297 Solution

EulerSolve provides an optimized solution for Project Euler Problem 297, Zeckendorf Representation, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Let $z(n)$ be the number of Fibonacci terms used in the Zeckendorf representation of $n$. The solver computes the prefix sum $S(N)=\sum_{0 \le n < N} z(n),$ with $z(0)=0$, and the Project Euler target is $S(10^{17})$. Mathematical Approach 1. Zeckendorf representation and notation The code uses the shifted Fibonacci basis $F_1=1,\qquad F_2=2,\qquad F_{k+2}=F_{k+1}+F_k,$ so the sequence is $1,2,3,5,8,\dots$. Zeckendorf's theorem says that every positive integer has a unique expansion $n = F_{i_1}+F_{i_2}+\cdots+F_{i_t}, \qquad i_{j+1}\ge i_j+2,$ meaning that no two consecutive Fibonacci numbers are used. The quantity $z(n)$ is exactly the number $t$ of summands in that unique expansion. 2. Exact structure of one Fibonacci block Fix $k\ge 2$. Because $F_{k+1}=F_k+F_{k-1},$ every integer in the half-open interval $[F_k,F_{k+1})$ can be written uniquely as $n = F_k + r,\qquad 0 \le r < F_{k-1}.$ Now $r < F_{k-1}$, so the Zeckendorf representation of $r$ cannot contain $F_{k-1}$. Therefore adding $F_k$ creates no adjacency conflict, and we get the exact identity $z(F_k+r)=1+z(r).$ This is the key bijection behind the whole solution: the block $[F_k,F_{k+1})$ is just the smaller block $[0,F_{k-1})$ with one extra leading term $F_k$. 3....

Detailed mathematical approach

Problem Summary

Let $z(n)$ be the number of Fibonacci terms used in the Zeckendorf representation of $n$. The solver computes the prefix sum

$S(N)=\sum_{0 \le n < N} z(n),$

with $z(0)=0$, and the Project Euler target is $S(10^{17})$.

Mathematical Approach

1. Zeckendorf representation and notation

The code uses the shifted Fibonacci basis

$F_1=1,\qquad F_2=2,\qquad F_{k+2}=F_{k+1}+F_k,$

so the sequence is $1,2,3,5,8,\dots$. Zeckendorf's theorem says that every positive integer has a unique expansion

$n = F_{i_1}+F_{i_2}+\cdots+F_{i_t}, \qquad i_{j+1}\ge i_j+2,$

meaning that no two consecutive Fibonacci numbers are used. The quantity $z(n)$ is exactly the number $t$ of summands in that unique expansion.

2. Exact structure of one Fibonacci block

Fix $k\ge 2$. Because

$F_{k+1}=F_k+F_{k-1},$

every integer in the half-open interval $[F_k,F_{k+1})$ can be written uniquely as

$n = F_k + r,\qquad 0 \le r < F_{k-1}.$

Now $r < F_{k-1}$, so the Zeckendorf representation of $r$ cannot contain $F_{k-1}$. Therefore adding $F_k$ creates no adjacency conflict, and we get the exact identity

$z(F_k+r)=1+z(r).$

This is the key bijection behind the whole solution: the block $[F_k,F_{k+1})$ is just the smaller block $[0,F_{k-1})$ with one extra leading term $F_k$.

3. Prefix sums at Fibonacci boundaries

Define

$A_k = S(F_k).$

Summing the previous identity over all $r\in[0,F_{k-1})$ gives

$A_{k+1}-A_k = \sum_{r=0}^{F_{k-1}-1}(1+z(r)) = F_{k-1}+A_{k-1}.$

So the boundary values satisfy

$A_{k+1}=A_k+F_{k-1}+A_{k-1}.$

The first values are

$A_1=0,\quad A_2=1,\quad A_3=2,\quad A_4=5,\quad A_5=10,\quad A_6=20.$

For example, $[8,13)=\{8,9,10,11,12\}$ has Zeckendorf term counts

$1,2,2,2,3,$

whose sum is $10$. Since $A_5=S(8)=10$, we obtain $A_6=S(13)=20$.

4. General recurrence for arbitrary $N$

Let $p$ be the largest Fibonacci number strictly smaller than $N$, say $p=F_k$. Then $N \le F_{k+1}$, hence

$0 \le N-p \le F_{k-1}.$

So the same block argument works on the truncated interval $[p,N)$: for every $0\le r < N-p$,

$z(p+r)=1+z(r).$

Summing over $[0,N)$ gives

$S(N)=S(p)+(N-p)+S(N-p).$

This is exactly the formula implemented in S(n). The binary search only exists to find that largest $p$.

5. Worked example: $N=10$

The largest Fibonacci below $10$ is $p=8$. Therefore

$S(10)=S(8)+(10-8)+S(2)=10+2+1=13.$

Direct inspection confirms it. The numbers $8$ and $9$ have Zeckendorf term counts $1$ and $2$, so the extra contribution beyond $S(8)$ is $3$, exactly as the formula predicts.

6. Why memoization is enough

Every recursive step replaces $N$ by the pair $(p,N-p)$, where both values are smaller and lie on lower Fibonacci scales. In fact the arguments that ever appear are exactly the suffix remainders in the greedy Zeckendorf decomposition of the original $N$. Since Fibonacci numbers grow exponentially, the number of relevant scales is only $O(\log N)$, so memoization is enough to make the recursion extremely small.

7. Checkpoints and interpretation

The C++ implementation verifies the checkpoint

$S(10^6)=7894453.$

Useful smaller values are

$S(5)=5,\qquad S(8)=10,\qquad S(13)=20,\qquad S(100)=261.$

These checkpoints test both Fibonacci-boundary values and non-boundary values, so they validate the recurrence rather well.

How the Code Works

The solver first precomputes the Fibonacci list up to $10^{18}$, which safely covers the target $10^{17}$. For each query $N$, it finds the largest $p<N$, applies

$S(N)=S(p)+(N-p)+S(N-p),$

stores the result in a hash map, and returns it. The wrapper solve(limit) only clears the memo table and starts this recursion.

Complexity Analysis

If $F_k \le N < F_{k+1}$, then the recursion depth is at most $k$, and with memoization the number of distinct states is also $O(k)$. Because $F_k$ grows exponentially, $k=O(\log N)$. Thus both time and memory are $O(\log N)$.