077. 素数之和(Prime summations)

把十写成小于它的素数之和总共有五种不同的方法:

$$ \begin{aligned} &7 + 3\\ &5 + 5\\ &5 + 3 + 2\\ &3 + 3 + 2 + 2\\ &2 + 2 + 2 + 2 + 2 \end{aligned} $$
求第一个使得其表达成素数之和超过五千种方法的数。

分析:这道题和第三十一题和第七十六题非常类似,可以使用几乎一样的思路和代码加以解决。设\(i\)为某个自然数,\(j\)表示用前几个素数来表示\(i\),如当\(j=1\),则只用第一个素数也就是二来表示\(i\);当\(j=2\),则用前两个素数也就是二和三来表示\(i\),则\(w(i,j)\)为数\(i\)表示成前\(j\)个素数之和的方法数。显然当\(i=1\)时,\(w(i,j)=0\);当\(j=1\)时,如果\(i\)为偶数,则\(w(i,j)=1\);如果\(i\)为奇数,则\(w(i,j)=0\)。最后,我们设当\(i=0\)时,\(w(i,j)=1\)

\(\pi(i)\)表示小于等于\(i\)的素数的个数,则题目中要求的实际上就是\(w(i,\pi(i))\)。这道题和第三十一题唯一的区别在于:第三十一题中是把任意自然数表示成为特定的钱币单位之和,而这里是把任意自然数表示成为特定的素数之和。三十一题我们建立了一个钱币单位的列表,这里只需要建立一个特定素数的列表,事实表明这个列表非常短,只需要列出八十以下的素数就足够了,假设这个素数列表为\(primes\),则可以将状态转移方程表示如下:

$$ w\left( i,j \right) =\begin{cases} 1& i=0\\ 0& i=1\\ 1& j=1\ and\ j\ is\ even\\ 0& j=0\ and\ j\ is\ odd\\ w\left( i,j-1 \right)& i<primes\left[ j \right]\\ w\left( i,j-1 \right) +w\left( i-primes\left[ j \right] ,j \right)& otherwise\\ \end{cases} $$

将上述状态转移方程翻译为代码,我们就可以求出任意自然数表示成小于等于它的素数之和的方法数。我们从十一开始逐渐向上搜索,达到第一个方法数超过五千的数并返回,即为题目所求。代码如下:

# time cost = 1 ms

from sympy import primepi
from functools import lru_cache

primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79]

@lru_cache(maxsize=2048)
def ways(x,y):
    if x == 0:
        return 1
    elif x == 1:
        return 0
    elif y == 1:
        return 0 if x%2==1 else 1
    elif x < primes[y-1]:
        return ways(x,y-1)
    else:
        return ways(x,y-1) + ways(x-primes[y-1],y)

def main(N=5000):
    i = 11
    while True:
        w = ways(i,primepi(i))
        if w > N:
            return i
        else:
            i += 1