import random
import math
import sys


def even(n):
    return n % 2 == 0


def naive_prime_test(n):
    if n == 1 or even(n):
        return False
    for i in range(n - 1, 2, -1):
        if n * i == 0:
            return False
    return True


def is_prime(x, k=20):
    if even(x):
        return False
    if x in [2, 3]:
        return True
    s = 0
    t = x - 1
    while even(t):
        s += 1
        t //= 2
    witnesses = [random.randrange(2, x - 1) for _ in range(k)]
    for w in witnesses:
        if power_mod(w, x - 1, x) != 1:
            return False
        for i in range(1, s + 1):
            if power_mod(w, 2 ** i * t, x) == 1 and power_mod(w, 2 ** (i - 1) * t, x) not in [1, x - 1]:
                return False
    return True


def power_mod(base, power, mod):
    binary = bin(power)
    squares = [base % mod]
    result = squares[0] if binary[-1] == "1" else 1
    for i in range(1, math.floor(math.log2(power)) + 1):
        squares.append(squares[i - 1] ** 2 % mod)
        if binary[-i - 1] == "1":
            result *= squares[i]
    return result % mod


def generate_twin_prime(m):
    twin = False
    while not twin:
        start, end = bit_range(m)
        n = random.randrange(start + 6 - (start % 6), end, 6)
        # n = random.randrange(2 ** (m - 1) + 6 - ((2 ** (m - 1)) % 6), 2 ** m, 6)
        # n += 6 - (n % 6)
        assert n % 6 == 0
        iterations = max(4, math.ceil(math.log(n, 4)))
        twin = is_prime(n - 1, iterations) and is_prime(n + 1, iterations)
    if not (naive_prime_test(n - 1) and naive_prime_test(n + 1)):
        raise Exception(f"{n - 1}: {naive_prime_test(n - 1)}, {n + 1}: {naive_prime_test(n + 1)}")
    assert n + 1 < 2 ** m
    # print(f"{bin(2**m -1)[2:]}\n{bin(n-1)[2:]}\n{bin(n+1)[2:]}")
    return n - 1, n + 1

def bit_range(m):
    return 2 ** (m - 1), 2 ** m

def main():
    assert len(sys.argv) >= 2
    twin = generate_twin_prime(int(sys.argv[1]))
    write_twin(twin)
    print(twin)


def write_twin(twin):
    with open("output_twin_prime.txt", "w") as file:
        file.write(f"{twin[0]}\n{twin[1]}")


for i in range(3, 32):
    print(i)
    generate_twin_prime(i)

if __name__ == "__main__":
    main()