77. Prime summations.md

77. Prime summations

Question

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3

5 + 5

5 + 3 + 2

3 + 3 + 2 + 2

2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?

Solution

Very similar to 76. Counting summations

def p77(N=5000):
    @lru_cache(maxsize=None)
    def f(n, i=0):
        """i: min index can be used to form the sum"""
        if n == 0: return 1
        if n < primes[i]: return 0
        res = 0
        for j in range(i, len(primes)):
            if primes[j] > n: break
            res += f(n - primes[j], j)
        return res

    primes = sieve(1000)  # sieve function see link below
    n, ways = 2, 1
    while ways <= N:
        n += 1
        ways = f(n)
    return n

Answer

71

Note

• sieve