Erdős Problem #1106
Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory.
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.
UNACCEPTED DRAFT — mathematical editorial review pending
This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.
Review the underlying draft on GitHub.
The question in plain language
The partition function \(p(n)\) counts the ways to write an integer \(n\) as an unordered sum of positive integers. For example, \(p(4)=5\) because the partitions are \(4\), \(3+1\), \(2+2\), \(2+1+1\), and \(1+1+1+1\).
Erdős Problem #1106 asks how many different prime factors appear among the partition numbers \(p(1),\ldots,p(n)\). More precisely,
where \(\omega\) counts distinct primes, ignoring multiplicity.
There are two questions: must \(F(n)\) tend to infinity? And is the much stronger inequality \(F(n)>n\) eventually true?
A small example
The first ten partition numbers are
Even if a prime divides several partition numbers, it counts only once in \(F(n)\). A recurrence that counts partitions and a separate exact prime-factor sieve give
This does not contradict an eventual conjecture \(F(n)>n\): small values may fail it.
What is known
The first question has been settled affirmatively. The maintained catalogue credits Schinzel, using the Hardy–Ramanujan partition asymptotic together with a theorem of Tijdeman (1973). An explanation appears in Erdős–Ivić (1990). Schinzel and Wirsing (1987) strengthened the conclusion to
A later theorem of Ono (2000), as reported by the catalogue, says that every prime divides at least one partition number. This also implies that \(F(n)\to\infty\): any finite collection of primes has finitely many witness indices, so all those primes appear in \(F(n)\) after the largest such index.
The stronger eventual inequality \(F(n)>n\) remains open. The general page therefore retains an open classification, even though its first part has a published proof.
GCL's current state
Authenticated source audit #2377 separately records the proved first assertion and the open second. It independently verifies the exact partition counts and finite set of prime divisors through \(25\).
The frozen Lean representation still marks both theorem parts open, with unproved bodies. The mathematical status of the first part must be determined from published literature, not this stale annotation.
What remains
Read the original Tijdeman, Schinzel–Wirsing, Erdős–Ivić and Ono proofs; verify the statement of each implication; and assess later progress on the stronger \(F(n)>n\) question. Reconcile the stale formal annotation separately.
Sources and claim boundaries
Erdős Problem #1106; Tijdeman (1973), Schinzel–Wirsing (1987), Erdős–Ivić (1990), Ono (2000) as cited by the maintained catalogue; frozen formal statement; source return #2377. Published results are external, finite arithmetic independent, and the stronger assertion remains open. Unaccepted draft.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2377 — 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.