Zeckendorf Representation

Each new term in the Fibonacci sequence is generated by adding the previous two terms.
Starting with $1$ and $2$, the first $10$ terms will be: $1, 2, 3, 5, 8, 13, 21, 34, 55, 89$.
Every positive integer can be uniquely written as a sum of nonconsecutive terms of the Fibonacci sequence. For example, $100 = 3 + 8 + 89$.
Such a sum is called the Zeckendorf representation of the number.
For any integer $n \gt 0$, let $z(n)$ be the number of terms in the Zeckendorf representation of $n$.
Thus, $z(5) = 1$, $z(14) = 2$, $z(100) = 3$ etc.
Also, for $0 \lt n \lt 10^6$, $\sum z(n) = 7894453$.
Find $\sum z(n)$ for $0 \lt n \lt 10^{17}$.

This problem involves a deep understanding of number theory, more specifically Fibonacci sequences, and Zeckendorf’s theorem.

First, we notice that the desired sum is equal to the quantity of numbers that have a certain highest Fibonacci number in their Zeckendorf representation.
The observation here is that looking at numbers with a certain highest Fibonacci number in their representation is the same as considering sequences from that Fibonacci number. Therefore, we can count how many such sequences exist up to a certain Fibonacci number as the highest.

The argument from induction becomes essential here as it allows us to link the current Fibonacci number with the previous two, just like in the definition of Fibonacci numbers themselves.

For a number to have Fibonacci number $F_n$ as the highest number in its Zeckendorf representation, the sum with the preceding Fibonacci number $F_{n-1}$ can’t be used since it gives $F_{n+1}$ according to the definition of Fibonacci numbers.

If we denote by $g(n)$ the quantity of numbers with $F_n$ as the largest number in the Zeckendorf representation, we can state $g(n) = g(n-1) + g(n-2) + 2^{n-2}$;

The $2^{(n-2)}$ term is introduced to account for the situation as we don’t add the number $F_n$ as the highest number, which gives us $2^{(n-2)}$ possibilities comprised of $0, 1$ but none of them using the number $F_{n+1}$.

So far so good!
However, we want to find $\sum_{n=1} ^{N} z(n)$. We need to find an expression for $z(n)$ using $g(n)$. Notice that $z(n) = g(k)+1$, where k is the biggest number such that $F_k \le n$. Therefore, our objective function becomes $\sum_{n=1} ^N z(n) = \sum_{i=1} ^k g(n) + N$.

Great! Now we have two recursive formulas linked to each other. The next challenge is to deal with the upper bound $10^{17}$.

The key observation here is that, given the rate of growth of Fibonacci numbers (approximately increasing by a golden ratio), it will have around 90 terms less than $10^{17}$ (as $\phi^{90}$ is of the same order of magnitude as $10^{17}$). This means we need to find the first 90 levels of $g(n)$.

With those 90 terms, we can quickly scan over all numbers less than $10^{17}$ to find sums $\sum_{i=1} ^k g(n) + N$ for all $N$ less than $10^{17}$ by decreasing order of $N$ from $10^{17}$ to $1$.

This won’t take too much computational time: We are just considering all numbers between $F_k$ and $F_{k+1}$ to have the same $z(n)$, and their quantity is $F_{k+1} – F_k$, which is of the order of $F_k$ ($k$ ranging from $1$ to $90$).

Computing $F_k$, $g(k)$ for $k$ from 1 to 90, and then scanning for $\sum_{i=1} ^k g(n) + N$, will be doable in a reasonable computational time frame.

Please note that the problem at hand is pretty advanced and requires a deep understanding of number theory and programming skills to get through. The problem might even seem unsolvable at first glance. However, with a good understanding of recursion and the property of Fibonacci numbers, this seemingly insurmountable problem can be solved in a reasonable amount of time.

(Note: The problem is a competition-level problem and requires more sophisticated mathematics than typically encountered in standard high school coursework).

More Answers: