Detailed mathematical approach

Problem Summary

Let \(f_0=1\), \(f_1=2\), and \(f_{k+2}=f_{k+1}+f_k\). For a given bound \(N\), keep every term \(f_i\le N\). We must count how many subsets of this finite Fibonacci-like set have total sum at most \(N\).

If \(m\) is the largest index with \(f_m\le N\), then the target quantity is

$S(N)=\#\left\{B\subseteq \{f_0,f_1,\dots,f_m\}:\sum_{x\in B}x\le N\right\}.$

The title "Not Zeckendorf" signals that we are not restricting ourselves to the unique nonconsecutive Fibonacci representation of each integer. Every subset is allowed, so different subsets may produce the same sum, for example \(3\) and \(1+2\).

Mathematical Approach

The implementation solves the problem by recursive decomposition together with an exact pruning rule based on prefix sums.

Step 1: Build the finite search space

The recurrence \(f_{k+2}=f_{k+1}+f_k\) makes the sequence grow exponentially, so only \(O(\log N)\) terms are relevant. Once the largest usable index \(m\) is found, the whole problem becomes a subset-counting question on the finite set \(\{f_0,\dots,f_m\}\).

This matters because the original input \(N\) can be huge, but the number of candidate terms stays small enough for a state-based recursion.

Step 2: Define the counting state

For \(-1\le i\le m\) and \(L\ge 0\), define

$C(i,L)=\#\left\{B\subseteq \{f_0,f_1,\dots,f_i\}:\sum_{x\in B}x\le L\right\}.$

This means: among the first \(i+1\) terms, how many subsets stay within budget \(L\)? The desired answer is simply

$S(N)=C(m,N).$

The empty-set convention gives the base case

$C(-1,L)=1,$

because when no terms remain, only the empty subset survives.

Step 3: Split on the largest available term

Every admissible subset of \(\{f_0,\dots,f_i\}\) either avoids \(f_i\) or includes it.

If \(f_i\) is not chosen, the count is \(C(i-1,L)\).

If \(f_i\) is chosen, then the remaining elements must fit inside the reduced limit \(L-f_i\), which contributes \(C(i-1,L-f_i)\), but only when \(L\ge f_i\).

Therefore

$C(i,L)= \begin{cases} C(i-1,L), & L<f_i,\\ C(i-1,L)+C(i-1,L-f_i), & L\ge f_i. \end{cases}$

This is the exact include-or-exclude recurrence implemented in all three languages.

Step 4: Use the prefix-sum cutoff

Let

$P_i=\sum_{j=0}^{i} f_j.$

If \(L\ge P_i\), then even the subset containing every available term has sum at most \(L\). Hence every subset is feasible, so we get the closed form

$C(i,L)=2^{i+1}\qquad\text{whenever}\qquad L\ge P_i.$

This shortcut is exact, not heuristic. It prunes entire subtrees of the recursion.

For this particular sequence, the prefix sums also satisfy

$P_i=f_{i+2}-2,$

which follows by induction from the same Fibonacci-style recurrence. The implementations compute the prefix sums directly, then apply the cutoff test during recursion.

Step 5: Why memoization is enough

Different decision paths can lead to the same pair \((i,L)\). Once we know the largest usable index and the remaining budget, the earlier history no longer matters. Therefore the state graph is a directed acyclic graph rather than a tree of unrelated branches.

Memoization turns this observation into an exact algorithm: each distinct state \((i,L)\) is solved once, stored, and reused whenever it reappears.

Worked Example: \(N=10\)

The usable terms are

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

so the prefix sums are

$1,\ 3,\ 6,\ 11,\ 19.$

We want \(S(10)=C(4,10)\). Since \(10<19\), split on \(8\):

$C(4,10)=C(3,10)+C(3,2).$

For the first term, \(10<11\), so split on \(5\):

$C(3,10)=C(2,10)+C(2,5).$

Now \(10\ge 6\), hence

$C(2,10)=2^3=8.$

Next,

$C(2,5)=C(1,5)+C(1,2).$

Because \(5\ge 3\), we have \(C(1,5)=2^2=4\). Also

$C(1,2)=C(0,2)+C(0,0)=2+1=3.$

So \(C(2,5)=7\), and therefore \(C(3,10)=15\).

For the second branch, \(2<5\), so

$C(3,2)=C(2,2)=C(1,2)=3.$

Altogether,

$S(10)=15+3=18.$

Equivalently, \(15\) valid subsets avoid \(8\), while only \(3\) valid subsets use it: \(\{8\}\), \(\{8,1\}\), and \(\{8,2\}\).

How the Code Works

The C++, Python, and Java implementations first generate all Fibonacci-like terms not exceeding \(N\), then compute their prefix sums. After that they evaluate the recurrence top-down.

Each recursive state is identified by two pieces of information: the largest index still available and the remaining limit. If no terms remain, the state returns \(1\). If the remaining limit covers the full prefix sum, the state returns \(2^{i+1}\) immediately. Otherwise the implementation adds the exclude branch and, when allowed, the include branch.

To avoid recomputing identical states, the implementation stores previously solved limits separately for each index in hash-based lookup tables. The final call uses the largest index with \(f_i\le N\) and the original bound \(N\).

Complexity Analysis

Let \(k=m+1\) be the number of usable terms. Since \(f_i\) grows like \(\varphi^i\), we have \(k=\Theta(\log N)\).

If \(M\) denotes the number of distinct states \((i,L)\) actually visited, then both time and memory are \(O(M)\), because each state is computed once and then memoized. The recursion depth is \(O(k)=O(\log N)\).

A trivial upper bound is \(M=O(2^k)\), corresponding to the raw subset recursion, but the exact prefix-sum cutoff collapses many large branches immediately. That pruning is the reason the method is practical for the problem's input size.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=755
2. Fibonacci number: Wikipedia - Fibonacci number
3. Zeckendorf's theorem: Wikipedia - Zeckendorf's theorem
4. Subset sum problem: Wikipedia - Subset sum problem
5. Dynamic programming: Wikipedia - Dynamic programming