Python Implementation of Problem 51
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 51
Again, surprised how effective the brute force solution was
Problem:
By replacing the 1st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.
By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.
Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.
- python.src.p0051.check_mask(mask: List[str], largest_possible: int, L: int, Ls: int) Tuple[bool, int]
1"""
2Project Euler Problem 51
3
4Again, surprised how effective the brute force solution was
5
6Problem:
7
8By replacing the 1st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53,
973, and 83, are all prime.
10
11By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven
12primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993.
13Consequently 56003, being the first member of this family, is the smallest prime with this property.
14
15Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit,
16is part of an eight prime value family.
17"""
18from itertools import combinations, count, product
19from typing import List, Tuple
20
21from .lib.primes import is_prime
22
23all_digits = tuple(str(x) for x in range(10))
24non_zero = all_digits[1:]
25endings = ("1", "3", "7", "9")
26
27
28def main() -> int:
29 for L in count(5):
30 largest_possible: int = 10**L
31 for Ls in range(1, L - 1):
32 for indices in combinations(range(L - 1), Ls):
33 mask = ["d"] * L # d can be replaced by any digit
34 for index in indices:
35 mask[index] = "s" # s can be replaced by any single digit
36 valid, smallest = check_mask(mask, largest_possible, L, Ls)
37 if valid:
38 return smallest
39 return -1 # pragma: no cover
40
41
42def check_mask(mask: List[str], largest_possible: int, L: int, Ls: int) -> Tuple[bool, int]:
43 for start, middle, end in product(non_zero, product(all_digits, repeat=(L - Ls - 2)), endings):
44 digits = (start, *middle, end)
45 current = mask.copy()
46 for digit in digits:
47 current[current.index("d")] = digit
48 valid = 0
49 smallest = largest_possible
50 if current[0] == "s":
51 selection = non_zero
52 else:
53 selection = all_digits
54 for s in selection:
55 new = [x if x != "s" else s for x in current]
56 num = int("".join(new))
57 if is_prime(num):
58 valid += 1
59 smallest = min(smallest, num)
60 elif 10 - int(s) + valid <= 8:
61 break
62 else:
63 return True, smallest
64 return False, 0