프로젝트 오일러 041

1-n 펜디지털 수에는 1부터 n까지의 모든 숫자가 등장합니다. 그런데 특정한 자리 수의 펜디지털 수들은 결코 소수가 될 수 없습니다. 눈치채셨겠지만 3의 배수는 모든 자리 수의 합이 3의 배수이기 때문에 1-2팬디지털 수, 1-3펜디지털수는 모두 3의 배수입니다. n에 따라서 각 자리 수의 합을 구해보면 실제로는 1-4 펜디지털수와 1-7펜디지털수에서만 소수가 나올 수 있는 가능성이 있습니다.

• n = 2 : 1 + 2 = 3 ··· 0
• n = 3 : 1 + 2 + 3 = 6 ··· 0
• n = 4 : 1 + 2 + 3 + 4 = 10 ··· 1
• n = 5 : 1 + 2 + 3 + 4 + 5 = 15 ··· 0
• n = 6 : 1 + 2 + 3 + 4 + 5 + 6 = 21 ··· 0
• n = 7 : 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 ··· 1
• n = 8 : 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36 ··· 0
• n = 9 : 1 + 2 + … + 8 + 9 = 45 ··· 0

팬디지털 소수

범위가 정해졌으니 7자리 이내의 팬디지털 수에서 소수를 찾으면 됩니다. 7자리로 범위를 한정하기는 했지만, 가장 큰 7자리 팬디지털 수는 7,654,321로 이 횟수만큼 루프를 돌면 시간이 오래 걸립니다. 최대 한계값이 정해져 있고, 가장 큰 팬디지털 소수를 구하면 되니, 한계값부터 검사하는 수를 줄여가면서 체크하면 첫번째로 만나는 수가 답이 되겠죠.

from itertools import permutations
from euler import isprime

def check(n=7):
    for xs in permutations(f'{c}' for c in range(n, 0, -1)):
        x = int(''.join(xs))
        if isprime(x):
            print(x)
            return True
    return False


@
def main():
    for k in (7, 4):
        if check(k):
            return


if __name__ == '__main__':
    main()

다른 풀이법도 가능합니다. 7654321까지의 모든 소수를 소수체로 구한 다음, 가장 큰 소수부터 팬디털인지 검사하는 방법도 있습니다.(이건 각자 구현해봅시다.)

문제에서는 1부터 n까지의 숫자를 한 번만 써서 만든 숫자를 팬디지털이라고 하지만, 팬디지털의 범위는 좀 더 넓어서 특정 진법에 사용되는 숫자가 최소 한 번 이상 사용된 정수는 모두 팬디지털이라고 합니다.