python – Project Euler Problem #755

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
$nge 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 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 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 can be done more?

  • I am aware of this is one of the last questions of the Euler Project. Therefore, probably it requires a depth of math. However, I lack that. It is okay if you share just only the names of formulas or theories. I can try them to implement my current code.
  • Probably code also has algorithmic fallacies or misinterpretations of question. If there is one you can just mention where it is and why there is a problem, not the solution.
    Thanks in advance.!