Erdős #18 — practical numbers: how few divisors suffice?

Statement

Call $m$ *practical* if every integer $1\leq n<m$ is the sum of distinct divisors of $m$. If $m$ is practical, let $h(m)$ be the least number such that every $n<m$ can be written as a sum of at most $h(m)$ distinct divisors of $m$.

Three related questions are posed: 1. (the \$250 question) Are there infinitely many practical $m$ such that $$h(m) < (\log\log m)^{O(1)}?$$ 2. Is it true that $h(n!) < n^{o(1)}$? 3. Or perhaps even $h(n!) < (\log n)^{O(1)}$?

(Per the forum clarification history on erdosproblems.com/18 — comments by Woett, Dogmachine, Thomas Bloom, Feb/Oct/Dec 2025–Feb 2026 — the site now attaches the \$250 prize specifically to question 1, "for a proof or disproof of whether $h(n)<(\log\log n)^{O(1)}$ for infinitely many practical $n$"; questions 2–3 about $h(n!)$ specifically are separate, unpriced sub-questions Erdős also raised.)

Facts

- Prize \$250; status open (erdosproblems.com/18, reflects site-owner belief as of last edit 11 Apr 2026). - Falsifiable: no — this is an infinitude/asymptotic statement, needs a genuine proof or disproof, not a finite counterexample (a single practical $m$ with small $h(m)$ does not resolve "infinitely many"). - Origin: Erdős, [Er74b], [Er79], [ErGr80] ("Old and New Problems and Results in Combinatorial Number Theory", §Egyptian fractions/practical numbers), [Er81h, p.172] (source of the \$250 reward), [Er95], [Er96b], [Er98]. - Almost all integers are not practical (erdosproblems.com/18, stated without further citation). - Erdős's own original bound: $h(n!) < n$ (trivial-strength, linear). - Best known nontrivial bound: M. Vose, "Egyptian fractions", Bull. London Math. Soc. 17 (1985), 21–24 [Vo85] — proved there exist infinitely many practical $m$ with $$h(m) \ll (\log m)^{1/2}.$$ This is the record cited on erdosproblems.com/18 and is the bound Erdős's \$250 conjecture ($(\log\log m)^{O(1)}$) is trying to beat — an exponentially stronger claim (double-log vs. single-log-to-the-1/2). No source found that improves this *order* since 1985 (see Literature state). - A closely related but distinct explicit-sequence result: Hisashi Yokota, "On a Sum of Divisors", Canad. Math. Bull. 35(3) (1992), 423–430, sharpens Vose's earlier work on $l(N,r)$ (= min number of distinct divisors of $N$ summing to $r$) / $l(N)=\max_r l(N,r)$ for "Vose's sequence" $\{N_k\}$ to the exact asymptotic $l(N_k)\sim\sqrt{\log N_k}$ — pins down the constant but does not change the $(\log N)^{1/2}$ order. - User-submitted (unverified, illustrative only) computed values from erdosproblems.com/forum/discuss/18 (securehedgehog999, 10 Jun 2026): $h(n!)$ for $n=3,\dots,11$ is $2,3,4,5,5,6,7,7,7$; among practical $m\leq 16384$ the largest with $h(m)=4$ is $m=180$; the minimum of $h$ over dyadic blocks $[2^j,2^{j+1})$ is $5$ for $8\le j\le 13$ (attained at $m=264,528,1050,2100,4200,9240$); $h(720720)=6$, $h(4324320)=7$. These are forum-comment claims, not peer-reviewed, but consistent with slow (sub-linear, plausibly $O(\log)$-ish) empirical growth for small $n$. - Practical numbers are exactly characterized (Stewart 1954; Sierpiński 1955): $n=p_1^{a_1}\cdots p_r^{a_r}$ ($p_1<\cdots<p_r$) is practical iff $p_i \le 1+\sigma(p_1^{a_1}\cdots p_{i-1}^{a_{i-1}})$ for all $i$ — confirmed via Molnar's "Minimalist Practical Numbers" (2026, grantmolnar.com), which cites this as [Stewart 1954, Thm 1 §3] and is itself a live research thread on the fine structure of divisor-sum representations of practical numbers (proves: a practical number has a *unique* subset-of-divisors representation for every $m<n$ iff $n$ is a power of $2$). - The sequence of practical numbers is OEIS A005153. - Formalized in Lean: yes — google-deepmind/formal-conjectures/FormalConjectures/ErdosProblems/18.lean defines practicalH exactly as $h(m)$ above and proves small worked examples ($h(1)=1,h(2)=1,h(6)=2$, etc.) via decide/Finset machinery, but the actual conjecture is not proved (no sorry-free statement of the open bound found). - Related problems: erdos/304, erdos/825 (both cited as "See also" on erdosproblems.com/18).

Literature state

Not resolved anywhere found. This is a genuinely open, 50-year-old problem (Erdős's earliest cited reference is 1974) with essentially no order-of-magnitude progress since Vose's 1985 bound $h(m)\ll(\log m)^{1/2}$ for an explicit infinite sequence: - Direct literature search (arXiv, OpenAlex, Google Scholar via WebSearch, Semantic Scholar snippets) for "practical number" + "h(m)"/"l(N,r)"/subset-sum-of-divisors turns up a cluster of *adjacent* but not overlapping papers: Weingartner (arXiv:1405.2585, density of practical numbers of polynomial form), Pomerance–Weingartner (arXiv:2007.11062, density/prime-shift results, an "essentially proves Margenstern's conjecture" density paper), Somu–Li–Kukla (arXiv:2212.03673, abstract only inspected), Molnar 2026 (uniqueness of the representation, a genuinely new but *different* question — proves minimalist ⟺ power of 2). None of these, as far as could be verified by reading full text (Weingartner) or abstract (the rest), touch the $h(m)$ efficiency bound. - Pollack–Pomerance's survey "Some problems of Erdős on the sum-of-divisors function" (TransAMS Ser. B, 2016, full text read) is the closest-titled candidate for a resolution/survey and was read in full — it does not discuss $h(m)$, Vose's bound, or this problem at all; it covers aliquot reversals, nonaliquot density, and friendly $k$-sets instead. This effectively rules out the most likely single survey source of a resolution. - No AI system is credited with any contribution to problem #18 in Terence Tao's community-maintained "AI contributions to Erdős problems" wiki (github.com/teorth/erdosproblems/wiki, checked in full, as of the page's stated last-update near 30 Jun 2026) — the problem does not appear in any of the wiki's categories (standalone, alongside-literature, building-on-literature, human-collaboration, literature-search, formalization). - The Lean formalization (google-deepmind/formal-conjectures) states the *definition* $h(m)$ precisely and machine-verifies small cases, but records no proof of either direction of the open bound — consistent with genuine open status. - The forum comment history (6 comments, all read) is entirely about *disambiguating the statement* (is the \$250 about $h(m)$ for general practical $m$, or about $h(n!)$? — resolved: it's about $h(m)$, general practical $m$) and contains no claimed partial results, only one user-submitted numerical table (small-$n$ values of $h(n!)$ and small examples of $h$, unverified/illustrative). - Conclusion: the problem is open in the literature as well as on the site; the state of the art is still Vose 1985 (order $(\log m)^{1/2}$, constant sharpened by Yokota 1992) against Erdős's target of $(\log\log m)^{O(1)}$ — an unclosed and, as far as this search found, *untouched* gap for four decades.

Attack surface

- Mode: derivation (constructive number theory) with a small finite-search side-channel for data/intuition; not literature-resolution (nothing to recombine — see above) and not directly finite-refutable (the core claim is an infinitude statement). - Concrete first experiment: (1) Reproduce Vose's construction computationally. Vose builds practical $m_k$ via the greedy Stewart–Sierpiński condition $p_i\le 1+\sigma(p_1^{a_1}\cdots p_{i-1}^{a_{i-1}})$, then represents every $n<m_k$ by a greedy/DP algorithm over the divisors; implement this explicitly (the DP is the same one used by the forum commenter: for each $M$, h[M] = max over 1≤k<M of min #divisors of M summing to k, computable exactly for $M$ up to $\sim10^7$–$10^8$ by meet-in-the-middle or subset-sum DP) and empirically chart $h(m_k)$ vs. $(\log m_k)^{1/2}$ vs. $(\log\log m_k)^C$ for the largest reachable $k$, to see how far from Erdős's target the *actual* constant is and whether any structural pattern (e.g. specific families of highly divisible/superior-highly-composite-like practical numbers) beats $(\log m)^{1/2}$ in practice. (2) In parallel, since $h(m)$-with-divisors-restricted-to-$m$ is literally an Egyptian-fraction problem with denominators forced to divide $m$ ($n=\sum_{d\in D} d,\ D\subseteq\mathrm{div}(m)$ $\Leftrightarrow$ $n/m=\sum_{d\in D}1/(m/d)$, a sum of distinct unit fractions with denominators among $m$'s co-divisors), directly port any complete/greedy-Egyptian-fraction algorithm from the Erdős #304 literature (unrestricted-denominator Egyptian fractions, also conjectured $\ll\log\log b$) and check whether the *divisor-restriction* actually costs anything asymptotically, or whether a #304-style construction can be adapted, since both problems conjecture the *same* $\log\log$-type bound. - Oracle: mechanical for the finite/computational side — $h(m)$ is exactly computable by DP/ILP for any concrete $m$ (verify: enumerate divisors of $m$, check every $n<m$ is a subset sum, record the minimum cardinality per $n$, take the max); NOT mechanical for the actual open claim, which needs a genuine existence/impossibility proof for an infinite family. - Feasibility: honest read — famous-flavored but under-worked, not famous-hard. Unlike Erdős #1 (attacked continuously by top researchers since 1931 with a moving frontier), problem #18 shows a 40-year stall at Vose 1985 with apparently zero subsequent attempts at the specific $h(m)$ efficiency question (adjacent "practical numbers" research — Weingartner, Pomerance–Weingartner, Molnar, Somu–Li–Kukla — has moved to density/structure/uniqueness questions, not this one). This is exactly the profile of a problem that could be crackable by a fresh derivation attempt (greedy/complete-sequence + explicit construction, akin to superior/colossally-abundant-number constructions used for practical-number density results) rather than one requiring new deep machinery — but also carries real risk that the $40$-year stall reflects a genuine obstruction (the double-log target may simply be too strong; matching or beating $(\log m)^{1/2}$ with a qualitatively different exponent, e.g. $(\log m)^{1/3}$, would already be new and publishable, and is a more realistic intermediate target than jumping straight to $(\log\log m)^{O(1)}$).

Related

- erdos/304 — Egyptian-fraction complexity $N(a,b)$ (min terms in $a/b=\sum 1/n_i$, unrestricted $n_i$), also conjectured $N(b)\ll\log\log b$ [ErGr80,p.37] — the *unrestricted-denominator* twin of this *divisor-restricted* problem; same conjectured bound shape, most natural technique-transfer target. - erdos/825 — weird numbers / abundancy index: is there $C$ with every $n$, $\sigma(n)>Cn$, a distinct sum of *proper* divisors of $n$? Same underlying object (distinct-divisor-subset-sum representability), but an *existence* question rather than an *efficiency* one; shares the Benkoski–Erdős [BeEr74] / [Er74b] origin cluster. - concept/practical-numbers — the base object; Stewart–Sierpiński structure theorem, OEIS A005153, density $\sim cx/\log x$ (Saias, Weingartner). - concept/complete-sequences — the general theory of integer sequences $u_1\le u_2\le\cdots$ with $u_{i+1}\le 1+\sum_{j\le i}u_j$ (every integer up to the total is a subset sum); practical numbers are exactly the case where the sequence is the divisor list of a fixed $m$, so complete-sequence machinery (postage-stamp-problem style) plausibly transfers. - concept/egyptian-fractions — Vose's own specialty (Bull. LMS 1985 paper is literally titled "Egyptian fractions"); the divisor-sum representation of $n<m$ is exactly a unit-fraction representation of $n/m$ with denominators restricted to co-divisors of $m$. - concept/greedy-divisor-representation — the DP/greedy algorithm (used both by Vose's construction and by the forum's exact-$h$ computation) that is the natural finite-search/verification oracle for this problem. - concept/sum-of-divisors-function — $\sigma(n)$, central to the Stewart–Sierpiński practicality criterion and to essentially all adjacent literature (Weingartner, Pomerance–Weingartner, Molnar).