Solution

Answer: 2252639041804718029

Let

$$F_1=1,\quad F_2=2,\quad F_n=F_{n-1}+F_{n-2}$$

so the Fibonacci sequence is

$$1,2,3,5,8,13,\dots$$

Every positive integer has a unique representation as a sum of nonconsecutive Fibonacci numbers from this sequence (Zeckendorf’s theorem).

Define $z(n)$ to be the number of Fibonacci terms in the Zeckendorf representation of $n$.

We must compute

$$\sum_{0<n<10^{17}} z(n).$$

Mathematical analysis

Define

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

We seek $S(10^{17})$.

1. Structure of Zeckendorf representations

Consider all numbers less than $F_k$.

Every number $n<F_k$ falls into one of two groups:

$0\le n<F_{k-1}$
$F_{k-1}\le n<F_k$

For the second group, write

$$n=F_{k-1}+m,$$

where necessarily

$$0\le m<F_{k-2},$$

because Zeckendorf representations cannot use consecutive Fibonacci numbers.

Thus

$$z(n)=1+z(m).$$

So the interval $[F_{k-1},F_k)$ contributes:

one extra Fibonacci term for each number,
plus the contribution from all $m<F_{k-2}$.

Hence:

$$S(F_k)=S(F_{k-1})+S(F_{k-2})+F_{k-2}.$$

(The term $F_{k-2}$ counts the extra “+1” over exactly $F_{k-2}$ values.)

2. Recurrence for exact Fibonacci boundaries

Define

$$A_k=S(F_k).$$

Then:

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

Base cases:

$$A_1=S(1)=0,$$

$$A_2=S(2)=z(1)=1.$$

This lets us compute all $A_k$ very quickly.

3. General recursion for arbitrary $N$

Let $F_k$ be the largest Fibonacci number with

$$F_k\le N.$$

Split the range $0<n<N$ into:

$0<n<F_k$
$F_k\le n<N$

The first contributes:

$$A_k.$$

For the second, every number has the form

$$F_k+m,\qquad 0\le m<N-F_k,$$

and therefore

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

So:

$$S(N)=A_k+(N-F_k)+S(N-F_k).$$

This recursion reduces $N$ by its largest Fibonacci summand each step, exactly mirroring the Zeckendorf decomposition.

Python implementation

from functools import lru_cache

LIMIT = 10**17

# ------------------------------------------------------------
# Build Fibonacci numbers:
# F1 = 1, F2 = 2
# ------------------------------------------------------------

fib = [1, 2]

while fib[-1] < LIMIT:
    fib.append(fib[-1] + fib[-2])

# ------------------------------------------------------------
# A[k] = S(F_k)
# where S(N) = sum_{0 < n < N} z(n)
#
# Recurrence:
# A[k] = A[k-1] + A[k-2] + F[k-2]
# ------------------------------------------------------------

A = [0] * len(fib)

A[0] = 0          # S(1)
A[1] = 1          # S(2)

for k in range(2, len(fib)):
    A[k] = A[k-1] + A[k-2] + fib[k-2]

# ------------------------------------------------------------
# Recursive computation of S(N)
# ------------------------------------------------------------

@lru_cache(None)
def S(N):
    if N <= 1:
        return 0

    # largest Fibonacci number <= N
    k = 0
    while k + 1 < len(fib) and fib[k + 1] <= N:
        k += 1

    # exact boundary
    if fib[k] == N:
        return A[k]

    # recursive decomposition
    return A[k] + (N - fib[k]) + S(N - fib[k])

# ------------------------------------------------------------
# Compute answer
# ------------------------------------------------------------

answer = S(10**17)

print(answer)

Code walkthrough

Building Fibonacci numbers

fib = [1, 2]
while fib[-1] < LIMIT:
    fib.append(fib[-1] + fib[-2])

Creates:

$$1,2,3,5,8,13,\dots$$

up to beyond $10^{17}$.

Precomputing $A_k=S(F_k)$

A[k] = A[k-1] + A[k-2] + fib[k-2]

This implements the recurrence derived earlier.

For example:

$$S(8)=10$$

because:

$$\begin{aligned} z(1)&=1\ z(2)&=1\ z(3)&=1\ z(4)&=2\ z(5)&=1\ z(6)&=2\ z(7)&=2 \end{aligned}$$

and

$$1+1+1+2+1+2+2=10.$$

Recursive computation

return A[k] + (N - fib[k]) + S(N - fib[k])

This corresponds exactly to:

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

The recursion depth is tiny because Zeckendorf decompositions are short.

Verification against the example

The problem states:

$$\sum_{0<n<10^6} z(n)=7894453.$$

Running the program gives exactly:

$$7894453.$$

So the method is validated.

Final verification

The final value is about $2.25\times 10^{18}$, which is reasonable:

there are $10^{17}$ numbers,
typical Zeckendorf representations use around $O(\log n)$ Fibonacci terms,
average term count is roughly in the low tens.

The computation is exact and matches the known sample check.

Answer: 2252639041804718029

Project Euler Problem 297