046. 另一个哥德巴赫猜想(Goldbach's other conjecture)

克里斯蒂安·哥德巴赫曾经提出任何一个奇合数都可以被写成一个质数和一个平方数的两倍的和,如:

$$ \begin{aligned} 9 &= 7+2\times1^2\\ 15 &= 7+2\times2^2\\ 21 &= 3 + 2\times3^2\\ 25 &= 7 + 2\times3^2\\ 27 &= 19 + 2\times2^2\\ 33 &= 31 + 2\times1^2 \end{aligned} $$
然而人们最终发现这个猜想是错误的,求最小的不能被写成一个质数和一个平方数的两倍之和的奇合数。

分析:简单分析一下题意,我们可以有两种思路:第一种思路是对任意的奇合数\(c\),找到所有小于它的质数\(p\),用这个奇合数分别减去这些质数再除以二,判断结果是否是一个平方数。根据素数定理,对任意正实数\(x\),设\(\pi(x)\)为小于\(x\)的素数个数,则\(\pi(x)\approx x/ln(x)\),则需要判断的次数也等于这个数。第二种思路是对任意奇合数\(c\),设其满足题目要求,则\(c=p+2k^2\),因为素数必大于一,即\(p=c-2k^2>1 \Rightarrow k<\sqrt{(c-1)/2}\),简单观察可以发现\(k<\pi(x)\),因此使用第二种方法需要验证的次数要小于第一种方法的验证次数。比如说对于奇合数5001,小于它的质数共有669个,因此使用第一种方法要做669次验证,而使用第二种方法只需要做不超过\(\sqrt{(5001-1)/2}=50\)次验证。我们需要编写一个验证一个奇合数是否存在满足题目要求的分解方法的函数,即对小于\(k\)的值逐一验证判断奇合数减去一个平方的二倍是否为一个质数,如果存在一个这样的质数,则退出循环。如果验证完所有小于\(k\)的值仍然未找到这样一个质数,则该奇合数不能表示题目要求的形式,即为所求。以下是对\(k<\pi(x)\)的严格证明,如果对此不感兴趣可以跳过,直观上知道第二种思路的验证次数更少就可以了。

为了证明\(k<\pi(x)\),考虑到至少在\(10^{25}\)范围内,\(\pi(x)>x/ln(x)\),则只需要证明:

$$ \sqrt{(x-1)/2}<x/ln(x) $$

利用对数平均不等式,即对所有的\(x\ge0,y\ge0\),有:

$$ \sqrt{xy}\le\frac{x-y}{lnx-lny}\le \frac{x+y}{2} $$

则有:

$$ \sqrt{\frac{x-1}{2}}<\sqrt{\frac{x}{2}}<\sqrt{x}<\frac{x-1}{lnx}<\frac{x}{lnx} $$

证明完毕。

from math import sqrt
from sympy import isprime

def nonexist(x):
    limit = int(sqrt((x-1)/2))
    for i in range(1,limit+1):
        if isprime(x-2*i**2):
            return False
    return True

def main():
    i = 35
    while True:
        if not isprime(i) and nonexist(i):
            return i
        i += 2