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!

• Vishesh Mangla: The answer may lie here en.wikipedia.org/wiki/Fibonacci_number#/media/… . I 'm not sure but the classic dynamic programming problem of rod cutting might be the solution.
• Vishesh Mangla: Secondly try implementing this algorithm in c, it should run much much faster.
• Lady Be Good: @VisheshMangla okay, thanks. I will edit as soon as I try these.

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.