Project Euler Problem 755

Solution

Answer: 2877071595975576960

Let

$$F={1,2,3,5,8,\dots}$$

and let $f(n)$ be the number of subsets of $F$ whose elements sum to $n$.

Then

$$S(N)=\sum_{k=0}^N f(k)$$

counts all subsets of Fibonacci numbers whose total sum is at most $N$.

So the task is:

Count the subsets of distinct Fibonacci numbers with sum $\le 10^{13}$.

A very efficient recursion works.

If the available Fibonacci numbers are $F_0,\dots,F_i$, then:

either we do not use $F_i$,
or we do use $F_i$.

Hence:

$$C(i,x)=C(i-1,x)+C(i-1,x-F_i).$$

We also use a crucial shortcut:

$$x \ge \sum_{k=0}^i F_k,$$

then every subset is allowed, so

$$C(i,x)=2^{i+1}.$$

This reduces the number of states dramatically.

Python code:

from functools import lru_cache

N = 10**13

# Build Fibonacci numbers: 1,2,3,5,...
fibs = [1, 2]
while fibs[-1] + fibs[-2] <= N:
    fibs.append(fibs[-1] + fibs[-2])

# Prefix sums
prefix = []
s = 0
for x in fibs:
    s += x
    prefix.append(s)

@lru_cache(None)
def count_subsets(i, limit):
    # Number of subsets using fibs[0..i] with sum <= limit

    if limit < 0:
        return 0

    if i < 0:
        return 1  # empty subset

    # If limit already exceeds total possible sum,
    # every subset is valid.
    if limit >= prefix[i]:
        return 1 << (i + 1)

    # Can't use fibs[i]
    if fibs[i] > limit:
        return count_subsets(i - 1, limit)

    # Exclude or include fibs[i]
    return (
        count_subsets(i - 1, limit)
        + count_subsets(i - 1, limit - fibs[i])
    )

answer = count_subsets(len(fibs) - 1, N)

print(answer)

Verification on the given examples:

$S(100)=415$
$S(10^4)=312807$

Both are reproduced exactly.

Running the program for $N=10^{13}$ gives:

$$2877071595975576960$$

Answer: 2877071595975576960