0051 素数数字替换
* * * *
拉格朗日计划
* * * *
素数数字替换

将两位素数13的第一位数字1替换为其它数字,在九个可能的值中有六个是素数:13、23、43、53、73、83。

将五位素数56003的第三和第四位数字00替换为其它相等的数字,在十个可能值中有七个是素数:56003、56113、56333、56443、56663、56773、56993。

56003作为其中最小的数,也是满足同样性质(替换得到七个素数)的数中最小的一个。

通过将一个素数中不一定相邻但相等的一些数字替换为其它相等的数字,有时能够得到八个素数,求满足这一性质的最小素数。

本题难度:



解答

猜测这样的数至少应该有六位是合理的、且至少应该需要替换三个数字(也可以先穷举排除六位以下以及替换三个以下的情形),所以从能替换三个以上数字的六位数开始搜索。

先用筛法找出所有的六位、且含三个以上相同数字的素数。再依次尝试将重复数字替换为其它数字是否仍是素数,直到找到第一个符合要求的数为止。

结果是$121313$,对应的8个素数分别是121313、222323、323333、424343、525353、626363、828383、929393。

target=1000000
d=[0]*target
n=2

while n < target:
    for i in range(n+n,target,n):
        d[i]=d[i]+1
    n=n+1
    while n < target and d[n]>0:
        n=n+1
primeList=[n for n in range(100000,target) if d[n]==0]
primeSet=set(primeList)

def getMode(m):
    a=[0]*10
    while m>0:
        a[m%10]+=1
        m/=10
    return max([a[i],i] for i in range(10))

i=-1
found=False
while not found and i < len(primeList)-1:
    i+=1
    p=primeList[i]
    j,y=getMode(p)
    if j>=3:
        q=str(p)
        x=str(y)
        found=(sum(int(q.replace(x,k)) in primeSet for k in "0123456789")>=8)

print p