-
Notifications
You must be signed in to change notification settings - Fork 0
/
0060euler_PrimePairSets.py
56 lines (47 loc) · 1.37 KB
/
0060euler_PrimePairSets.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# 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.
from itertools import permutations, combinations
from euler import is_prime
def digitSum(number):
total = 0
while number > 0:
digit = number % 10
total += digit
return total
print digitSum(311)
print digitSum(711)
print digitSum(7109)
def getConcatenated(primes):
primes = [str(prime) for prime in primes]
conCats = [int(''.join(p)) for p in permutations(primes, 2)]
for c in conCats:
if not is_prime(c):
return False
return True
def sundaram3(max_n):
numbers = range(3, max_n+1, 2)
half = (max_n)//2
initial = 4
for step in xrange(3, max_n+1, 2):
for i in xrange(initial, half, step):
numbers[i-1] = 0
initial += 2*(step+1)
if initial > half:
return [2] + filter(None, numbers)
def getCombinationsFive(primes):
for c in combinations(primes, 5):
print c
if getConcatenated(c):
return c, sum(c)
p = sundaram3(10000)
p.remove(2)
p.remove(5)
getCombinationsFive(p)