Powers of 2 with only digits 0 and 1 in base 3: are there finitely many? (Erdős #406)
Statement
Is it true that there are only finitely many powers of $2$ which have only the digits $0$ and $1$ when written in base $3$? The only known examples are $2^0=1$, $2^2=4=(11)_3$, and $2^8=256=(100111)_3$, i.e. $256=1+3+3^2+3^5$. (In the companion variant allowing only the digits $1$ and $2$, the largest known such power of $2$ is $2^{15}$.)
Acceptance. FULLY RESOLVES: a proof that only finitely many powers of $2$ have only the digits $0$ and $1$ in base $3$ (ideally effective, identifying all examples), OR a proof that infinitely many such powers exist. Machine-checkable proof (Lean/Coq) preferred; otherwise a complete written proof with all steps. A finite computation alone cannot close the finiteness question. ADVANCES: (a) extend the verified statement 'every $2^n$ with $16\le n\le N$ contains a ternary digit $2$' to an $N$ strictly beyond the best bound stated in the background, with the search program and a reproducible exhaustiveness certificate; (b) exhibit a new power of $2$ whose base-3 expansion uses only digits $0$ and $1$ — a fully machine-checkable witness (give the exponent $n$ and the ternary expansion); (c) improve Narkiewicz's counting bound $N(x)\le 1.62\,x^{\log_3 2}$ (smaller exponent or constant) with proof; or (d) a Lean formalisation of a known partial result (e.g. the counting bound). Deliver the proof file, or the search code plus attained bound and certificate, or the witness exponent with its verified ternary expansion.
Background
Posed by Erdős [Er79, p.67] and repeated in Erdős–Graham [ErGr80, p.80]; listed as open on erdosproblems.com/406 (fetched 2026-07-13, status 'open', tagged 'number theory | base representations') and mentioned as problem B33 of Guy's collection [Gu04]. The expected answer is yes, with $2^8=256$ the last example. A positive answer would imply, via Kummer's carry criterion, that $3\mid\binom{2^{k+1}}{2^k}$ for all sufficiently large $k$. The computational frontier: Saye [Sa22] verified that $2^n$ contains every possible ternary digit (in particular a digit $2$) for all $16\le n\le 5.9\times 10^{21}$. On the counting side, Narkiewicz [Na80] proved $N(x)\le 1.62\,x^{\log_3 2}$, where $N(x)$ counts the $n\le x$ for which $2^n$ has only ternary digits $0$ and $1$. Generalisations to other bases and digit sets appear in [La09] and [AbLa14]. The statement is formalised in Lean in the google-deepmind/formal-conjectures repository. Thematically close to the venue problem on whether infinitely many $\binom{2n}{n}$ are coprime to $105$ (Erdős #376), which likewise reduces to base-$p$ digit conditions on $n$, but the present question concerns the ternary digits of $2^n$ itself and is distinct. The attacker's tool: a high-throughput ternary-digit sieve on $2^n$ (tracking $2^n \bmod 3^k$ to rule out digit-$2$-free windows) to push Saye's verified range, plus Lean formalisation of the known partial results.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #406 (T. F. Bloom) | website |
| REF-02 | Formalised statement of Erdős #406 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.