Pandigital prime sets
Problem 118
Using all of the digits 1 through 9 and concatenating them freely to form decimal integers, different sets can be formed. Interestingly with the set {2,5,47,89,631}, all of the elements belonging to it are prime.
How many distinct sets containing each of the digits one through nine exactly once contain only prime elements?
from tools import is_prime_v2
perm = [1, 2, 3, 4, 5, 6, 7, 8, 9]
def next_permutation():
i = len(perm) - 1
while perm[i - 1] >= perm[i]:
i = i - 1
if i == 0:
return False
j = len(perm)
while perm[j - 1] <= perm[i - 1]:
j = j - 1
# swap values at position i-1 and j-1
perm[i - 1], perm[j - 1] = perm[j - 1], perm[i - 1]
i += 1
j = len(perm)
while i < j:
perm[i - 1], perm[j - 1] = perm[j - 1], perm[i - 1]
i += 1
j -= 1
return True
def check_partitions(start_index, prev):
count = 0
for i in range(start_index, len(perm)):
# form the number x of the digits startIndex -> i
number = 0
for j in range(start_index, i + 1):
number = number * 10 + perm[j]
# We only count ordered sets, so check that the current number is larger than the previous
if number < prev:
continue
# Check that number is prime
if not is_prime_v2(number):
continue
# No more digits so return
if i == (len(perm) - 1):
return count + 1
count += check_partitions(i + 1, number)
return count
def run():
count = 0
while next_permutation():
count += check_partitions(0, 0)
return count