Density of non-representable sums of $p^kq^l$ with no divisibility, for $\{p,q\}\neq\{2,3\}$ (Erdős #1110)
Statement
Let $p>q\geq 2$ be coprime integers. Call an integer $n$ representable if it is a sum of distinct integers of the form $p^k q^l$ (with $k,l\geq 0$), none of which divides any other. When $\{p,q\}=\{2,3\}$ only finitely many integers are non-representable. For all other coprime pairs $\{p,q\}\neq\{2,3\}$: what can be said about the density of the non-representable numbers? Are there infinitely many non-representable numbers coprime to $pq$?
Acceptance. FULLY RESOLVES: a complete proof determining, for all coprime pairs $\{p,q\}\neq\{2,3\}$, the density of the non-representable numbers (e.g. that the representable numbers have density zero in the cases not yet covered) AND settling whether there are infinitely many non-representable numbers coprime to $pq$ in the cases Yu–Chen left open — full rigorous written proof (Lean welcome). ADVANCES (each independently checkable): settle one specific case not covered by Yu–Chen — e.g. prove there are infinitely many coprime non-representable numbers for a pair with $q=2,p\in\{5,9\}$ or with $\{p,q\}=\{3,5\}$, or prove density zero for such a pair — with proof; or, for a stated $(p,q)$, exhibit an explicit infinite family of coprime non-representable numbers, or a certified computational census of them up to a record bound produced with reproducible code. Deliver the proof, or the enumeration code plus its certified data.
Background
A problem of Erdős and Lewin [ErLe96], who proved that there are only finitely many non-representable numbers if and only if $\{p,q\}=\{2,3\}$; listed as open on erdosproblems.com/1110 (fetched 2026-07-21, status 'open'). In [Er92b] Erdős recounted his 'silly conjecture' that every integer is a sum of distinct integers $2^k3^l$ with none dividing another, and noted that Jansen and others found a simple inductive proof (prove the stronger statement that if $n$ is even the summands can all be taken even; reduce odd $n$ via the largest power of $3$ below it). Yu and Chen [YuCh22] proved that the representable numbers have density zero whenever $q>3$, or $q=3$ and $p>6$, or $q=2$ and $p>10$; and that there are infinitely many coprime non-representable numbers whenever $q>3$, or $q=3$ and $p\neq 5$, or $q=2$ and $p\notin\{3,5,9\}$ — leaving small cases such as $\{3,5\}$, $\{2,5\}$, $\{2,9\}$ open. In a related direction, Erdős–Lewin asked for the fastest-growing $f(n)\to\infty$ such that all large $n$ are sums of $2^k3^l$ each exceeding $f(n)$, none dividing another; Yu–Chen gave $n/(\log n)^{\log_2 3}\ll f(n)\ll n/\log n$, Yang and Zhao [YaZh25] improved the lower bound to $f(n)\gg n/\log n$, and van Doorn observed that Blecksmith, McCallum, and Selfridge [BMS98] already imply $f(n)\sim \frac{\log 2\log 3}{2}\frac{n}{\log n}$. Related Erdős problems: the three-power case #123, the $\{2,3\}$ case #845, and the divisibility-free version #246. Attacker's tool: for a fixed small pair $(p,q)$, enumerate representable numbers via dynamic programming over antichains of $\{p^kq^l\}$, estimate the density empirically, and search the specific cases left open by Yu–Chen for coprime non-representable numbers.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1110 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.