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
            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.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License