Practical numbers with tiny representations: is $h(m)<(\log\log m)^{O(1)}$ infinitely often? (Erdős #18)
Statement
Call $m$ practical if every integer $1\leq n<m$ is a sum of distinct divisors of $m$. For practical $m$, let $h(m)$ be the least $k$ such that every integer $1\leq n<m$ is a sum of at most $k$ distinct divisors of $m$. Are there infinitely many practical $m$ such that $$h(m)<(\log\log m)^{O(1)}?$$ Is it true that $h(n!)<n^{o(1)}$? Or perhaps even $h(n!)<(\log n)^{O(1)}$?
Acceptance. FULLY RESOLVES: a proof that there are infinitely many practical $m$ with $h(m)\leq(\log\log m)^{C}$ for some absolute constant $C$ (this is the $250 question), or a proof that no such infinite family exists; and/or a proof or disproof of $h(n!)<n^{o(1)}$ (or the stronger $h(n!)<(\log n)^{O(1)}$). Machine-checkable (Lean/Coq) preferred, else a complete written proof. ADVANCES: (a) an infinite family of practical $m$ with $h(m)$ of strictly smaller order than the $(\log m)^{1/2}$ bound stated in the background, with proof; (b) an upper bound for $h(n!)$ asymptotically better than the $h(n!)<n$ bound stated in the background, with proof; (c) a nontrivial general lower bound on $h(m)$ for practical $m$, with proof; (d) exact values of $h(m)$ for all practical $m$ up to a substantial bound, or of $h(n!)$ for as many $n$ as feasible, with reproducible search code, per-value certificates (a worst-case target $n$ and an optimal representation), and an analysis of the empirical growth rate; (e) a Lean formalization of Vose's theorem. Deliver the proof file, or the code + certified value tables.
Background
Raised by Erdős repeatedly [Er74b], [Er79], [ErGr80], [Er81h, p.172], [Er95], [Er96b], [Er98]; listed as open on erdosproblems.com/18 (fetched 2026-07-21, status 'open', tagged 'number theory | divisors | factorials'). Erdős offered $250 in [Er81h] for a proof or disproof of the first question (infinitely many practical $n$ with $h(n)<(\log\log n)^{O(1)}$). Known frontier: almost all integers are not practical; Erdős originally showed $h(n!)<n$; the best general result is Vose [Vo85], who proved there exist infinitely many practical $m$ with $h(m)\ll(\log m)^{1/2}$. The practical numbers are OEIS A005153 (their distribution is well understood: Weingartner proved they have density $\sim c\,x/\log x$, echoing the primes, though that is about membership, not $h$). A formalized statement exists in the DeepMind formal-conjectures repository (FormalConjectures/ErdosProblems/18.lean). Related site problems: Erdős #304 (erdosproblems.com/304) and Erdős #825 (erdosproblems.com/825). The attacker's tools: exact computation of $h(m)$ for structured practical $m$ (primorials, factorials, highly composite numbers) via subset-sum/greedy certification over the divisor multiset, mapping the empirical growth of $\min h(m)$ and $h(n!)$; and constructive divisor-system designs (binary-like chains of divisors) aiming below Vose's $(\log m)^{1/2}$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #18 (T. F. Bloom) | website |
| REF-02 | OEIS A005153 — practical numbers: every k <= sigma(m) is a sum of distinct divisors of m | website |
| REF-03 | Formalized statement of Erdős #18 (DeepMind formal-conjectures, Lean) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.