Project Euler Problem #755

Question

As the title indicates this is one of the last most problems of Project Euler. The problem is straightforward. However, similar to the rest of the Euler Project problems either Memory Error or long execution times are problems. An explanation of the problem is:

Consider the Fibonacci sequence \$\{1,2,3,5,8,13,21,\ldots\} \$.

We let \$f(n)\$ be the number of ways of representing an integer \$n\ge 0\$ as the sum of different Fibonacci numbers. For example, \$16 = 3+13 = 1+2+13 = 3+5+8 = 1+2+5+8\$ and hence \$f(16) = 4\$ . By convention \$f(0) = 1\$ .

Further we define, \$\displaystyle S(n) = \sum_{k=0}^n f(k)\$ You are given \$S(100) = 415\$ and \$S(10^4) = 312807 \$ .

Find \$ \displaystyle S(10^{13})\$ .

I'll show my code, and then explain what I have done so far. Lastly, ask for any kind of help. Thanks in advance.

"""
    * EULER PROJECT PROBLEM 755
"""
import itertools

def sumOfList(aList):
    sumL = 0
    for x in aList:
        sumL += x
    yield sumL

mostList = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657,
             46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465,
             14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170,
             1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173,
             86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920,
             2504730781961, 4052739537881, 6557470319842]

def fibonList(x):
    fibonSeq = []
    firstT = 0

    while mostList[firstT] <= x:
        fibonSeq.append(mostList[firstT])
        firstT += 1

    yield fibonSeq

def powerset(iterable):
    b = list(set(iterable))
    for s in range(1, len(b) + 1):
        for comb in itertools.combinations(b, s):
            yield comb

def repWay(x):
    ways = 0
    for each in fibonList(x):
        for i, combo in enumerate(powerset(each), 1):
            for ea in sumOfList(combo):
                if ea == x:
                    ways += 1
    yield ways

def rangerepWays(x):
    generalSum = 0
    for i in range(x + 1):
        for x in repWay(i):
            generalSum += x
    yield generalSum + 1    # + 1 because 0 = 0, while creating fib list I didn't incorporate 0 into fiblist.

for x in rangerepWays(10 ** 2):
    print(x)

1- First: It works, but, unfortunately, is too slow.

• I have tested the program with the given examples in the question and it works. It passed both.

2- Second: What I have done

• As you can see, the functions don't return anything, instead, I used generators to avoid Memory Error errors.
• To prevent calculating Fibonacci numbers that are below a number at each recursion, I first created mostList than created a list whose elements are smaller than an upper limit.

3- Third: What else can be done?

• I am aware of this is one of the last questions of the Euler Project. Therefore, probably it requires a deep knowledge of mathematics. However, I lack that. It is okay if you share just only the names of applicable formulas or theories. I can try them to implement my current code.
• My code may also have algorithmic fallacies or misinterpretations of the question. If there is one, you can just mention where it is and why there is a problem, not the solution.

Thanks in advance!

Answer 1

A low hanging fruit first. You don't need to work through the entire powerset. Given that \$i_0 < i_1 < ... < i_k\$, and \$N = F_{i_0} + F_{i_1} + ... + F_{i_k}\$, how small \$F_{i_k}\$ could be?

Recall that \$F_0 + F_1 + ... + F_n = F_{n+2} - 2\$. As long as \$F_{n+2} - 2 < N\$, a representation is impossible, so the term \$F_n\$ cannot be the largest. Therefore, the largest term in the representation must satisfy both \$F_n \le N\$ and \$F_{n+2} - 2 \ge N\$. Since the Fibonacci numbers grow exponentially, this observation drastically reduces the choice of the largest term (one or two possibilities, depending on how \$N\$ compares to \$F_{n+1}\$).

That alone shall give you a boost.

---

Yet it is still bruteforcing. As you correctly say, there must be an underlying math.

I played with your program, printing the total number of representations for numbers between \$F_n\$ and \$F_{n+1}\$. The results are surprising:

Range     Total
3..4      3
5..7      5
8..12     11
13..20    21
21..33    43
34..54    85

Hmm... \$T_{n+1} = 2T_n - 1\$. Something to prove about, isn't it? Try. I don't want to spoil the fun.

---

For a proper review:

• I don't see the reason for sumOfList, fibList, repWay, and rangerepWays being generators. yield only make sense if it breaks the natural control flow, while preserving some execution context. Those above have no context to preserve; they can safely return. Making them generators only adds overhead.

  powerset is a different story. It yields in the midst of a (nested) loop.

• Naming deserves some attention. It took me a while to understand what, say, repWays is supposed to accomplish. Along the same line, mostList is a list of the Fibonacci numbers, isn't it? - so name it accordingly.