Statement
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?
Solution
Bruteforce solution with some tweaks.
First, I generate all the primes that can possibly be part of the subsets. This is done using combinations, to filter possible subset of digits that will never form primes and then using permutations to generate all the possible numbers and checking them against a function that bruteforces to check whether it's prime or not. These primes are stored in two "views", one that groups them by their length, and other which groups them by length and and digit so it's easy to grab all primes of a certain length that contain a certain digit. This is done in python using dictionaries.
To calculate the possibilities I use a recursive function which calculates the number of sets whose content has primes of length greater or equal to a given length, excluding the given used digits and whose primes are greater or equal to a given prime.
from itertools import permutations, combinations, chain from CommonFunctions import find_primes_less_than primes = find_primes_less_than(32000) def is_prime(n): if n == 1: return False limit = int(n ** 0.5) for p in primes: if p > limit: return True if n % p == 0: return False return True len_key = {} len_dig_key = {} def generator(length, used, prev_p): if length == 9: return [] complete_set = len_key[length].copy() for i in used: complete_set -= len_dig_key[length][i] return filter(lambda x: x > prev_p, complete_set) def solver(min_l, used=set(), prev_p=0): accum = 9 - len(used) result = sum(1 for i in generator(accum, used, prev_p)) for l in range(min_l, accum // 2 + 1): for p in generator(l, used, prev_p): new_used = used | set(map(int, str(p))) result += solver(l, new_used, p) return result def populate_dicts(): def filt_func(i): if len(i) == 1: return True if i[-1] & 1 == 0 or i[-1] == 5: return False return True for i in range(1, 9): len_key[i] = set() temp = {} for dig in range(1, 10): temp[dig] = set() comb = (c for c in combinations(range(1, 10), i) if sum(c) % 3 > 0) permut = filter(filt_func, chain.from_iterable(permutations(c, i) for c in comb) ) for perm in permut: p = int(''.join(map(str, perm))) if not is_prime(p): continue len_key[i].add(p) for dig in perm: temp[dig].add(p) len_dig_key[i] = temp len_key[1].add(3) len_dig_key[1][3].add(3) if __name__ == '__main__': populate_dicts() result = solver(1) print("The result is:", result)
The Python file is available for download here.
