71 lines
1.4 KiB
Python
71 lines
1.4 KiB
Python
from lib_prime import primes, is_prime_rabin_miller
|
|
from math import isqrt
|
|
|
|
|
|
def next_larger_prime(n):
|
|
""" Returns the next prime larger or equal to n. """
|
|
if n == 1:
|
|
return 2
|
|
|
|
n += 1
|
|
if n % 2 == 0:
|
|
n += 1
|
|
|
|
|
|
for _ in range(1000):
|
|
if is_prime_rabin_miller(n):
|
|
return n
|
|
n += 2
|
|
assert False
|
|
|
|
|
|
def m(n):
|
|
higher_prime = next_larger_prime(n + 1)
|
|
m = higher_prime - n
|
|
return m
|
|
|
|
|
|
def admissible(xs, threshold):
|
|
found = set()
|
|
numbers = [(xs[0], 0)]
|
|
|
|
while numbers:
|
|
value, index = numbers.pop()
|
|
if value >= threshold:
|
|
continue
|
|
if index == len(xs) - 1:
|
|
found.add(value)
|
|
numbers.append((value * xs[index], index))
|
|
if index < len(xs) - 1:
|
|
numbers.append((value * xs[index + 1], index + 1))
|
|
return found
|
|
|
|
|
|
def euler_293():
|
|
n = 10**9
|
|
assert next_larger_prime(1) == 2
|
|
assert next_larger_prime(7) == 11
|
|
assert m(630) == 11
|
|
|
|
m_set = set()
|
|
ps = primes(isqrt(n) + 10*8)
|
|
|
|
pow2 = 2
|
|
while pow2 < n:
|
|
mv = m(pow2)
|
|
m_set.add(mv)
|
|
pow2 *= 2
|
|
|
|
for i in range(len(ps)):
|
|
xs = ps[0:i + 1]
|
|
for x in admissible(xs, n):
|
|
m_set.add(m(x))
|
|
|
|
return sum(m_set)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
solution = euler_293()
|
|
print("e293.py: " + str(solution))
|
|
assert solution == 2209
|