全数字素数集

考虑集合

{2, 5, 47, 89, 631}

，它的所有元素都是素数，且1到9的数字恰好各出现一次。

像这样的集合共有多少个？

本题难度:

解答

由于

1 + \dots + 9 = 45

，因此1到9的任何排列所形成的数都能被3整除，从而不是素数。所以这样的集合中至少有两个元素。

将9写成至少两个正整数的和，共有29种写法：

\begin{array}{r} 8 + 1 = 9 \\ 7 + 2 = 9 \\ 7 + 1 + 1 = 9 \\ 6 + 3 = 9 \\ 6 + 2 + 1 = 9 \\ 6 + 1 + 1 + 1 = 9 \\ 5 + 4 = 9 \\ 5 + 3 + 1 = 9 \\ 5 + 2 + 2 = 9 \\ 5 + 2 + 1 + 1 = 9 \\ 5 + 1 + 1 + 1 + 1 = 9 \\ 4 + 4 + 1 = 9 \\ 4 + 3 + 2 = 9 \\ 4 + 3 + 1 + 1 = 9 \\ 4 + 2 + 2 + 1 = 9 \\ 4 + 2 + 1 + 1 + 1 = 9 \\ 4 + 1 + 1 + 1 + 1 + 1 = 9 \\ 3 + 3 + 3 = 9 \\ 3 + 3 + 2 + 1 = 9 \\ 3 + 3 + 1 + 1 + 1 = 9 \\ 3 + 2 + 2 + 2 = 9 \\ 3 + 2 + 2 + 1 + 1 = 9 \\ 3 + 2 + 1 + 1 + 1 + 1 = 9 \\ 3 + 1 + 1 + 1 + 1 + 1 + 1 = 9 \\ 2 + 2 + 2 + 2 + 1 = 9 \\ 2 + 2 + 2 + 1 + 1 + 1 = 9 \\ 2 + 2 + 1 + 1 + 1 + 1 + 1 = 9 \\ 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 9 \\ 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 9 \end{array}

注意到一位的素数只有2、3、5、7四个，因此集合中最多只有四个一位数，从而可以排除形如

9 = 4 + 1 + 1 + 1 + 1 + 1

这样含有五个或以上1的拆分。

在其余

24

种拆分中，只有

9 = 8 + 1 = 7 + 2 = 7 + 1 + 1

含有七位和八位数。

因此先用筛法生成

10^{6}

以内的素数，保留此列表的同时也从中筛选出仅由不同数字组成的素数并按其长度分组。

对21种由不超过

10^{6}

的数组成的集合，遍历所有可能的组合。对另外3种包含七位和八位数的情况，检验由七个或八个不同数字的排列组成的数中是否存在素数。

经过十分繁琐的分情况计算最后可得结果是

44680

。

import itertools

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

p=[k for k in range(2,target) if d[k]==0]

def isBigPrime(n):
    i=0
    while p[i]*p[i]<=n and n%p[i]:
        i+=1
    return n%p[i]!=0

q={2:[],3:[],4:[],5:[],6:[]}
for n in p:
    r=str(n)
    if "0" not in r and len(r)>1 and len(set(r))==len(r):
        q[len(r)].append(r)

m5=set("14689")
m6=[set("124689"),set("134689"),set("145689"),set("146789")]
m7=[set("1234689"),set("1245689"),set("1246789"),set("1345689"),set("1346789"),set("1456789")]
m8=[set("13456789"),set("12456789"),set("12346789"),set("12345689")]

s=0

# 5 + 1 + 1 + 1 + 1 = 9
s+=sum(1 for i in q[5] if set(i)==m5)

# 3 + 2 + 1 + 1 + 1 + 1 = 9
s+=sum(1 for i in q[3] for j in q[2] if set(i+j)==m5)    

# 6 + 1 + 1 + 1 = 9
s+=sum(1 for i in q[6] if set(i) in m6) 

# 4 + 2 + 1 + 1 + 1 = 9
s+=sum(1 for i in q[4] for j in q[2] if set(i+j) in m6) 

# 3 + 3 + 1 + 1 + 1 = 9
s+=sum(1 for i in q[3] for j in q[3] if set(i+j) in m6)/2 

# 2 + 2 + 2 + 1 + 1 + 1 = 9
s+=sum(1 for i in q[2] for j in q[2] for k in q[2] if set(i+j+k) in m6)/6

# 3 + 2 + 2 + 1 + 1 = 9
s+=sum(1 for i in q[3] for j in q[2] for k in q[2] if set(i+j+k) in m7)/2

# 5 + 2 + 1 + 1 = 9
s+=sum(1 for i in q[5] for j in q[2] if set(i+j) in m7) 

# 4 + 3 + 1 + 1 = 9
s+=sum(1 for i in q[4] for j in q[3] if set(i+j) in m7) 

# 2 + 2 + 2 + 2 + 1 = 9
s+=sum(1 for a,b,c,d in itertools.product(q[2],repeat=4) if set(a+b+c+d) in m8)/24

# 4 + 2 + 2 + 1 = 9
s+=sum(1 for i in q[4] for j in q[2] for k in q[2] if set(i+j+k) in m8)/2

# 3 + 3 + 2 + 1 = 9
s+=sum(1 for i in q[3] for j in q[3] for k in q[2] if set(i+j+k) in m8)/2

# 6 + 2 + 1 = 9
s+=sum(1 for i in q[6] for j in q[2] if set(i+j) in m8)

# 4 + 4 + 1 = 9
s+=sum(1 for i in q[4] for j in q[4] if set(i+j) in m8)/2

# 5 + 3 + 1 = 9
s+=sum(1 for i in q[5] for j in q[3] if set(i+j) in m8)

# 5 + 2 + 2 = 9
s+=sum(1 for i in q[5] for j in q[2] for k in q[2] if len(set(i+j+k))==9)/2

# 4 + 3 + 2 = 9
s+=sum(1 for i in q[4] for j in q[3] for k in q[2] if len(set(i+j+k))==9)

# 3 + 3 + 3 = 9
s+=sum(1 for i in q[3] for j in q[3] for k in q[3] if len(set(i+j+k))==9)/6

# 6 + 3 = 9
s+=sum(1 for i in q[6] for j in q[3] if len(set(i+j))==9)

# 5 + 4 = 9
s+=sum(1 for i in q[5] for j in q[4] if len(set(i+j))==9)

# 3 + 2 + 2 + 2 = 9
s+=sum(1 for a in q[3] for b in q[2] for c in q[2] for d in q[2] if len(set(a+b+c+d))==9)/6

# 8 + 1 = 9
s+=sum(isBigPrime(int("".join(t))) for r in m8 for t in itertools.permutations(list(r)))

# 7 + 1 + 1 = 9
s+=sum(isBigPrime(int("".join(t))) for r in m7 for t in itertools.permutations(list(r)))

# 7 + 2 = 9
s+=sum(isBigPrime(int("".join(t))) for r in q[2] for t in itertools.permutations(list(set("123456789")-set(r))))

print s