66 lines
1.2 KiB
Python
66 lines
1.2 KiB
Python
|
#!/usr/bin/env python3
|
||
|
|
|
||
|
|
from random import randint
|
||
|
|
from operator import mul
|
||
|
|
from functools import reduce
|
||
|
|
|
||
|
|
DEPTH = 5
|
||
|
|
SEQ = [1, 3, 7, 9, 13, 27]
|
||
|
|
NOTP = [5, 11, 15, 17, 19, 21, 23, 25]
|
||
|
|
|
||
|
|
|
||
|
|
def is_prime(n, depth=DEPTH):
|
||
|
|
r = 0
|
||
|
|
d = n - 1
|
||
|
|
while not d % 2:
|
||
|
|
r += 1
|
||
|
|
d //= 2
|
||
|
|
for k in range(depth):
|
||
|
|
a = randint(2, n - 2)
|
||
|
|
x = pow(a, d, n)
|
||
|
|
if x == 1 or x == n - 1:
|
||
|
|
continue
|
||
|
|
for i in range(r-1):
|
||
|
|
x = pow(x, 2, n)
|
||
|
|
if x == n-1:
|
||
|
|
break
|
||
|
|
else:
|
||
|
|
return False
|
||
|
|
return True
|
||
|
|
|
||
|
|
def test(m, nums):
|
||
|
|
return all((m**2 + r) % n for n in nums for r in SEQ)
|
||
|
|
|
||
|
|
def getmod(nums):
|
||
|
|
return [m for m in range(reduce(mul, nums)) if test(m, nums)]
|
||
|
|
|
||
|
|
def testseq(n):
|
||
|
|
for s in SEQ:
|
||
|
|
if not is_prime(n**2 + s):
|
||
|
|
return False
|
||
|
|
for s in NOTP:
|
||
|
|
if is_prime(n**2 + s):
|
||
|
|
return False
|
||
|
|
return True
|
||
|
|
|
||
|
|
|
||
|
|
nums = [2, 3, 5, 7, 11, 13, 17]
|
||
|
|
|
||
|
|
N = 150 * 10**6
|
||
|
|
|
||
|
|
n = 0
|
||
|
|
mods = getmod(nums)
|
||
|
|
step = reduce(mul, nums)
|
||
|
|
|
||
|
|
s = 0
|
||
|
|
|
||
|
|
while n < N:
|
||
|
|
for m in mods:
|
||
|
|
if n + m >= N:
|
||
|
|
break
|
||
|
|
if testseq(n+m):
|
||
|
|
s += n + m
|
||
|
|
n += step
|
||
|
|
|
||
|
|
print(s)
|