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

The Fibonacci sequence of this problem starts with $1$ and $2$, and every further term is the sum of the previous two: $F_1=1$, $F_2=2$ and $F_{k+2}=F_{k+1}+F_k$, so the terms are $1,2,3,5,8,13,21,34,55,89,\dots$. Every positive integer can be written in exactly one way as a sum of distinct terms of this sequence of which no two are consecutive terms, for example $100=3+8+89$; this sum is the Zeckendorf representation of the number. For $n\gt0$, $z(n)$ is the number of terms in the Zeckendorf representation of $n$, so $z(5)=1$, $z(14)=2$ and $z(100)=3$. The statement gives the sum of $z(n)$ over $0\lt n\lt10^6$ as $7894453$ and asks for the sum of $z(n)$ over $0\lt n\lt10^{17}$. ^[1]

The whole solution in one sentence: every number from a Fibonacci number up to the next one is that Fibonacci number plus a smaller number and has exactly one term more than the smaller number, so each total splits into two smaller totals plus one extra term per number of the last block, and a recursion that remembers its results needs only $104$ totals for the limit $10^{17}$.

Mathematical Approach

We start with small numbers, prove the theorem behind the representation, and then turn one identity about the numbers between two Fibonacci numbers into a recursion for the total.

1. Small numbers

To write down a representation, take the largest Fibonacci number that does not exceed the number and repeat with the rest; Section 2 shows that this greedy method always produces the Zeckendorf representation. For $n=1,2,\dots,13$ it gives $1$, $2$, $3$, $3+1$, $5$, $5+1$, $5+2$, $8$, $8+1$, $8+2$, $8+3$, $8+3+1$ and $13$, so the counts $z(1),\dots,z(13)$ are

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

Likewise $14=13+1$ and $100=89+8+3$. Writing $1$ for each Fibonacci number that is used and $0$ for each one that is not, from the largest term down to $F_1$, turns a representation into a row of digits: $100$ becomes $1000010100$, with ones at the places of $89$, $8$ and $3$. The rows are exactly the strings of zeros and ones that start with $1$ and have no two neighbouring ones, and $z(n)$ counts the ones. ^[3] The empty sum represents $0$, so $z(0)=0$.

The list already shows a pattern: from $8$ to $12$ the counts are $1,2,2,2,3$, which are the counts $0,1,1,1,2$ of the numbers $0,\dots,4$, each increased by $1$. Section 3 proves that this happens after every Fibonacci number, and the whole solution rests on it.

2. Why the representation exists and is unique

Lemma. If distinct terms of the sequence, no two of them consecutive, have the largest term $F_j$, then their sum is less than $F_{j+1}$.

Proof by induction on $j$. If $F_j$ is the only term, the sum $F_j$ is less than $F_{j+1}$; for $j\le2$ this is the only possibility, since the only term below $F_2$ is $F_1$, which is consecutive to $F_2$. Otherwise the remaining terms have a largest term $F_i$ with $i\le j-2$, so by the induction hypothesis they add up to less than $F_{i+1}\le F_{j-1}$, and the whole sum is less than $F_j+F_{j-1}=F_{j+1}$. $\square$

Uniqueness. By the lemma, the largest term $F_j$ of any representation of $n$ satisfies $F_j\le n\lt F_{j+1}$, so it is the largest Fibonacci number not exceeding $n$, the one the greedy method takes. The other terms represent $n-F_j$, and by induction on $n$ that representation is unique as well.

Existence. Every Fibonacci number is its own representation. For any other $n$, choose $j$ with $F_j\lt n\lt F_{j+1}$; then $j\ge3$, and the rest $r=n-F_j$ satisfies $0\lt r\lt F_{j+1}-F_j=F_{j-1}$. By induction $r$ has a representation, and all its terms are at most $r\lt F_{j-1}$, so adding $F_j$ creates no consecutive pair. Together, uniqueness and existence are Zeckendorf's theorem, and the existence proof is the greedy method. ^[2]

3. One Fibonacci block

Claim. Let $k\ge2$. The numbers $n$ with $F_k\le n\lt F_{k+1}$ are exactly the numbers $F_k+r$ with $0\le r\lt F_{k-1}$, and for each of them

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

Proof. The first statement holds because $F_{k+1}-F_k=F_{k-1}$. For the second, every term of the representation of $r$ is at most $r\lt F_{k-1}$, so its index is at most $k-2$. Adding the term $F_k$ therefore gives distinct terms, no two of them consecutive, with the sum $F_k+r$. By uniqueness this is the representation of $F_k+r$, and it has one term more than that of $r$. $\square$

In digit rows, the block consists of the rows of length $k$ that begin with $10$, followed by the row of any number below $F_{k-1}$, written with $k-2$ digits. For $k=5$ this is the block $8,\dots,12$ of Section 1. The OEIS entry for $z$ records the same identity. ^[3]

4. The total to compute

For $N\ge1$ let $S(N)$ be the total number of terms of all numbers below $N$:

$$S(N)=\sum_{n=0}^{N-1}z(n).$$

Since $z(0)=0$, the requested sum is $S(10^{17})$, and the statement says that $S(10^6)=7894453$. Adding up the counts of Section 1 gives the first totals $S(1),\dots,S(13)$:

$0,1,2,3,5,6,8,10,11,13,15,17,20.$

In particular $S(N)=N-1$ for $1\le N\le4$, because $1$, $2$ and $3$ have one term each. The OEIS lists these totals as the partial sums of $z$, shifted by one place. ^[3]

5. The recursion

Claim. Let $N\ge3$, and let $p=F_k$ be the largest Fibonacci number strictly below $N$. Then

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

Proof. As $N\ge3$ we have $k\ge2$, and as $p$ is the largest Fibonacci number below $N$, also $N\le F_{k+1}$, so $1\le N-p\le F_{k-1}$. The numbers below $p$ contribute $S(p)$. The other numbers below $N$ are $p+r$ with $0\le r\lt N-p$; by Section 3 each of them has $1+z(r)$ terms, so together they contribute $(N-p)+S(N-p)$. $\square$

Both arguments on the right are smaller than $N$, and $N-p\ge1$, so a recursion based on this formula never needs $S(0)$. The word "strictly" matters: for a Fibonacci number $N=F_{k+1}$ we get $p=F_k$ and a complete block, whereas $p=N$ would only give $S(N)=S(N)+0+S(0)$, and the recursion would never end.

6. Totals at Fibonacci numbers

For $N=F_{k+1}$ we have $p=F_k$ and $N-p=F_{k-1}$, so with $A_k=S(F_k)$ the recursion becomes, for $k\ge2$,

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

starting from $A_1=S(1)=0$ and $A_2=S(2)=1$. Hence $A_3=1+0+1=2$, $A_4=2+1+2=5$, $A_5=5+2+3=10$, and further $A_6=20$, $A_7=38$, $A_8=71$, $A_9=130$ and $A_{10}=S(89)=235$.

In the usual numbering $f_0=0$, $f_1=1$, $f_{m+2}=f_{m+1}+f_m$ of the Fibonacci numbers we have $F_k=f_{k+1}$, so the recurrence reads $A_{k+1}=A_k+A_{k-1}+f_k$. The sums $C_k=\sum_{j=0}^{k}f_j\,f_{k-j}$ of the products of two Fibonacci numbers whose indices add up to $k$ form the self-convolution of the Fibonacci numbers; for example $C_4=1\cdot2+1\cdot1+2\cdot1=5$. In $C_{k+1}$ the term with $j=k$ is $f_k$, the term with $j=k+1$ is $0$, and writing $f_{k+1-j}=f_{k-j}+f_{k-1-j}$ in the other terms splits them into $C_k$ and $C_{k-1}$. So $C_{k+1}=C_k+C_{k-1}+f_k$, and since $C_1=0$ and $C_2=1$, induction gives $C_k=A_k$. Substituting into the recurrence confirms the closed form recorded for these numbers: ^[4]

$$A_k=\frac{(k-1)\,f_k+2k\,f_{k-1}}{5}.$$

Since $f_k/f_{k+1}$ tends to $1/\varphi$ with $\varphi=(1+\sqrt5)/2$, and $(\varphi+2)(\varphi^2+1)=5\varphi^2$, the average $A_k/F_k$ of the counts below $F_k$ grows like $k/(\varphi^2+1)\approx0.276\,k$, in agreement with Lekkerkerker's theorem. ^[5]

7. Worked example: $S(100)$

The largest Fibonacci number below $100$ is $89$, so $S(100)=S(89)+11+S(11)$. The largest one below $11$ is $8$, and $S(11)=S(8)+3+S(3)$${}=10+3+2=15$, with $S(8)=A_5$ and $S(3)=A_3$. With $S(89)=A_{10}=235$ from Section 6,

$$S(100)=235+11+15=261.$$

Here $11$ counts the leading term $89$ of the numbers $89,\dots,99$, and $S(11)$ the rest of their terms, which are the terms of $0,\dots,10$. Counting the terms of all numbers from $1$ to $99$ one by one also gives $261$.

8. Which values the recursion needs

Let $N=F_{k_1}+F_{k_2}+\dots+F_{k_t}$ be the Zeckendorf representation, with $k_1\gt k_2\gt\dots\gt k_t$. If $t\ge2$, the largest Fibonacci number below $N$ is $F_{k_1}$, and $N-F_{k_1}$ is the tail $F_{k_2}+\dots+F_{k_t}$. So the recursion only meets $N$, its tails and Fibonacci numbers, and $S(F_{k+1})$ only needs $S(F_k)$ and $S(F_{k-1})$. Unrolling it gives

$$S(N)=\sum_{i=1}^{t}\bigl(A_{k_i}+(i-1)\,F_{k_i}\bigr).$$

This can also be seen directly: for $i=1,\dots,t$ the numbers from $P=F_{k_1}+\dots+F_{k_{i-1}}$ to $P+F_{k_i}-1$ are $P+r$ with $r\lt F_{k_i}$, and these ranges contain every number below $N$ exactly once. For $i\ge2$ the smallest index in $P$ is $k_{i-1}\ge k_i+2$, while $r$ only uses indices up to $k_i-1$, so the two representations join without a consecutive pair and $z(P+r)=(i-1)+z(r)$; for $i=1$, where $P=0$, this is trivial. For $100=89+8+3$ the formula gives $235+(10+8)+(2+6)=261$ once more.

With memoisation, which stores every computed total and looks it up when it is needed again, ^[7] the recursion therefore computes few totals. For $N=10^{17}$ the representation has $26$ terms, the largest being $F_{82}$, and the recursion stores $104$ totals: those of the $79$ Fibonacci numbers from $F_4=5$ to $F_{82}$, of $10^{17}$ itself and of $24$ of its tails; the last tail, $3$, is a base case. In general a limit $N\lt F_{k+1}$ leads to at most $k$ Fibonacci numbers and, because the indices $k_i$ differ by at least $2$, to at most $k/2$ tails. Since $F_k$ is the integer nearest to $\varphi^{k+1}/\sqrt5$, ^[6] $k$ is about $\log_\varphi N$, so only $O(\log N)$ totals are ever stored.

How the Code Works

The C++ program ^[9] starts in main. parse_arguments fills an Options record: the limit is $10^{17}$ unless --limit= gives another positive number, read digit by digit by parse_i64_after_prefix, and --skip-checkpoints turns the check off. Unless that flag is set, run_checkpoints requires solve(1000000) to return $7894453$, the value from the statement, and the program stops with exit code $2$ otherwise. A fresh Solver then computes the total for the limit and prints it.

The constructor of Solver fills the vector fib_ with $1,2,3,5,\dots$ while the last term is below $10^{18}$, so the table ends with $F_{87}=1100087778366101931$ and has $87$ entries. solve(n) empties memo_, an unordered_map from arguments to totals, and calls the private method S(n), which carries out Sections 4 and 5 with the memoisation of Section 8:

For $n\le4$ the method returns $n-1$, the base values of Section 4. The formula would give $-1$ for $n=0$, but by Section 5 that argument never occurs.
Otherwise, if $n$ is a key of memo_, it returns the stored total.
Otherwise std::lower_bound finds the first table entry that is not less than $n$; ^[8] the entry before it is $p$, the largest Fibonacci number strictly below $n$, and the method stores and returns S(p) + (n - p) + S(n - p).

The Python and Java versions have the same Solver, but no options and no checkpoint: Python's solve(limit), with the default limit $10^{17}$, and Java's solve() return the total for $10^{17}$ as a string, which is printed. Python finds $p$ by scanning self.fib from the front, keeps the totals in a dictionary and raises the recursion limit to $2000$, far above the $81$ nested calls that occur; Java writes the binary search out by hand over an ArrayList<Long> and uses a HashMap<Long, Long>. C++ and Java compute with signed 64-bit integers (long long, long), Python with unlimited integers.

Complexity and Verification

Each stored total is computed once, with one search and two calls, so the number of calls is one more than twice the number of stored totals: for $N=10^{17}$ there are $104$ totals and $209$ calls, and the longest chain of nested calls, from $S(10^{17})$ through $S(F_{82}),S(F_{81}),\dots,S(F_4)$ to the base case $S(F_3)$, has $81$ of them. The table has a fixed size of $87$, so a search costs about $7$ comparisons in C++ and Java and at most $87$ in Python's scan. If the table is extended as $N$ grows, it needs $O(\log N)$ entries, and Section 8 bounds the number of stored totals by $O(\log N)$; counting each operation on a number and each access to the memo table as one step, the method then takes $O(\log N\,\log\log N)$ time with binary search, $O(\log^2N)$ with the scan, and $O(\log N)$ memory. All three programs finish in a few hundredths of a second.

The totals fit into 64 bits at the default limit. Every $n\lt10^{17}\lt F_{83}$ uses only terms up to $F_{82}$, no two of them consecutive, so $z(n)\le41$; the bound is attained by $F_{82}-1=F_{81}+F_{79}+\dots+F_1$. Hence every total in the computation is below $41\cdot10^{17}$, which is less than $2^{63}\approx9.2\cdot10^{18}$. For limits given with --limit=, neither the 64-bit range nor the end of the table is checked.

Unless --skip-checkpoints is given, the C++ program checks $S(10^6)=7894453$ from the statement before the main computation; Python and Java run no checks. For this article, all $196418$ digit rows of length $25$ without two neighbouring ones were listed: their values are the numbers $0,\dots,196417$, each exactly once, as Section 2 predicts, and counting their ones confirms Section 3 and the recursion for every limit up to $F_{26}=196418$. The greedy method confirms the recursion for every limit up to $10^6$, and the unrolled formula of Section 8, with the closed form of Section 6, for $20270$ limits up to $10^{18}$, among them every power of ten and every Fibonacci number with its two neighbours. All three programs print the same total for $10^{17}$, which the unrolled formula reproduces, and with --limit=10 and --limit=100 the C++ program prints $13$ and $261$, as in Sections 4 and 7. These checks are not part of the published solutions.

Footnotes and References

The references below supply the background facts used above. The proofs of the block identity and of the recursion, the unrolled formula and all counts of stored totals and calls are derived or computed in this article.

Project Euler 297 — Zeckendorf Representation. The official statement defines the Fibonacci sequence starting with 1 and 2, the Zeckendorf representation, as in 100 = 3 + 8 + 89, and z(n), the number of its terms; it gives z(5) = 1, z(14) = 2, z(100) = 3 and the sum 7894453 of z(n) for 0 < n < 10⁶, and asks for the sum for 0 < n < 10¹⁷.
Wikipedia — Zeckendorf's theorem. Every positive integer is uniquely a sum of distinct, non-consecutive Fibonacci numbers. The article proves existence by strong induction, choosing Fⱼ < n < Fⱼ₊₁ and representing n − Fⱼ, proves uniqueness, notes that the greedy algorithm finds the representation, and credits Edouard Zeckendorf (1972).
OEIS A007895 — Number of terms in the Zeckendorf representation of n. The entry starts 0, 1, 1, 1, 2, 1, 2, 2, 1 from n = 0, describes a(n) as the number of ones of the n-th binary number without two neighbouring ones, and gives a(F(n+1) + i) = a(i) + 1 for 0 ≤ i < F(n), with F(1) = F(2) = 1: the identity of Section 3. Its partial sums form A179180, whose term with index n is S(n + 1) in this article.
OEIS A001629 — Self-convolution of Fibonacci numbers. The entry lists 0, 0, 1, 2, 5, 10, 20, 38, 71, 130, 235, … from n = 0, the recurrence a(n) = a(n − 1) + a(n − 2) + F(n − 1) and the closed form ((n − 1)F(n) + 2nF(n − 1))/5, with F the usual Fibonacci numbers; in Section 6, Aₖ = a(k).
M. Kologlu, G. Kopp, S. J. Miller and Y. Wang — On the number of summands in Zeckendorf decompositions (arXiv:1008.3204). The abstract recalls Lekkerkerker's theorem: the integers in [Fₙ, Fₙ₊₁) have on average n/(φ² + 1) + O(1) summands, with φ the golden mean.
Wikipedia — Fibonacci sequence. In the usual numbering f₀ = 0, f₁ = 1, Binet's formula makes fₙ the integer closest to φⁿ/√5 for n ≥ 0, with φ = (1 + √5)/2; Section 8 applies this to Fₖ = fₖ₊₁.
Wikipedia — Memoization. An optimisation technique that stores the results of expensive calls of pure functions and returns the stored result when the same input occurs again.
cppreference — std::lower_bound. The function returns the first element of a sorted range that is not ordered before the given value, or the end of the range if there is none, with at most log₂(N) + O(1) comparisons for N elements.
C++ — Euler297.cpp. The linked immutable C++ revision contains Options, parse_arguments, the class Solver with its memoised method S, and run_checkpoints. It is the implementation record for this article.

Problem 297 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

namespace {

using i64 = long long;

struct Options {
    i64 limit = 100000000000000000LL;
    bool run_checkpoints = true;
};

bool parse_i64_after_prefix(const std::string& arg, const std::string& prefix, i64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    i64 parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<i64>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_i64_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.limit >= 1;
}

class Solver {
public:
    Solver() {
        fib_.push_back(1);
        fib_.push_back(2);
        while (fib_.back() < 1000000000000000000LL) {
            const i64 n = fib_[fib_.size() - 1] + fib_[fib_.size() - 2];
            fib_.push_back(n);
        }
    }

    i64 solve(const i64 n) {
        memo_.clear();
        return S(n);
    }

private:
    i64 S(const i64 n) {
        if (n <= 4) {
            return n - 1;
        }
        const auto it = memo_.find(n);
        if (it != memo_.end()) {
            return it->second;
        }

        auto lb = std::lower_bound(fib_.begin(), fib_.end(), n);
        const i64 p = *(lb - 1);
        const i64 value = S(p) + (n - p) + S(n - p);
        memo_.emplace(n, value);
        return value;
    }

    std::vector<i64> fib_;
    std::unordered_map<i64, i64> memo_;
};

bool run_checkpoints() {
    Solver solver;
    if (solver.solve(1000000) != 7894453LL) {
        std::cerr << "Checkpoint failed for limit 1e6" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    Solver solver;
    std::cout << solver.solve(options.limit) << '\n';
    return 0;
}

Python

import sys

sys.setrecursionlimit(2000)

class Solver:
    def __init__(self):
        self.fib = [1, 2]
        while self.fib[-1] < 1000000000000000000:
            self.fib.append(self.fib[-1] + self.fib[-2])
        self.memo = {}

    def S(self, n):
        if n <= 4:
            return n - 1
        if n in self.memo:
            return self.memo[n]

        # Find largest Fibonacci number less than n
        lb = 0
        for i, val in enumerate(self.fib):
            if val >= n:
                lb = i
                break

        p = self.fib[lb - 1]
        value = self.S(p) + (n - p) + self.S(n - p)
        self.memo[n] = value
        return value

    def solve(self, n):
        self.memo.clear()
        return self.S(n)

def solve(limit=100000000000000000):
    solver = Solver()
    return str(solver.solve(limit))

if __name__ == '__main__':
    print(solve())

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Euler297 {
    static class Solver {
        List<Long> fib;
        Map<Long, Long> memo;

        Solver() {
            fib = new ArrayList<>();
            fib.add(1L);
            fib.add(2L);
            while (fib.get(fib.size() - 1) < 1000000000000000000L) {
                long n = fib.get(fib.size() - 1) + fib.get(fib.size() - 2);
                fib.add(n);
            }
            memo = new HashMap<>();
        }

        long solve(long n) {
            memo.clear();
            return S(n);
        }

        long S(long n) {
            if (n <= 4) {
                return n - 1;
            }
            if (memo.containsKey(n)) {
                return memo.get(n);
            }

            int lb = 0;
            // binary search equivalent
            int l = 0, r = fib.size() - 1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (fib.get(mid) >= n) {
                    lb = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }

            long p = fib.get(lb - 1);
            long value = S(p) + (n - p) + S(n - p);
            memo.put(n, value);
            return value;
        }
    }

    public static String solve() {
        Solver solver = new Solver();
        return String.valueOf(solver.solve(100000000000000000L));
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}