051. 质数数位替换(Prime digit replacements)

通过替换*3这样一个两位数的第一位,我们可以发现形成的九个数字有六个是质数,即13, 23,43,53,73,83。类似的,如果我们用同样的数字替换56**3这样一个五位数的第三位和第四位,会生成56003, 56113, 56333, 56443, 56663, 56773, 56993七个质数,事实是56003是拥有这个性质的最小质数。已知对于一个质数,可以通过使用相同的数字替换这个质数的一部分(不一定是相邻的数位),可以生成八个质数,求满足这个条件的最小质数。

分析:欧拉工程的前五十题都是难度系数为5%的题,这是我们碰到的第一道难度系数为15%的题,所以在解题思路上会相对更复杂一些。因为题目对所求质数是几位数以及替换数位有几位都没有给出规定,所以需要我们自己来分析以缩小筛选的范围。首先我们来看如果要满足题目的要求,替换的数位应该是几位。我们知道一个数字的各位数之和如果能够被三整除,则这个数字必然可以被三整除。因此,假设我们所求质数\(p\)的各位数之和为\(s\),则\(s\)除三的余数只能等于一或者二,设这个余数为\(r\),即\(s\equiv r\ (mod\ 3)\)。假设我们替换的数位个数为\(d\),即当\(d=1\)时,我们替换质数\(p\)的一位数;当\(d=2\)时,我们替换质数\(p\)的两位数,同时假设\(d\)除三的余数为\(x\),即\(d\equiv x\ (mod\ 3)\),则\(x\)的取值有\(0,1,2\)三种情况。

假设\(x=0\),即\(d\)是三的倍数,我们可以替换原数字的三位数、六位数、九位数等等。易知替换形成的九个数的各位数数字之和分别为\(s+d,s+2d,s+3d\cdots,s+9d\),则这九个数除三的余数为:

$$ s+kd\equiv r+kx\ (mod\ 3)\equiv r\ (mod\ 3)\quad (k=1,2,\cdots,9) $$

因为\(r=1\)或者\(r=2\),则易知这九个数都不能被三整除。则我们可以得出结论说:如果替换的数位是三或者三的倍数,则形成的数字必然不能被三整除。现在假设\(d\)不是三的倍数,则\(x\)会取一或者二。当\(x=1\)时,形成的九个数除三的余数分别为\(r+1,r+2\cdots,r+9\),显然这九个连续的自然数中会有三个被三整除,从而使得替换后形成的质数最多只有七个,不能满足题目要求。同理,当\(x=2\)时,形成的九个数除三的余数分别为\(r+2,r+4\cdots,r+18\),这九个数中同样会有三个被三整除,使得形成的质数只有七个。据此,我们可以得出结论:除非替换的数位个数是三或者三的倍数,否则形成质数个数最多只能有七个,不能满足题目要求。

此外,因为我们要求的是满足要求的最小质数,因此最小质数的被替换的数位只是\(0,1,2\),因为如果数位大于二,则比它的大的数最多只有六个,不可能形成八个满足条件的数。最后,因为要求重复的数位至少要有三位,则所求质数至少应是一个四位数,因为111,222,333之类的三位数必然不是素数。综上,我们得出所求质数必然要满足三个条件:(1)至少要是一个四位数,我们可以从数字1111开始搜寻;(2)重复的数位只能是三或三的倍数;(3)重复的数字只能是0, 1, 2三个数。

根据以上的推理,我们可以编写一个函数判断某个质数是否是符合条件的数。首先判断重复数位是否是三或三的倍数以及重复数字是否是0, 1, 2。如果不满足要求,则返回假。如果满足要求,则将其重复数字依次替换成比它大的截至到九的数字,统计形成的数中有多少个质数,如果形成的质数个数不等于八,则返回假,否则返回这个质数,即为我们要求的数。我们从1111开始向上搜寻,找到的第一个符合条件的数即为题目所求。代码如下:

# time cost = 355 ms ± 1.51 ms

from sympy import nextprime,isprime
from collections import Counter

def is_replacable_prime(n):
    s = str(n)
    count = Counter(s)
    num,d = count.most_common(1)[0]
    if d % 3 == 0 and num in set('012'):
        k = 1
        for j in range(int(num)+1,10):
            new = s.replace(num,str(j))
            if isprime(int(new)):
                k += 1
        if k == 8:
            return True
    return False

def main():
    n = 1111
    while True:
        p = nextprime(n)
        if is_replacable_prime(p):
            return p
        else:
            n = p