The problem: https://projecteuler.net/problem=41
Consider the following count for sums from 1 to 9.
s = 0
for i in range(1, 10):
s += i
print("1 + ... +", i, "=", s, "= 3 *", s//3, "+", s%3)
This gives that a 2,3,5,6,8,9-digit number can't be a panditial prime because the sum of a pandigital number of that amount of digits will be divisible by three. The only real problem is that this doesn't exclude a 7-digit pandigital prime.
We know also that there isn't a 1-pandigital prime because the only one 1-pandigital number is 1, which isn't a prime.
$7! = 5040$ isn't big. Maybe testing all the possibilities isn't bad. Besides, we know we have to test only 4-digit and 7-digit pandigital numbers. $4! = 24$ isn't big at all.
Now, then, we go on to test all 4-digit pandigital numbers. To do this, we start with the 4-tuple (1, 2, 3, 4) and we keep permuting it until we get all the possible permutations of it. We do an entirely analogous procedure to generate all 7-digit pandigital numbers.
To generate all n-digit pandigital numbers, we can exploit the fact that the $n$-th order symmetric group $S_n$ is finite and generated by $(1 2)$, $(1 2 ... n)$. If we keep applying these two permutations on top of the initial 1 through n tuple, we'll eventually get all permutations of it.
def is_prime(n):
if n <= 1:
return False
i = 2
while i*i <= n:
if n % i == 0:
return False
i += 1
return True
def numeric_val_of(t):
n = 0
for d in t:
n *= 10
n += d
return n
def perm1(t):
t = t.copy()
t[0], t[1] = t[1], t[0]
return t
def perm_all(t, order):
t_out = [0]*order
for i in range(order):
t_out[(i+1) % order] = t[i]
return t_out
def all_order(order):
from collections import deque
queue = deque()
seen = set()
queue.append(list(range(1, order+1)))
while len(queue) > 0:
t = queue.popleft()
n = numeric_val_of(t)
if n not in seen:
seen.add(n)
queue.append(perm1(t))
queue.append(perm_all(t, order))
return seen
all4 = all_order(4)
all7 = all_order(7)
largest = -1 # We could have used 2143 from the problem statement as well.
for candidates in [all4, all7]:
for candidate in candidates:
if candidate > largest and is_prime(candidate):
largest = candidate
print(largest)