Problem 618

p618.py

def compute(limit):
    d = [1] + [0] * limit
    primes = eulerlib.primes(limit)
    mod = 10**9
    Fibonnaci_numbers = [2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368]

    for p in primes:
        for i in range(p,limit+1):
            d[i] += (p*d[i-p] % mod)
    
    total = 0
    for x in Fibonnaci_numbers:
        total += (d[x] % mod)
        
    return total % mod