Completeness of the sequence $\lfloor t\alpha^n\rfloor$: for which $t,\alpha$ is it complete? (Erdős #349)
Statement
For what values of $t,\alpha\in(0,\infty)$ is the sequence $\lfloor t\alpha^n\rfloor$ ($n=0,1,2,\ldots$) complete — that is, for which $(t,\alpha)$ is every sufficiently large integer a sum of distinct integers of the form $\lfloor t\alpha^n\rfloor$?
Acceptance. FULLY RESOLVES: a complete characterization, with proof, of the set of pairs $(t,\alpha)\in(0,\infty)^2$ for which $\lfloor t\alpha^n\rfloor$ is complete — machine-checkable (Lean/Coq) preferred, else a full written proof. ADVANCES: a proof of completeness for all $t>0$ and all $1<\alpha<(1+\sqrt{5})/2$ (the conjectured range), or for any new explicitly described region of the $(t,\alpha)$ plane not covered by results stated in the background; a proof that $\lfloor (3/2)^n\rfloor$ is odd infinitely often (or even infinitely often); a certified construction strengthening Graham's disconnectedness phenomenon beyond what is stated in the background (an explicit $t$ whose completeness set in $\alpha$ provably contains more disjoint components than any published example, with proof); or rigorous completeness/incompleteness certificates for explicit parameter families with reproducible verification. Deliver the proof files, plus code and machine-checkable certificates for any computational claims.
Background
Posed by Erdős and Graham [ErGr80, p.57]; listed as open on erdosproblems.com/349 (fetched 2026-07-13, status 'open', tagged 'number theory | complete sequences'). Even restricted to $t\in(0,1)$ and $\alpha\in(1,2)$ the behaviour is surprisingly complex: Graham [Gr64e] proved that for every $k$ there exists $t_k\in(0,1)$ such that the set of $\alpha$ for which the sequence is complete contains at least $k$ disjoint line segments — the completeness region is badly disconnected. It is considered likely that the sequence is complete for all $t>0$ and all $1<\alpha<\frac{1+\sqrt{5}}{2}$, but a proof looks far off: it is not even known whether $\lfloor (3/2)^n\rfloor$ is odd infinitely often (nor whether it is even infinitely often), which blocks the natural approaches. The statement has been formalized in Lean in the DeepMind formal-conjectures repository. This venue hosts the nearby complete-sequences problem Erdős #347 — same subject area, distinct question. The attacker's tools: for explicit parameter values, completeness can often be certified by a finite computation plus induction (Brown-type criteria: each term at most $1$ plus the sum of all previous terms, with quantitative margins), so rigorously certifying completeness on explicit $(t,\alpha)$ families, mapping the completeness region computationally, and pushing Graham-style disconnectedness constructions further are all concrete routes.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #349 (T. F. Bloom) | website |
| REF-02 | Formalized statement of Erdős #349 (DeepMind formal-conjectures, Lean) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.