Erdős Problem #18
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, divisors, factorials.
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
A positive integer \(n\) is practical when every smaller positive integer can be expressed as a sum of distinct positive divisors of \(n\). Let \(h(n)\) be the largest, over target integers \(1\le m\le n\), of the smallest number of divisors needed in such a representation. Erdős Problem #18 asks several related questions about finding practical numbers with surprisingly small \(h(n)\), including growth conditions involving factorials.
The original statement uses \(m<n\) rather than \(m\le n\). For practical \(n\ge2\) these produce the same maximum because the extra target \(n\) is represented by the single divisor \(n\); the boundary \(n=1\) must be treated separately.
A small example
Take \(n=8\), whose positive divisors are \(1,2,4,8\). Every integer from 1 through 7 has a binary expansion into distinct divisors. However, \(7=1+2+4\) needs three summands, and no two of these divisors sum to 7. Thus \(h(8)=3\).
More generally, for every integer \(k\ge1\),
The binary representation supplies the upper bound, and the target \(2^k-1\) requires all \(k\) smaller powers of two. The endpoint \(h(1)=1\) is a separate exception to the displayed formula with \(k=0\).
What is known
The external registry separates three unresolved questions, including an eventual subpolynomial estimate for \(h(n!)\) and a sharper polylogarithmic form. It reports earlier bounds credited to Erdős and a theorem of Vose giving infinitely many practical integers with a square-root-logarithmic upper bound for \(h(n)\). Those published claims are source-reported in the audit; their entire original analytic proofs were not independently replayed.
GCL's current state
GCL's source audit directly checked the frozen practical-number and maximal-length definitions and reproduced \(h(2^k)\) for \(0\le k\le10\) with a distinct-summand subset-sum program. It identified that all three formal problem statements still have unfilled proofs and that a finite binary example does not resolve the growth questions.
What remains
The central gap is between elementary representation lengths for powers of two and uniform efficient representations by divisors of much more complicated numbers, particularly factorials. Formalizing the exact binary lemma is useful mathematical infrastructure, but proving any global factorial bound needs additional arguments.
Sources and claim boundaries
- Erdős Problems #18: distinct conjectural variants and dated status.
- Vose (1985), Egyptian Fractions, Bulletin of the London Mathematical Society 17, 21–24; theorem reported, not independently replayed here.
- GCL audit #1287: exact power-of-two calculation and quantifier boundaries, not a proof of the open questions.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1287 — 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.