Erdős Problem #406
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, base representations.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
Write a positive integer in base \(3\), so that its digits are \(0\), \(1\), or \(2\). Problem 406 asks whether only finitely many powers \(2^n\) avoid the digit \(2\) altogether. Equivalently, is the set
finite? The wording concerns the exponents, not merely the numerical size of the powers. The first examples are \(2^0=1\), \(2^2=4=(11)_3\), and \(2^8=256=(100111)_3\). The conjectural stronger statement is that these are the only examples, but finiteness alone would still allow additional examples.
This is Erdős’s question about ternary expansions of powers of two. It is a digit-restriction problem with an elementary statement but difficult global behavior: increasing \(n\) makes the number of ternary digits grow, while the digits are constrained by the multiplicative sequence \(2^n\).
A small example
The third listed example can be checked without approximation:
so the ternary expansion is \((100111)_3\). I also ran this exact-integer check for every \(n\) from \(0\) through \(16\):
def ternary(n):
digits = []
while n:
n, r = divmod(n, 3)
digits.append(str(r))
return ''.join(reversed(digits)) or '0'
good = [n for n in range(17)
if set(ternary(2**n)) <= {'0', '1'}]
print(good)
The output was [0, 2, 8]; the same run printed \(2^8=256\), 100111, and verified the displayed sum. This is a reproducible finite calculation, not an argument about all exponents: it checks only the explicitly bounded range \(0\leq n\leq16\) and cannot exclude a later example.
There is a related variant in which the allowed digits are \(1\) and \(2\). The exact check gives exponents \(0,1,2,3,4,15\) through \(16\), matching the reported candidate \(2^{15}\) as the largest such power in the small range. The variant must not be confused with Problem 406, whose allowed digits are \(0\) and \(1\).
What is known
The maintained Erdős Problems entry records the question as open. It reports that Gupta’s earlier search found no further \(0\)–\(1\) ternary powers through exponent \(4373\), and that later computation extended the range. Robert Saye’s primary paper, On two conjectures concerning the ternary digits of powers of two (Journal of Integer Sequences 25 (2022), Article 22.3.4, pp. 1–9), gives the clearest recent finite result. Its Lemma 1 describes the period \(u_k=2\cdot3^{k-1}\) of powers of \(2\) modulo \(3^k\) and a recursion that controls the next ternary digit. Section 4 reports a computation testing the Erdős and Sloane digit conjectures for every exponent through
No counterexample was found in that finite range. Saye’s result is computational evidence, not a proof that the set of exceptional exponents is finite.
There is also a genuine analytic counting result. Narkiewicz proved the bound \(N(x)\leq1.62x^{\log_3 2}\) for the number \(N(x)\) of exponents \(n\leq x\) whose ternary expansion of \(2^n\) omits \(2\). Jeffrey Lagarias’s primary paper Ternary expansions of powers of 2 (Journal of the London Mathematical Society 79 (2009), 562–588) states this history and proves a broader 3-adic analogue in Theorem 1.4. A sublinear upper bound still permits infinitely many such exponents, so it does not settle Problem 406.
GCL's current state
The frozen catalogue source is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, with the entry’s Git blob 4e60263a80af6207aca494d2e1388e44fa372889. At that revision the entry says open, gives no prize, marks the statement as formalized, and dates the update to 2025-08-31. The live page was edited 13 April 2026; it still presents the question, reports five discussion comments, and reports zero proof expositions and zero proof claims. Those page signals do not replace the original papers or the V2 coverage ledger.
The pinned Formal Conjectures file is google-deepmind/formal-conjectures commit 85f863718beeec7b58a3a1926ee92e3472bc2020, blob a582ccfc9d3482c3c1583ca3c807c62101994ab0. Its main declaration has no extra mathematical hypothesis beyond natural-number membership in the set and states an answer(sorry) equivalence with finiteness. A second IsGreatest declaration records the \(1\)–\(2\) digit variant. Both proofs end in sorry. Thus the file is a formal statement interface, not a checked proof, and its quantifiers and list-based digit predicate still require semantic review against the primary wording.
What remains
The central unresolved task is a proof or disproof of finiteness, not merely a larger search. A bounded successor could take an exact exponent ceiling \(B\), reproduce Saye’s residue recursion modulo the required powers of \(3\), and emit the complete list of candidate exponents up to \(B\) together with independently checkable integer identities. Acceptance would require exact arithmetic, a stated convention for \(n=0\), and a certificate that every recursion branch covering \(0\leq n\leq B\) was visited. A found exponent outside \(0,2,8\) would falsify the “only three examples” strengthening, but would not by itself disprove finiteness. Failure to find one would establish only the bounded claim.
Before any formal proof work, the natural prerequisite is a line-by-line semantic comparison of \(Nat.digits 3 n \subseteq [0, 1]\) with the source definition of a base-three expansion, including the treatment of zero and the exponent convention. No Lean replay or mathematical certification is supplied here.
Sources and claim boundaries
The assignment record is MATH-PROGRAMME issue #1676. The maintained entry is Erdős Problem 406. Primary sources read for this article are Saye’s 2022 paper and Lagarias’s 2009 paper; the historical references are Erdős, Some unconventional problems in number theory, Math. Mag. 52 (1979), pp. 67–70, and Erdős–Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), p. 80.
The frozen catalogue file is pinned here, and the pinned formal file is pinned here. The original SOURCE RESULT/1 citation is authenticated original RESULT/1. V2 ledger coverage, not this article, decides accepted GCL coverage. The finite calculation above is local evidence only; it is neither an external proof nor GCL mathematical certification.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1676 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.