Python Implementation of Problem 118
View source code here on GitHub!
Includes
Problem Solution
1"""
2Project Euler Problem 118
3
4This one doesn't look pretty, but it was much faster to roll out my own loop than try to make combinations() work here.
5It's also more efficient because it recycles some of the number generation.
6
7Problem:
8
9Using all of the digits 1 through 9 and concatenating them freely to form decimal integers, different sets can be
10formed. Interestingly with the set {2,5,47,89,631}, all of the elements belonging to it are prime.
11
12How many distinct sets containing each of the digits one through nine exactly once contain only prime elements?
13"""
14from itertools import takewhile
15from math import ceil, log10
16from typing import Tuple
17
18from .lib.primes import primes
19
20is_slow = True
21all_digits = set("123456789")
22max_digits = {
23 2: 8,
24 3: 7,
25 4: 6,
26 5: 5,
27 6: 3,
28}
29
30
31def is_not_pandigital(*numbers: int) -> int:
32 """If it's pandigital, returns 0. If not, returns the number of total digits"""
33 string = "".join(str(n) for n in numbers)
34 length = len(string)
35 if length == 9 and set(string) == all_digits:
36 return 0
37 return length
38
39
40def check(*numbers: int) -> Tuple[bool, bool]:
41 """Returns two bools, indicating first whether to continue and second whether to increment answer."""
42 if numbers[-2] >= numbers[-1]:
43 return (True, False) # otherwise we can't guarantee uniqueness
44 length = is_not_pandigital(*numbers)
45 if length == 9:
46 return (True, False) # this means any nested loops can't be pandigital
47 if not length:
48 return (True, True) # if this set is pandigital, skip nested loops
49 return (False, False)
50
51
52def nest(cached_primes: Tuple[int, ...], numbers: Tuple[int, ...], digits: int) -> int:
53 answer = 0
54 for x in takewhile((10**(9 - digits)).__gt__, cached_primes):
55 cont, inc = check(*numbers, x)
56 answer += inc
57 x_digits = digits + int(ceil(log10(x)))
58 if not cont and len(numbers) < 6:
59 answer += nest(cached_primes, (*numbers, x), x_digits)
60 return answer
61
62
63def main() -> int:
64 answer = 0
65 cached_primes = tuple(primes(98765432)) # should be largest eligible number
66 for a in takewhile((10**5).__gt__, cached_primes):
67 a_digits = int(ceil(log10(a)))
68 answer += nest(cached_primes, (a, ), a_digits)
69 return answer