Python Implementation of Problem 60
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 60
Problem:
The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.
Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.
1"""
2Project Euler Problem 60
3
4Problem:
5
6The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the
7result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes,
8792, represents the lowest sum for a set of four primes with this property.
9
10Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.
11"""
12from collections import defaultdict
13from itertools import combinations
14from typing import DefaultDict, List, Set
15
16from .lib.primes import is_prime, primes
17
18
19def is_concat_prime(x: int, y: int) -> bool:
20 sx = str(x)
21 sy = str(y)
22 return is_prime(int(sx + sy)) and is_prime(int(sy + sx))
23
24
25def main() -> int:
26 iterator = primes()
27 cached_primes: List[int] = []
28 for p in iterator:
29 cached_primes.append(p)
30 if p > 4:
31 break
32 cached_primes.remove(2)
33 # 2 is excluded because higher even numbers can't be prime
34 cached_primes.remove(5)
35 # 5 is excluded because if a number ends with 5, it's divisible by 5
36 compat: DefaultDict[int, Set[int]] = defaultdict(set)
37 for x in iterator:
38 for y in cached_primes:
39 if is_concat_prime(x, y):
40 for a, b, c in combinations(compat[y], 3):
41 if a in compat[b] and a in compat[c] and b in compat[c]: # remember these are commutative
42 if is_concat_prime(a, x) and is_concat_prime(b, x) and is_concat_prime(c, x):
43 return x + y + a + b + c
44 compat[x].add(y)
45 compat[y].add(x)
46 cached_primes.append(x)
47 return -1 # pragma: no cover