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