Python Implementation of Problem 118

View source code here on GitHub!

Includes

Problem Solution

Project Euler Problem 118

This one doesn't look pretty, but it was much faster to roll out my own loop than try to make combinations() work here. It's also more efficient because it recycles some of the number generation.

Problem:

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?

python.src.p0118.is_not_pandigital(*numbers: int) → int

If it's pandigital, returns 0. If not, returns the number of total digits

python.src.p0118.check(*numbers: int) → Tuple[bool, bool]

Returns two bools, indicating first whether to continue and second whether to increment answer.

python.src.p0118.nest(cached_primes: Tuple[int, ...], numbers: Tuple[int, ...], digits: int) → int
python.src.p0118.main() → int
 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

Tags: partition, prime-number, python-iterator