Project Euler 41

题目

Pandigital prime

We shall say that an \(n\)-digit number is pandigital if it makes use of all the digits \(1\) to \(n\) exactly once. For example, \(2143\) is a \(4\)-digit pandigital and is also prime.

What is the largest \(n\)-digit pandigital prime that exists?

解决方案

观察前\(9\)项\(1\sim n\)中所有数之和\(p(n)=\dfrac{n(n+1)}{2}\)的值：

\[1,3,6,10,15,21,28,36,45\]

可以发现，当\(n\neq 1,4,7\)时，\(p(n)\equiv 0 \pmod 3\)。

这说明在其它情况下，无论里面的数位排列如何，它们都是\(3\)的倍数，故对这一部分的数不需要进行判断。

对于剩下的数，用itertools库中的permutations对每一个排列进行遍历，并判断拼成的数是不是质数。

判断大质数使用gmpy2中的is_prime，它会以\(2^{-64}\)的概率将一个合数判断成质数。这个函数将会封装在自定义的tools工具包中。

代码

from itertools import permutations
from gmpy2 import is_prime

ls = [7, 4, 1]
ok = False
for n in ls:
    per = permutations([n - i for i in range(n)])
    for p in per:
        w = int("".join(str(x) for x in p))
        if is_prime(w):
            ans = w
            ok = True
            break
    if ok:
        break
print(ans)