134. 质数对连接(Prime pair connection)

考虑连续的质数\(p_1=19\)\(p_2=23\),可以验证\(1219\)是所有以\(p_1\)结尾并且可被\(p_2\)整除的数中最小的一个。

事实上除了\(p_1=3\)\(p_2=5\)这一对以外,对于任意一对连续质数\(p_2>p_1\)都存在一系列的整数\(n\),其尾数为\(p_1\)且可被\(p_2\)整除,则记\(S\)为所有\(n\)中的最小值。对于\(5\le p_1\le1000000\)内所有连续质数对,求\(\sum S\)

分析:根据题意,设我们要求的最小整数为\(x\),则它需要满足两个条件:一是它可被\(p_2\)整除,则有\(x\equiv 0(mod\ p_2)\)。二是\(x\)的尾数是\(p_1\),即不论\(p1\)是几位数,都必须完整地出现在\(x\)的末尾。比如对于\(1219\)\(19\)是一个两位数,也就是说\(1219\equiv 19(mod\ 100)\),如果是三位数,则显然应满足\(x\equiv p_1(mod\ 1000)\)。依次类推\(x\)应满足的条件是\(x\equiv \ p_{1} \ ( mod\ \lceil log_{10}( p_{1})\rceil )\)。综上有:

$$ \begin{cases} x\equiv \ 0\ ( mod\ p_{2})\\ x\equiv \ p_{1} \ ( mod\ \lceil log_{10}( p_{1})\rceil ) \end{cases} $$

我们可使用中国剩余定理求解以上线性同余方程组,则其中的最小正整数解即为题目所求。在\(python\)\(sympy\)库中可以使用\(crt()\)函数来求解线性同余方程组,同时\(sympy\)中也提供了素数筛可以筛出特定范围内的素数。需要注意的是,题目要求是\(p_1<10^6\),此时\(p_2\)是大于一百万的,所以筛选素数的范围要略大于一百万,即要包括\(1000003\)这个素数。代码如下:

# time cost = 2.22 s ± 15.5 ms

from sympy.ntheory.modular import crt
from math import log10,ceil
from sympy import primerange

def smallest_number(p1,p2):
    m = pow(10,ceil(log10(p1)))
    u,v = [0,p1],[p2,m]
    res = crt(v,u)[0]
    return res

def main(N=10**6+4):
    res = 0
    primes = list(primerange(5,N))
    for i in range(len(primes)-1):
        res += smallest_number(primes[i],primes[i+1])
    return res