Erdős Problem #950

Erdős Problem 950 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

Erdős Problem #950

FORMAL RESTATEMENT

Define for integers $n\ge 1$: \[ f(n):=\sum_{\substack{p\ \text{prime}\\ p<n}}\frac{1}{n-p}. \] Questions:

1. Is $\liminf_{n\to\infty} f(n)=1$?
2. Is $\limsup_{n\to\infty} f(n)=\infty$?
3. Is it true that $f(n)=o(\log\log n)$ as $n\to\infty$ (for all integers $n$)?

QUICK LITERATURE/CONTEXT CHECK

The problem text states (and I take as given here) that de Bruijn--Erdős--Turán proved \[ \sum_{n<x} f(n)\sim x,\qquad \sum_{n<x} f(n)^2\sim x. \] It also states conditional implications relating $\liminf f(n)$ to primes in short intervals and a remark about bounding $f(n)$ under assumptions on $\pi(x)$ in short ranges. I do not add any external claims.

ATTACK PLAN

• Reality check: compute $f(n)$ for moderate $n$ to see the range of values.
• Unconditional lemmas: derive exact reformulations and simple bounds (dyadic decomposition gives $f(n)=O(\log n)$).
• Conditional mechanisms: prove clean implications of the form "many primes in $[n-m,n)$ $\Rightarrow$ $f(n)$ large" and "large prime gaps $\Rightarrow$ $f(n)$ can be small" (the latter is harder unconditionally).
• Stop: I do not expect a full resolution without deep prime-distribution input.

WORK

Fast reality check (computation). I computed $f(n)$ for $2\le n\le 5000$ by direct summation over primes $p<n$. Results:

• The minimum on $[2,5000]$ is $f(2)=0$ (empty sum). For $n\ge3$, the smallest value in this range occurred at $n=11$ with $f(11)=0.652777\ldots$.
• The maximum on $[2,5000]$ occurred at $n=3470$ with $f(3470)\approx 2.2768429429$.
• Sample values: $f(3)=1$, $f(4)=1.5$, $f(5)=5/6$, $f(10)\approx 0.80119$.

(These values are only a sanity check and do not determine the asymptotics.)

Lemma 950.1 (exact reformulation). For every integer $n\ge 2$, \[ f(n)=\sum_{k=1}^{n-2}\frac{1}{k}\,\mathbf 1_{\{n-k\ \mathrm{is\ prime}\}}, \] where $\mathbf 1_E$ is the indicator function.

Proof. In the original definition, substitute $k:=n-p$. As $p$ runs over primes $<n$, the quantity $k=n-p$ runs over integers $1\le k\le n-2$ such that $n-k$ is prime, and the summand $1/(n-p)$ becomes $1/k$. $\square$

Lemma 950.2 (unconditional dyadic upper bound). For every integer $n\ge 3$, \[ f(n)\le 2\,\lceil \log_2(n)\rceil. \] In particular $f(n)=O(\log n)$.

Proof. Partition the possible denominators $k=n-p$ into dyadic ranges. For $j\ge 0$, let \[ I_j:=\{k:\ 2^j<k\le 2^{j+1}\}. \] Then by Lemma 950.1, \[ f(n)=\sum_{j=0}^{\lceil\log_2(n)\rceil-1}\ \sum_{k\in I_j}\frac{1}{k}\,\mathbf 1_{\{n-k\ \mathrm{prime}\}}. \] For each $k\in I_j$, we have $1/k\le 1/2^j$. Also, the number of integers $k$ in $I_j$ is $|I_j|\le 2^{j+1}$, hence the number of primes of the form $n-k$ with $k\in I_j$ is at most $2^{j+1}$. Therefore the inner sum is bounded by \[ \sum_{k\in I_j}\frac{1}{k}\,\mathbf 1_{\{n-k\ \mathrm{prime}\}}\le \frac{1}{2^j}\cdot 2^{j+1}=2. \] Summing over $j$ gives $f(n)\le 2\lceil\log_2(n)\rceil$. $\square$

Lemma 950.3 (short-interval prime count forces large $f(n)$). Let $n\ge 3$ and $m\in\{1,2,\dots,n-2\}$. If there are at least $t$ primes in the interval $[n-m,n)$, i.e. \[ \#\{p\ \text{prime}:\ n-m\le p<n\}\ge t, \] then \[ f(n)\ge \frac{t}{m}. \]

Proof. Each such prime $p\in[n-m,n)$ contributes a term $1/(n-p)$ to $f(n)$ with denominator $n-p\le m$. Hence each such term is $\ge 1/m$, and summing over at least $t$ primes gives $f(n)\ge t/m$. $\square$

VERIFICATION

• Lemma 950.1 is a change of variables; checked range $p<n$ corresponds to $1\le k\le n-2$.
• Lemma 950.2 uses only the trivial bound "at most one prime per integer"; no hidden prime distribution.
• Lemma 950.3 is a direct monotonicity bound (primes closer to $n$ contribute larger terms).
• Computation sanity: verified small values by hand for $n=3,4,5$.

FINAL

UNRESOLVED

(i) Strongest proved partial result. Unconditionally, $f(n)=O(\log n)$ (Lemma 950.2) and if $[n-m,n)$ contains $t$ primes then $f(n)\ge t/m$ (Lemma 950.3). Computations up to $n=5000$ give values in roughly $[0.65,2.28]$ for $n\ge3$.

(ii) First gap. Prove either $\limsup f(n)=\infty$ or show it is bounded; similarly prove the exact value of $\liminf f(n)$ (conjectured to be $1$ in the statement) without appealing to results not included in the problem text.

(iii) Top 3 next moves.

1. Push computation much further (e.g. $n\le 10^7$) to estimate empirical growth of $\max_{n\le N} f(n)$ and behavior of small values.
2. Try to prove a lower bound mechanism for $\limsup$: find an explicit family of $n$ for which $[n-m,n)$ has unusually many primes (even modest $t\to\infty$ with $m$ fixed would force $f(n)\to\infty$ by Lemma 950.3).
3. For the $o(\log\log n)$ question, attempt to bound contributions from dyadic shells using any available uniform estimates for primes in intervals $[n-2^{j+1},n-2^j]$.

(iv) What a minimal counterexample would likely look like. To falsify $\limsup f(n)=\infty$, one would need a uniform bound on local prime clustering near every $n$. To falsify $\liminf f(n)=1$ (if interpreted as equality), one would need infinitely many $n$ where primes are sufficiently sparse in all ranges $[n-m,n)$ so that the weighted reciprocal sum stays below $1-\varepsilon$.

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.

Erdős Problem #950

FORMAL RESTATEMENT

Define for integers $n\ge 1$: \[ f(n):=\sum_{\substack{p\ \text{prime}\\ p<n}}\frac{1}{n-p}. \] Questions:

1. Is $\liminf_{n\to\infty} f(n)=1$?
2. Is $\limsup_{n\to\infty} f(n)=\infty$?
3. Is it true that $f(n)=o(\log\log n)$ as $n\to\infty$ (for all integers $n$)?

QUICK LITERATURE/CONTEXT CHECK

The problem text states (and I take as given here) that de Bruijn--Erdős--Turán proved \[ \sum_{n<x} f(n)\sim x,\qquad \sum_{n<x} f(n)^2\sim x. \] It also states conditional implications relating $\liminf f(n)$ to primes in short intervals and a remark about bounding $f(n)$ under assumptions on $\pi(x)$ in short ranges. I do not add any external claims.

ATTACK PLAN

• Reality check: compute $f(n)$ for moderate $n$ to see the range of values.
• Unconditional lemmas: derive exact reformulations and simple bounds (dyadic decomposition gives $f(n)=O(\log n)$).
• Conditional mechanisms: prove clean implications of the form "many primes in $[n-m,n)$ $\Rightarrow$ $f(n)$ large" and "large prime gaps $\Rightarrow$ $f(n)$ can be small" (the latter is harder unconditionally).
• Stop: I do not expect a full resolution without deep prime-distribution input.

WORK

Fast reality check (computation). I computed $f(n)$ for $2\le n\le 5000$ by direct summation over primes $p<n$. Results:

• The minimum on $[2,5000]$ is $f(2)=0$ (empty sum). For $n\ge3$, the smallest value in this range occurred at $n=11$ with $f(11)=0.652777\ldots$.
• The maximum on $[2,5000]$ occurred at $n=3470$ with $f(3470)\approx 2.2768429429$.
• Sample values: $f(3)=1$, $f(4)=1.5$, $f(5)=5/6$, $f(10)\approx 0.80119$.

(These values are only a sanity check and do not determine the asymptotics.)

Lemma 950.1 (exact reformulation). For every integer $n\ge 2$, \[ f(n)=\sum_{k=1}^{n-2}\frac{1}{k}\,\mathbf 1_{\{n-k\ \mathrm{is\ prime}\}}, \] where $\mathbf 1_E$ is the indicator function.

Proof. In the original definition, substitute $k:=n-p$. As $p$ runs over primes $<n$, the quantity $k=n-p$ runs over integers $1\le k\le n-2$ such that $n-k$ is prime, and the summand $1/(n-p)$ becomes $1/k$. $\square$

Lemma 950.2 (unconditional dyadic upper bound). For every integer $n\ge 3$, \[ f(n)\le 2\,\lceil \log_2(n)\rceil. \] In particular $f(n)=O(\log n)$.

Proof. Partition the possible denominators $k=n-p$ into dyadic ranges. For $j\ge 0$, let \[ I_j:=\{k:\ 2^j<k\le 2^{j+1}\}. \] Then by Lemma 950.1, \[ f(n)=\sum_{j=0}^{\lceil\log_2(n)\rceil-1}\ \sum_{k\in I_j}\frac{1}{k}\,\mathbf 1_{\{n-k\ \mathrm{prime}\}}. \] For each $k\in I_j$, we have $1/k\le 1/2^j$. Also, the number of integers $k$ in $I_j$ is $|I_j|\le 2^{j+1}$, hence the number of primes of the form $n-k$ with $k\in I_j$ is at most $2^{j+1}$. Therefore the inner sum is bounded by \[ \sum_{k\in I_j}\frac{1}{k}\,\mathbf 1_{\{n-k\ \mathrm{prime}\}}\le \frac{1}{2^j}\cdot 2^{j+1}=2. \] Summing over $j$ gives $f(n)\le 2\lceil\log_2(n)\rceil$. $\square$

Lemma 950.3 (short-interval prime count forces large $f(n)$). Let $n\ge 3$ and $m\in\{1,2,\dots,n-2\}$. If there are at least $t$ primes in the interval $[n-m,n)$, i.e. \[ \#\{p\ \text{prime}:\ n-m\le p<n\}\ge t, \] then \[ f(n)\ge \frac{t}{m}. \]

Proof. Each such prime $p\in[n-m,n)$ contributes a term $1/(n-p)$ to $f(n)$ with denominator $n-p\le m$. Hence each such term is $\ge 1/m$, and summing over at least $t$ primes gives $f(n)\ge t/m$. $\square$

VERIFICATION

• Lemma 950.1 is a change of variables; checked range $p<n$ corresponds to $1\le k\le n-2$.
• Lemma 950.2 uses only the trivial bound "at most one prime per integer"; no hidden prime distribution.
• Lemma 950.3 is a direct monotonicity bound (primes closer to $n$ contribute larger terms).
• Computation sanity: verified small values by hand for $n=3,4,5$.

FINAL

UNRESOLVED

(i) Strongest proved partial result. Unconditionally, $f(n)=O(\log n)$ (Lemma 950.2) and if $[n-m,n)$ contains $t$ primes then $f(n)\ge t/m$ (Lemma 950.3). Computations up to $n=5000$ give values in roughly $[0.65,2.28]$ for $n\ge3$.

(ii) First gap. Prove either $\limsup f(n)=\infty$ or show it is bounded; similarly prove the exact value of $\liminf f(n)$ (conjectured to be $1$ in the statement) without appealing to results not included in the problem text.

(iii) Top 3 next moves.

1. Push computation much further (e.g. $n\le 10^7$) to estimate empirical growth of $\max_{n\le N} f(n)$ and behavior of small values.
2. Try to prove a lower bound mechanism for $\limsup$: find an explicit family of $n$ for which $[n-m,n)$ has unusually many primes (even modest $t\to\infty$ with $m$ fixed would force $f(n)\to\infty$ by Lemma 950.3).
3. For the $o(\log\log n)$ question, attempt to bound contributions from dyadic shells using any available uniform estimates for primes in intervals $[n-2^{j+1},n-2^j]$.

(iv) What a minimal counterexample would likely look like. To falsify $\limsup f(n)=\infty$, one would need a uniform bound on local prime clustering near every $n$. To falsify $\liminf f(n)=1$ (if interpreted as equality), one would need infinitely many $n$ where primes are sufficiently sparse in all ranges $[n-m,n)$ so that the weighted reciprocal sum stays below $1-\varepsilon$.