Erdős Problem #1106

Erdős Problem 1106 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/1106

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/1106.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/1106.tex.

FORMAL RESTATEMENT. Let $p(n)$ denote the partition function of $n$ (number of integer partitions of $n$), with $p(0)=1$ and $p(n)\in\mathbb N$ for $n\ge 1$. For $n\ge 1$ define \[P(n):=\prod_{k=1}^n p(k),\qquad F(n):=\omega(P(n)), \] where $\omega(N)$ is the number of distinct prime divisors of a positive integer $N$. Questions:

• Does $F(n)\to\infty$ as $n\to\infty$?
• Is $F(n)>n$ for all sufficiently large $n$?

QUICK LITERATURE/CONTEXT CHECK (from the problem file only). The text reports: (i) Schinzel observed (Oberwolfach problem book) that $F(n)\to\infty$ follows from the asymptotic for $p(n)$ and a theorem of Tijdeman; details in Erdős--Ivić $1990$. (ii) Schinzel--Wirsing proved $F(n)\gg \log n$. (iii) Ono proved that every prime divides $p(n)$ for some $n\ge 1$ (indeed for a positive density of $n$ for each fixed prime). I do not reprove any of these external statements.

ATTACK PLAN.

• Prove basic structural facts about $F(n)$ (monotonicity) and give a clean conditional implication from (iii) to $F(n)\to\infty$.
• Provide computational sanity checks for $F(n)$ for moderate $n$.

WORK.

Lemma 1 (monotonicity). The function $F(n)$ is nondecreasing in $n$.

Proof. We have $P(n+1)=P(n)\,p(n+1)$. Thus the set of prime divisors of $P(n+1)$ is the union of the set of prime divisors of $P(n)$ with those of $p(n+1)$. In particular it contains the prime divisors of $P(n)$, so $\omega(P(n+1))\ge \omega(P(n))$, i.e. $F(n+1)\ge F(n)$. $\square$

Lemma 2 (conditional: Ono-type statement $\Rightarrow F(n)\to\infty$). Assume the following statement:

For every prime $q$ there exists an integer $m(q)\ge 1$ such that $q\mid p(m(q))$.

Then $F(n)\to\infty$.

Proof. Fix $y\ge 2$ and let $\mathcal P(y)$ be the set of primes $q\le y$. For each $q\in\mathcal P(y)$ choose $m(q)$ with $q\mid p(m(q))$. Let \[N(y):=\max\{m(q): q\le y,\ q\text{ prime}\}. \] Then for every $n\ge N(y)$ and every prime $q\le y$ we have $q\mid P(n)$ because $q\mid p(m(q))$ and $p(m(q))$ is a factor of $P(n)$. Therefore $F(n)=\omega(P(n))\ge |\mathcal P(y)|=\pi(y)$ for all $n\ge N(y)$. Since $\pi(y)\to\infty$ as $y\to\infty$, it follows that $F(n)\to\infty$ as $n\to\infty$. $\square$

FAST REALITY CHECK (computation of $F(n)$). I computed $p(k)$ for $1\le k\le n$, factored each $p(k)$, and tracked the union of prime factors. The exact values obtained include: \[ F(10)=5,\qquad F(50)=34,\qquad F(100)=96,\qquad F(200)=242,\qquad F(300)=412. \] In this computation, the first $n$ for which $F(n)>n$ was \[n=116\quad\text{with}\quad F(116)=117. \] These data strongly suggest $F(n)\to\infty$ and support the possibility that $F(n)>n$ eventually, but they are not a proof.

VERIFICATION.

• Lemma 1 is a direct set-inclusion argument on prime divisors.
• Lemma 2 is purely logical and does not use any properties of $p(n)$ beyond the assumption.
• Computation: $F(n)$ was computed as the size of the union of $\mathrm{primefactors}(p(k))$ for $k\le n$.

FINAL: UNRESOLVED. (i) Strongest proved partial result here. $F(n)$ is nondecreasing (Lemma 1). Moreover, if one assumes the statement "every prime divides some partition number" (which the problem text attributes to Ono), then $F(n)\to\infty$ follows immediately (Lemma 2).

(ii) First gap (crisp). I do not have a self-contained proof (without importing the cited deep results) that infinitely many distinct primes divide the set $\{p(1),p(2),\dots\}$, equivalently that $F(n)\to\infty$ unconditionally.

(iii) Top 3 next moves. 1. Use (and explicitly write out) the asymptotic formula for $p(n)$ together with a suitable "many small prime factors" theorem (as suggested in the problem text) to force new primes to appear in $\prod_{k\le n}p(k)$. 2. Attempt to show that for each fixed prime $q$, the congruence $p(n)\equiv 0\pmod q$ holds for infinitely many $n$ by elementary modular-form arguments (this is essentially what the text attributes to Ono). 3. Extend the computation to larger $n$ (with certified integer factorizations) to test the conjecture $F(n)>n$ and estimate growth rate.

(iv) Minimal counterexample structure. A counterexample to $F(n)\to\infty$ would require that all $p(1),p(2),\dots$ are composed of primes from a fixed finite set $S$; equivalently, $p(n)$ would be an $S$-smooth integer for all $n$, which seems incompatible with the rapid growth and varied congruence behavior of $p(n)$, but proving this incompatibility is the main obstacle.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT. Let $p(n)$ denote the partition function of $n$ (number of integer partitions of $n$), with $p(0)=1$ and $p(n)\in\mathbb N$ for $n\ge 1$. For $n\ge 1$ define \[P(n):=\prod_{k=1}^n p(k),\qquad F(n):=\omega(P(n)), \] where $\omega(N)$ is the number of distinct prime divisors of a positive integer $N$. Questions:

• Does $F(n)\to\infty$ as $n\to\infty$?
• Is $F(n)>n$ for all sufficiently large $n$?

QUICK LITERATURE/CONTEXT CHECK (from the problem file only). The text reports: (i) Schinzel observed (Oberwolfach problem book) that $F(n)\to\infty$ follows from the asymptotic for $p(n)$ and a theorem of Tijdeman; details in Erdős--Ivić $1990$. (ii) Schinzel--Wirsing proved $F(n)\gg \log n$. (iii) Ono proved that every prime divides $p(n)$ for some $n\ge 1$ (indeed for a positive density of $n$ for each fixed prime). I do not reprove any of these external statements.

ATTACK PLAN.

• Prove basic structural facts about $F(n)$ (monotonicity) and give a clean conditional implication from (iii) to $F(n)\to\infty$.
• Provide computational sanity checks for $F(n)$ for moderate $n$.

WORK.

Lemma 1 (monotonicity). The function $F(n)$ is nondecreasing in $n$.

Proof. We have $P(n+1)=P(n)\,p(n+1)$. Thus the set of prime divisors of $P(n+1)$ is the union of the set of prime divisors of $P(n)$ with those of $p(n+1)$. In particular it contains the prime divisors of $P(n)$, so $\omega(P(n+1))\ge \omega(P(n))$, i.e. $F(n+1)\ge F(n)$. $\square$

Lemma 2 (conditional: Ono-type statement $\Rightarrow F(n)\to\infty$). Assume the following statement:

For every prime $q$ there exists an integer $m(q)\ge 1$ such that $q\mid p(m(q))$.

Then $F(n)\to\infty$.

Proof. Fix $y\ge 2$ and let $\mathcal P(y)$ be the set of primes $q\le y$. For each $q\in\mathcal P(y)$ choose $m(q)$ with $q\mid p(m(q))$. Let \[N(y):=\max\{m(q): q\le y,\ q\text{ prime}\}. \] Then for every $n\ge N(y)$ and every prime $q\le y$ we have $q\mid P(n)$ because $q\mid p(m(q))$ and $p(m(q))$ is a factor of $P(n)$. Therefore $F(n)=\omega(P(n))\ge |\mathcal P(y)|=\pi(y)$ for all $n\ge N(y)$. Since $\pi(y)\to\infty$ as $y\to\infty$, it follows that $F(n)\to\infty$ as $n\to\infty$. $\square$

FAST REALITY CHECK (computation of $F(n)$). I computed $p(k)$ for $1\le k\le n$, factored each $p(k)$, and tracked the union of prime factors. The exact values obtained include: \[ F(10)=5,\qquad F(50)=34,\qquad F(100)=96,\qquad F(200)=242,\qquad F(300)=412. \] In this computation, the first $n$ for which $F(n)>n$ was \[n=116\quad\text{with}\quad F(116)=117. \] These data strongly suggest $F(n)\to\infty$ and support the possibility that $F(n)>n$ eventually, but they are not a proof.

VERIFICATION.

• Lemma 1 is a direct set-inclusion argument on prime divisors.
• Lemma 2 is purely logical and does not use any properties of $p(n)$ beyond the assumption.
• Computation: $F(n)$ was computed as the size of the union of $\mathrm{primefactors}(p(k))$ for $k\le n$.

FINAL: UNRESOLVED. (i) Strongest proved partial result here. $F(n)$ is nondecreasing (Lemma 1). Moreover, if one assumes the statement "every prime divides some partition number" (which the problem text attributes to Ono), then $F(n)\to\infty$ follows immediately (Lemma 2).

(ii) First gap (crisp). I do not have a self-contained proof (without importing the cited deep results) that infinitely many distinct primes divide the set $\{p(1),p(2),\dots\}$, equivalently that $F(n)\to\infty$ unconditionally.

(iii) Top 3 next moves. 1. Use (and explicitly write out) the asymptotic formula for $p(n)$ together with a suitable "many small prime factors" theorem (as suggested in the problem text) to force new primes to appear in $\prod_{k\le n}p(k)$. 2. Attempt to show that for each fixed prime $q$, the congruence $p(n)\equiv 0\pmod q$ holds for infinitely many $n$ by elementary modular-form arguments (this is essentially what the text attributes to Ono). 3. Extend the computation to larger $n$ (with certified integer factorizations) to test the conjecture $F(n)>n$ and estimate growth rate.

(iv) Minimal counterexample structure. A counterexample to $F(n)\to\infty$ would require that all $p(1),p(2),\dots$ are composed of primes from a fixed finite set $S$; equivalently, $p(n)$ would be an $S$-smooth integer for all $n$, which seems incompatible with the rapid growth and varied congruence behavior of $p(n)$, but proving this incompatibility is the main obstacle.