Project Euler Problem 118

# 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
for dig in perm:
len_dig_key[i] = temp

if __name__ == '__main__':
populate_dicts()
result = solver(1)
print("The result is:", result)
```