"""
Trial division for candidate Mersenne exponents.
For 2^p - 1, all factors must satisfy:
  q = 2kp + 1   (Mersenne factor theorem)
  q ≡ ±1 (mod 8)

Runs until a factor is found or time limit is reached.
Usage: python trial_div_candidates.py [hours]
Default: 6 hours total split across 3 candidates.
"""

import time, math, sys

CANDIDATES = [22514117, 22510841, 22514533]

def trial_div(p, seconds, start_k=1):
    deadline = time.time() + seconds
    k = start_k - 1
    count = 0
    t_last = time.time()
    while True:
        k += 1
        q = 2 * k * p + 1
        r = q % 8
        if r == 1 or r == 7:
            if pow(2, p, q) == 1:
                return q, k, count
            count += 1
            # Progress every 5M candidates
            if count % 5_000_000 == 0:
                elapsed = time.time() - (deadline - seconds)
                rate = count / elapsed
                q_now = 2 * k * p + 1
                print(f"   [{elapsed/3600:.2f}h]  tested {count/1e6:.1f}M  q=10^{math.log10(q_now):.2f}  rate={rate/1e6:.2f}M/s", flush=True)
        if time.time() >= deadline:
            return None, k, count

def main():
    hours = float(sys.argv[1]) if len(sys.argv) > 1 else 6.0
    seconds_each = hours * 3600 / len(CANDIDATES)
    print(f"Running {hours:.1f}h total ({seconds_each/3600:.2f}h per candidate)")
    print(f"Expected reach: ~10^{math.log10(2 * (192000 * seconds_each) * CANDIDATES[0] + 1):.1f} per candidate\n")

    for p in CANDIDATES:
        print(f"=== p={p:,}  (2^p-1 has {int(p*math.log10(2))+1:,} digits) ===")
        start = time.time()
        factor, k_max, tested = trial_div(p, seconds_each)
        elapsed = time.time() - start
        q_max = 2 * k_max * p + 1
        if factor:
            print(f"  *** FACTOR FOUND: {factor} ***")
            print(f"  2^{p}-1 is COMPOSITE (factor={factor})")
        else:
            print(f"  No factor found up to q=10^{math.log10(q_max):.2f} ({q_max:,})")
            print(f"  Tested {tested/1e6:.2f}M candidates in {elapsed/3600:.2f}h")
        print()

    print("Summary: no factors found = inconclusive (need Lucas-Lehmer for proof)")
    print("Check https://mersenne.org to see if these exponents are already tested.")

if __name__ == "__main__":
    main()
