Erdős Problem #462

Erdős Problem 462 --- collection record

PROVENANCE AND STATUS

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/462.tex.

REUSED SOURCE 1

1) FORMAL RESTATEMENT

Let $p(n)$ denote the least prime factor of $n$ (so if $n$ is prime then $p(n)=n$). The extracted problem states that there exists a constant $c>0$ such that \[S(x):=\sum_{\substack{n<x\\ n\ \textrm{not prime}}}\frac{p(n)}{n}\ \sim\ c\,\frac{x^{1/2}}{(\log x)^2}. \] It then asks whether there exists a constant $C>0$ such that \[T(x):=\sum_{x\le n\le x+C x^{1/2}(\log x)^2}\frac{p(n)}{n}\ \gg\ 1\] for all sufficiently large $x$.

Ambiguity. In the second sum, primes $n$ are not explicitly excluded. If primes are included, then each prime contributes $p(n)/n=1$ and the question becomes closely related to guaranteeing primes in intervals of length $\asymp x^{1/2}(\log x)^2$ (a Legendre-type prime gap question). The reference is ambiguous about whether primes should be excluded. In what follows I focus on the corrected version consistent with the first sum: \[T_{\mathrm{comp}}(x):=\sum_{\substack{x\le n\le x+C x^{1/2}(\log x)^2\\ n\ \textrm{not prime}}}\frac{p(n)}{n},\] and ask whether $T_{\mathrm{comp}}(x)\gg 1$ for all large $x$.

2) QUICK LITERATURE/CONTEXT CHECK

The Erdős problems page for #462 explicitly notes this ambiguity and remarks that if primes are included the question is essentially a weaker form of Legendre's conjecture, while if primes are excluded it is related to the distribution of semiprimes $pq$ with $p,q\approx x^{1/2}\log^{O(1)}x$ in short intervals. I do not use any external results beyond the asymptotic stated in the problem.

3) ATTACK PLAN

• Use the decomposition by least prime factor: write each composite $n$ uniquely as $n=p\,m$ with $p=p(n)$ and deduce $p(n)/n=1/m$.
• Derive consequences of the global asymptotic for averages of the short-interval sums.
• Compute the corrected short-interval sum numerically for moderately large $x$ to sanity-check.

4) WORK

Fast reality check (computations, corrected version excluding primes).

For several values of $x\le 1.5\times 10^6$ I computed \[\sum_{\substack{x\le n\le x+ C\sqrt{x}(\log x)^2\\ n\ \mathrm{composite}}}\frac{p(n)}{n} \] with $C=1$. The observed values were about $3.73$--$4.27$ for the sample points $x\in\{10^3,5\cdot 10^3,10^4,5\cdot 10^4,10^5,5\cdot 10^5,10^6,1.5\cdot 10^6\}$.

Lemma 462.1 (trivial pointwise bound). If $n$ is composite then $p(n)\le \sqrt{n}$, and hence \[0<\frac{p(n)}{n}\le \frac1{\sqrt{n}}. \]

Proof. If $n$ is composite, write $n=ab$ with $1<a\le b<n$. Then $a\le\sqrt{n}$. The least prime factor $p(n)$ is at most $a$, so $p(n)\le\sqrt{n}$. Dividing by $n$ gives $p(n)/n\le 1/\sqrt{n}$. $\square$

Lemma 462.2 (decomposition by least prime factor). Define $a_n:=\frac{p(n)}{n}$ if $n$ is composite and $a_n:=0$ if $n$ is prime or $n=1$. Then for every $x\ge 2$, \[\sum_{n<x} a_n = \sum_{\text{primes }p}\ \sum_{\substack{m<x/p\\ m\ge 2\\ p(m)\ge p}} \frac1m. \] Here $p(m)\ge p$ means that $m$ has no prime factor $<p$.

Proof. Every composite integer $n\ge 4$ has a unique least prime factor $p=p(n)$, and can be written uniquely as $n=p m$ with $m\ge 2$. Moreover, $p(n)=p$ if and only if (i) $p$ is prime, (ii) $n=pm$, and (iii) $m$ has no prime factor smaller than $p$, i.e. $p(m)\ge p$. For such $n=pm$, one has \[a_n = \frac{p(n)}{n} = \frac{p}{pm} = \frac1m. \] Summing $a_n$ over all composite $n<x$ and grouping terms by $p=p(n)$ yields exactly the double sum on the right-hand side. $\square$

Lemma 462.3 (average short-interval mass from the global asymptotic). Assume the asymptotic stated in the problem: \[S(x):=\sum_{n<x} a_n\sim c\frac{x^{1/2}}{(\log x)^2}.\] Fix $C>0$ and define $L(x):=\lfloor C x^{1/2}(\log x)^2\rfloor$. Consider the corrected short-interval sums \[T_{\mathrm{comp}}(x):=\sum_{x\le n\le x+L(x)} a_n\quad (a_n\ge 0).\] Then as $X\to\infty$, \[\frac1{X}\sum_{x=X}^{2X} T_{\mathrm{comp}}(x)\ \ge\ cC(\sqrt{2}-1)+o(1).\] In particular, there exist arbitrarily large $x$ for which $T_{\mathrm{comp}}(x)\gg_C 1$.

Proof. Let \[L_{\min}:=\lfloor C X^{1/2}(\log X)^2\rfloor. \] For all integers $x\in[X,2X]$, monotonicity of the function $x\mapsto x^{1/2}(\log x)^2$ implies $L(x)\ge L_{\min}$ for all sufficiently large $X$. Since $a_n\ge 0$, we have \[T_{\mathrm{comp}}(x)=\sum_{x\le n\le x+L(x)} a_n\ \ge\ \sum_{x\le n\le x+L_{\min}} a_n.\] Summing this inequality over $x=X,X+1,\dots,2X$ and swapping the order of summation gives \[\sum_{x=X}^{2X} T_{\mathrm{comp}}(x)\ \ge\ \sum_{x=X}^{2X}\ \sum_{x\le n\le x+L_{\min}} a_n =\sum_{n} a_n\,\#\{x\in[X,2X]: x\le n\le x+L_{\min}\}. \] Now fix any integer $n$ with $X+L_{\min}\le n\le 2X$. For each integer $j\in\{0,1,\dots,L_{\min}-1\}$ let $x=n-j$. Then $x\in[X,2X]$ and $x+L_{\min}=n-j+L_{\min}\ge n$, so $x\le n\le x+L_{\min}$. Hence \[\#\{x\in[X,2X]: x\le n\le x+L_{\min}\}\ \ge\ L_{\min}. \] Therefore \[\sum_{x=X}^{2X} T_{\mathrm{comp}}(x)\ \ge\ L_{\min}\sum_{n=X+L_{\min}}^{2X} a_n =L_{\min}\left(S(2X+1)-S(X+L_{\min})\right). \] Because $L_{\min}=o(X)$, the asymptotic for $S$ implies \[S(2X+1)-S(X+L_{\min})\ =\ c\frac{(2X)^{1/2}}{(\log X)^2}-c\frac{X^{1/2}}{(\log X)^2}+o\!\left(\frac{X^{1/2}}{(\log X)^2}\right) = c(\sqrt{2}-1)\frac{X^{1/2}}{(\log X)^2}+o\!\left(\frac{X^{1/2}}{(\log X)^2}\right). \] Multiplying by $L_{\min}=C X^{1/2}(\log X)^2+o\left(X^{1/2}(\log X)^2\right)$ yields \[\sum_{x=X}^{2X} T_{\mathrm{comp}}(x)\ \ge\ cC(\sqrt{2}-1)X+o(X). \] Dividing by $X$ proves the claimed average lower bound. Since an average over $x\in[X,2X]$ is bounded below by a positive constant for large $X$, at least one $x\in[X,2X]$ must satisfy $T_{\mathrm{comp}}(x)\gg_C 1$; letting $X\to\infty$ gives arbitrarily large such $x$. $\square$

5) VERIFICATION

• Checked that the ambiguity about primes is real (it is also noted in the discussion thread).
• Lemma 462.2: verified uniqueness of decomposition $n=p\,m$ with $p$ least prime factor.
• Lemma 462.3: verified the lower bound on the counting multiplicity $\#\{x: x\le n\le x+L(x)\}$ uses only monotonicity of $L(x)$ on $[X,2X]$ for large $X$ and that $L(x)\gg \sqrt{X}(\log X)^2$.
• Computations: used a least-prime-factor sieve up to $2\cdot 10^6$ and prefix sums of $a_n$ (excluding primes).

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: After excluding primes (the corrected reading), we have the exact decomposition \[\sum_{n<x,\,n\ \mathrm{composite}}\frac{p(n)}{n}=\sum_{p\ \mathrm{prime}}\ \sum_{\substack{m<x/p\\ m\ge 2,\ p(m)\ge p}} \frac1m\] (Lemma 462.2), and assuming the stated global asymptotic one can prove that the short-interval sum has positive average size $\asymp cC$ over $x\in[X,2X]$ (Lemma 462.3), hence is $\gg 1$ for infinitely many $x$. Computations for $x\le 1.5\cdot 10^6$ and $C=1$ show values around $4$.

(ii) First gap (crisp): Upgrade the average lower bound to a pointwise one: prove there exists $C>0$ and $c_0>0$ such that for every sufficiently large $x$, \[\sum_{\substack{x\le n\le x+C\sqrt{x}(\log x)^2\\ n\ \mathrm{composite}}}\frac{p(n)}{n}\ge c_0. \]

(iii) Top 3 next moves:

1. Show that intervals of length $\asymp \sqrt{x}(\log x)^2$ always contain enough semiprimes $pq$ with $p,q\approx \sqrt{x}\,\log^{O(1)}x$, since such terms contribute $\approx 1/q$.
2. Prove a lower bound for the count of integers $n$ in $[x,x+\sqrt{x}(\log x)^2]$ whose least prime factor lies in a controlled range (e.g. $p(n)\approx \sqrt{x}\,\log^A x$).
3. Numerically search for $x$ where the corrected interval sum is unusually small (relative to its average) to guess the obstruction structure.

(iv) Minimal counterexample structure: A minimal counterexample (under the corrected reading) would be a large $x$ for which the interval $[x,x+C\sqrt{x}(\log x)^2]$ contains very few composites with least prime factor $\gg \sqrt{x}/\log^{O(1)}x$; heuristically this would mean the interval avoids most semiprimes $pq$ with $p,q\approx \sqrt{x}\,\log^{O(1)}x$ and is dominated by numbers with very small least prime factor (whose contributions $p(n)/n$ are tiny).

COMPLETION ESTIMATE

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

1) FORMAL RESTATEMENT

Let $p(n)$ denote the least prime factor of $n$ (so if $n$ is prime then $p(n)=n$). The extracted problem states that there exists a constant $c>0$ such that \[S(x):=\sum_{\substack{n<x\\ n\ \textrm{not prime}}}\frac{p(n)}{n}\ \sim\ c\,\frac{x^{1/2}}{(\log x)^2}. \] It then asks whether there exists a constant $C>0$ such that \[T(x):=\sum_{x\le n\le x+C x^{1/2}(\log x)^2}\frac{p(n)}{n}\ \gg\ 1\] for all sufficiently large $x$.

Ambiguity. In the second sum, primes $n$ are not explicitly excluded. If primes are included, then each prime contributes $p(n)/n=1$ and the question becomes closely related to guaranteeing primes in intervals of length $\asymp x^{1/2}(\log x)^2$ (a Legendre-type prime gap question). The reference is ambiguous about whether primes should be excluded. In what follows I focus on the corrected version consistent with the first sum: \[T_{\mathrm{comp}}(x):=\sum_{\substack{x\le n\le x+C x^{1/2}(\log x)^2\\ n\ \textrm{not prime}}}\frac{p(n)}{n},\] and ask whether $T_{\mathrm{comp}}(x)\gg 1$ for all large $x$.

2) QUICK LITERATURE/CONTEXT CHECK

The Erdős problems page for #462 explicitly notes this ambiguity and remarks that if primes are included the question is essentially a weaker form of Legendre's conjecture, while if primes are excluded it is related to the distribution of semiprimes $pq$ with $p,q\approx x^{1/2}\log^{O(1)}x$ in short intervals. I do not use any external results beyond the asymptotic stated in the problem.

3) ATTACK PLAN

• Use the decomposition by least prime factor: write each composite $n$ uniquely as $n=p\,m$ with $p=p(n)$ and deduce $p(n)/n=1/m$.
• Derive consequences of the global asymptotic for averages of the short-interval sums.
• Compute the corrected short-interval sum numerically for moderately large $x$ to sanity-check.

4) WORK

Fast reality check (computations, corrected version excluding primes).

For several values of $x\le 1.5\times 10^6$ I computed \[\sum_{\substack{x\le n\le x+ C\sqrt{x}(\log x)^2\\ n\ \mathrm{composite}}}\frac{p(n)}{n} \] with $C=1$. The observed values were about $3.73$--$4.27$ for the sample points $x\in\{10^3,5\cdot 10^3,10^4,5\cdot 10^4,10^5,5\cdot 10^5,10^6,1.5\cdot 10^6\}$.

Lemma 462.1 (trivial pointwise bound). If $n$ is composite then $p(n)\le \sqrt{n}$, and hence \[0<\frac{p(n)}{n}\le \frac1{\sqrt{n}}. \]

Proof. If $n$ is composite, write $n=ab$ with $1<a\le b<n$. Then $a\le\sqrt{n}$. The least prime factor $p(n)$ is at most $a$, so $p(n)\le\sqrt{n}$. Dividing by $n$ gives $p(n)/n\le 1/\sqrt{n}$. $\square$

Lemma 462.2 (decomposition by least prime factor). Define $a_n:=\frac{p(n)}{n}$ if $n$ is composite and $a_n:=0$ if $n$ is prime or $n=1$. Then for every $x\ge 2$, \[\sum_{n<x} a_n = \sum_{\text{primes }p}\ \sum_{\substack{m<x/p\\ m\ge 2\\ p(m)\ge p}} \frac1m. \] Here $p(m)\ge p$ means that $m$ has no prime factor $<p$.

Proof. Every composite integer $n\ge 4$ has a unique least prime factor $p=p(n)$, and can be written uniquely as $n=p m$ with $m\ge 2$. Moreover, $p(n)=p$ if and only if (i) $p$ is prime, (ii) $n=pm$, and (iii) $m$ has no prime factor smaller than $p$, i.e. $p(m)\ge p$. For such $n=pm$, one has \[a_n = \frac{p(n)}{n} = \frac{p}{pm} = \frac1m. \] Summing $a_n$ over all composite $n<x$ and grouping terms by $p=p(n)$ yields exactly the double sum on the right-hand side. $\square$

Lemma 462.3 (average short-interval mass from the global asymptotic). Assume the asymptotic stated in the problem: \[S(x):=\sum_{n<x} a_n\sim c\frac{x^{1/2}}{(\log x)^2}.\] Fix $C>0$ and define $L(x):=\lfloor C x^{1/2}(\log x)^2\rfloor$. Consider the corrected short-interval sums \[T_{\mathrm{comp}}(x):=\sum_{x\le n\le x+L(x)} a_n\quad (a_n\ge 0).\] Then as $X\to\infty$, \[\frac1{X}\sum_{x=X}^{2X} T_{\mathrm{comp}}(x)\ \ge\ cC(\sqrt{2}-1)+o(1).\] In particular, there exist arbitrarily large $x$ for which $T_{\mathrm{comp}}(x)\gg_C 1$.

Proof. Let \[L_{\min}:=\lfloor C X^{1/2}(\log X)^2\rfloor. \] For all integers $x\in[X,2X]$, monotonicity of the function $x\mapsto x^{1/2}(\log x)^2$ implies $L(x)\ge L_{\min}$ for all sufficiently large $X$. Since $a_n\ge 0$, we have \[T_{\mathrm{comp}}(x)=\sum_{x\le n\le x+L(x)} a_n\ \ge\ \sum_{x\le n\le x+L_{\min}} a_n.\] Summing this inequality over $x=X,X+1,\dots,2X$ and swapping the order of summation gives \[\sum_{x=X}^{2X} T_{\mathrm{comp}}(x)\ \ge\ \sum_{x=X}^{2X}\ \sum_{x\le n\le x+L_{\min}} a_n =\sum_{n} a_n\,\#\{x\in[X,2X]: x\le n\le x+L_{\min}\}. \] Now fix any integer $n$ with $X+L_{\min}\le n\le 2X$. For each integer $j\in\{0,1,\dots,L_{\min}-1\}$ let $x=n-j$. Then $x\in[X,2X]$ and $x+L_{\min}=n-j+L_{\min}\ge n$, so $x\le n\le x+L_{\min}$. Hence \[\#\{x\in[X,2X]: x\le n\le x+L_{\min}\}\ \ge\ L_{\min}. \] Therefore \[\sum_{x=X}^{2X} T_{\mathrm{comp}}(x)\ \ge\ L_{\min}\sum_{n=X+L_{\min}}^{2X} a_n =L_{\min}\left(S(2X+1)-S(X+L_{\min})\right). \] Because $L_{\min}=o(X)$, the asymptotic for $S$ implies \[S(2X+1)-S(X+L_{\min})\ =\ c\frac{(2X)^{1/2}}{(\log X)^2}-c\frac{X^{1/2}}{(\log X)^2}+o\!\left(\frac{X^{1/2}}{(\log X)^2}\right) = c(\sqrt{2}-1)\frac{X^{1/2}}{(\log X)^2}+o\!\left(\frac{X^{1/2}}{(\log X)^2}\right). \] Multiplying by $L_{\min}=C X^{1/2}(\log X)^2+o\left(X^{1/2}(\log X)^2\right)$ yields \[\sum_{x=X}^{2X} T_{\mathrm{comp}}(x)\ \ge\ cC(\sqrt{2}-1)X+o(X). \] Dividing by $X$ proves the claimed average lower bound. Since an average over $x\in[X,2X]$ is bounded below by a positive constant for large $X$, at least one $x\in[X,2X]$ must satisfy $T_{\mathrm{comp}}(x)\gg_C 1$; letting $X\to\infty$ gives arbitrarily large such $x$. $\square$

5) VERIFICATION

• Checked that the ambiguity about primes is real (it is also noted in the discussion thread).
• Lemma 462.2: verified uniqueness of decomposition $n=p\,m$ with $p$ least prime factor.
• Lemma 462.3: verified the lower bound on the counting multiplicity $\#\{x: x\le n\le x+L(x)\}$ uses only monotonicity of $L(x)$ on $[X,2X]$ for large $X$ and that $L(x)\gg \sqrt{X}(\log X)^2$.
• Computations: used a least-prime-factor sieve up to $2\cdot 10^6$ and prefix sums of $a_n$ (excluding primes).

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: After excluding primes (the corrected reading), we have the exact decomposition \[\sum_{n<x,\,n\ \mathrm{composite}}\frac{p(n)}{n}=\sum_{p\ \mathrm{prime}}\ \sum_{\substack{m<x/p\\ m\ge 2,\ p(m)\ge p}} \frac1m\] (Lemma 462.2), and assuming the stated global asymptotic one can prove that the short-interval sum has positive average size $\asymp cC$ over $x\in[X,2X]$ (Lemma 462.3), hence is $\gg 1$ for infinitely many $x$. Computations for $x\le 1.5\cdot 10^6$ and $C=1$ show values around $4$.

(ii) First gap (crisp): Upgrade the average lower bound to a pointwise one: prove there exists $C>0$ and $c_0>0$ such that for every sufficiently large $x$, \[\sum_{\substack{x\le n\le x+C\sqrt{x}(\log x)^2\\ n\ \mathrm{composite}}}\frac{p(n)}{n}\ge c_0. \]

(iii) Top 3 next moves:

1. Show that intervals of length $\asymp \sqrt{x}(\log x)^2$ always contain enough semiprimes $pq$ with $p,q\approx \sqrt{x}\,\log^{O(1)}x$, since such terms contribute $\approx 1/q$.
2. Prove a lower bound for the count of integers $n$ in $[x,x+\sqrt{x}(\log x)^2]$ whose least prime factor lies in a controlled range (e.g. $p(n)\approx \sqrt{x}\,\log^A x$).
3. Numerically search for $x$ where the corrected interval sum is unusually small (relative to its average) to guess the obstruction structure.

(iv) Minimal counterexample structure: A minimal counterexample (under the corrected reading) would be a large $x$ for which the interval $[x,x+C\sqrt{x}(\log x)^2]$ contains very few composites with least prime factor $\gg \sqrt{x}/\log^{O(1)}x$; heuristically this would mean the interval avoids most semiprimes $pq$ with $p,q\approx \sqrt{x}\,\log^{O(1)}x$ and is dominated by numbers with very small least prime factor (whose contributions $p(n)/n$ are tiny).