Number of distinct primes dividing the product of the first $n$ partition numbers (Erdős #1106)
Statement
Let $p(k)$ denote the partition function (the number of ways of writing $k$ as a sum of positive integers, without regard to order), and let $F(n)$ be the number of distinct primes dividing the product $$\prod_{1\leq k\leq n}p(k).$$ Does $F(n)\to\infty$ as $n\to\infty$? More strongly, is $F(n)>n$ for all sufficiently large $n$?
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable in Lean preferred, otherwise a full written proof) that $F(n)>n$ for all sufficiently large $n$, or a proof that $F(n)\leq n$ for infinitely many $n$ (note the weaker $F(n)\to\infty$ is already known and does not count). ADVANCES: a proof strictly improving the best stated lower bound $F(n)\gg\log n$ (Schinzel–Wirsing) toward $n$ — state the current record in words and require a strictly larger order of growth, with proof; or an extended, reproducibly computed table of $F(n)$ (extending OEIS A194259/A194260) over a new verified range, with certified factorizations, demonstrating $F(n)>n$ throughout, plus the program. Deliver the proof or the improved lower bound / computed table with code.
Background
Asked by Erdős at Oberwolfach in 1986 [Ob1]. The weaker claim $F(n)\to\infty$ is essentially settled: Schinzel noted in the Oberwolfach problem book that it follows from the Hardy–Ramanujan asymptotic for $p(n)$ combined with a result of Tijdeman [Ti73], with details supplied in a paper of Erdős and Ivić [ErIv90, p.69]. Quantitatively, Schinzel and Wirsing [ScWi87] proved $F(n)\gg\log n$. Ono [On00] proved that every prime divides $p(n)$ for some $n\geq 1$ (indeed, for any fixed prime, for a positive-density set of $n$). The substantive open part is therefore the strong lower bound: is $F(n)>n$ for all large $n$? Related sequences OEIS A194259 and A194260. A Lean formalisation of the statement exists in the DeepMind formal-conjectures repository. Listed as open on erdosproblems.com/1106 (fetched 2026-07-21, status 'open'). Attacker's tool: compute $p(k)$ rapidly via the pentagonal-number recurrence (or Rademacher's formula), factor the running product incrementally, and tabulate $F(n)$ to extend OEIS A194259/A194260 and test $F(n)$ against $n$; on the theory side, push the Schinzel–Wirsing $\log n$ lower bound toward $n$ using prime-factor counts of $p(n)$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1106 (T. F. Bloom) | website |
| REF-02 | OEIS A194259 | website |
| REF-03 | OEIS A194260 | website |
| REF-04 | Lean formalisation (DeepMind formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.