考虑一个有重复数字的四位素数，显然这四个数字不能全都一样：否则如1111能被11整除，2222能被22整除等等；不过有九个四位素数中包含三个一： $$1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111.$$ 记$M(n,d)$为n位素数中数字d重复出现的最多次数，$N(n,d)$为数字d出现$M(n,d)$次的n位素数的总数，$S(n,d)$是这些素数的和。

例如按上例，$M(4,1)=3$是四位素数中数字$1$重复出现的最多次数，有$N(4,1)=9$个这样的素数，它们的和是$S(4,1)=22275$。

类似地，读者可以自行验证下表 $$\begin{matrix} d & M(4,d) & N(4,d) & S(4,d) \\ 0 & 2 & 13 & 67061 \\ 1 & 3 & 9 & 22275 \\ 2 & 3 & 1 & 2221 \\ 3 & 3 & 12 & 46214 \\ 4 & 3 & 2 & 8888 \\ 5 & 3 & 1 & 5557 \\ 6 & 3 & 1 & 6661 \\ 7 & 3 & 9 & 57863 \\ 8 & 3 & 1 & 8887 \\ 9 & 3 & 7 & 48073 \end{matrix}$$ 因此$\sum\limits_{d=0}^9S(4,d)=273700$。

求$\sum\limits_{d=0}^9S(10,d)$。

本题难度:

解答

本题的解答过程较繁琐。重复基本策略是对每个d，从9开始（显然10个同样数字组成的数是合数）往1依次枚举$M(n,d)$。

因此先用筛法生成$10^5$以内的素数，对每个数字d，设其重复出现$m$次，则将$10-d$个其它数字插入可能的位置并检验素性。

结果是$612407567715$，其中0、2、8重复8次，其它数均重复9次。

import itertools

x=10

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

while n < target:
    for i in range(n+n,target,n):
        d[i]+=1
    n=n+1
    while n < target and d[n]>0:
        n+=1
p=[i for i in range(2,target) if d[i]==0]

def isPrime(n):
    i=0
    while i < len(p) and p[i]*p[i] < n and n%p[i]:
        i+=1
    return i>=len(p) or n%p[i]

q=[[],[],[],[],[],[],[],[],[],[]]
d=set("0123456789")
n=1
while d:
    r=set([])
    for i in d:
        j=int(i)
        t=0
        while t < 10**n:
            s=str(t).zfill(n)
            for pos in itertools.combinations(range(x),n):
                z=""
                v=0
                for u in range(x):
                    if v < n and u==pos[v]:
                        z+=s[v]
                        v+=1
                    else:
                        z+=i
                y=int(z)
                if y>10**(x-1) and isPrime(y):
                    q[j].append(y)
                    r.add(i)
            t+=1
    d=d-r
    n+=1

print sum(sum(i) for i in q)