Erdős Problem #377

Problem 377. Is $\displaystyle f(n)=\sum_{p\le n,\ p\nmid \binom{2n}{n}}\frac1p$ bounded? --- Round 2

1) ROUND-2 OBJECTIVE

Path (C): strict progress by proving a new theorem that localizes any possible unboundedness to arbitrarily small primes.

Round 1 recorded the average-order results of Erdős--Graham--Ruzsa--Straus and left open whether $f(n)$ is bounded. In this round I prove a new uniform upper bound for the contribution of all primes in the range $n^{1/(m+1)}<p\le n$, for every fixed $m$. In particular, primes $\sqrt{n}<p\le n$ can contribute at most $\log 2+o(1)$. So if $f(n)$ is unbounded, the entire growth must come from smaller and smaller primes.

2) Round-1 FOUNDATION USED

I use only the Round-1 Kummer reformulation: for a prime $p$, \[ p\nmid \binom{2n}{n} \] if and only if every base-$p$ digit of $n$ is at most $(p-1)/2$. No other Round-1 proof is reproved.

3) NEW INSIGHT / TOOL (ROUND-2)

The new observation is a size-digit lemma:

if \[ n^{1/(k+1)}<p\le n^{1/k} \] and $p\nmid \binom{2n}{n}$, then the base-$p$ expansion of $n$ has exactly $k+1$ digits, each at most $(p-1)/2$, hence \[ n\le \frac{p^{k+1}-1}{2}. \] This forces \[ p\ge (2n+1)^{1/(k+1)}. \] So in each dyadic-like prime window $(n^{1/(k+1)},\,n^{1/k}]$, the "good" primes can only occupy the much shorter terminal interval \[ [(2n+1)^{1/(k+1)},\,n^{1/k}]. \] Summing reciprocal primes over these terminal intervals gives a new explicit bound.

4) ATTACK PLAN (ROUND-2)

The exact gap after Round 1 was that there was no structural theorem explaining where a possible blow-up of $f(n)$ could come from.

I now prove: \[ \sum_{\substack{n^{1/(m+1)}<p\le n\\ p\nmid \binom{2n}{n}}}\frac1p \le \log(m+1)+o(1) \qquad (m \text{ fixed}). \] This will imply that any unboundedness of $f(n)$ must be caused by primes \[ p\le n^{1/(m+1)} \] for every fixed $m$, since the complementary range $n^{1/(m+1)}<p\le n$ has uniformly bounded total weight. That is a genuine narrowing of the problem.

5) WORK (ROUND-2)

Write \[ C_n:=\binom{2n}{n}. \]

Lemma 5.1 (window lemma)

Fix an integer $k\ge 1$. For each $n$, define \[ I_k(n):=\sum_{\substack{n^{1/(k+1)}<p\le n^{1/k}\\ p\nmid C_n}}\frac1p. \] Then, as $n\to\infty$ with $k$ fixed, \[ I_k(n)\le \log\!\left(\frac{k+1}{k}\right)+o(1). \]

Proof.

Let \[ n^{1/(k+1)}<p\le n^{1/k} \] and suppose $p\nmid C_n$. By Kummer's theorem, every base-$p$ digit of $n$ is at most $(p-1)/2$.

Because $p\le n^{1/k}$, we have $p^k\le n$, so the base-$p$ expansion of $n$ has at least $k+1$ digits. Because $p>n^{1/(k+1)}$, we have $p^{k+1}>n$, so the expansion has at most $k+1$ digits. Hence $n$ has exactly $k+1$ base-$p$ digits: \[ n=a_0+a_1p+\cdots + a_kp^k, \qquad 0\le a_j\le \frac{p-1}{2}. \] Therefore \[ n\le \frac{p-1}{2}\sum_{j=0}^k p^j = \frac{p-1}{2}\cdot \frac{p^{k+1}-1}{p-1} = \frac{p^{k+1}-1}{2}. \] Rearranging gives \[ p\ge (2n+1)^{1/(k+1)}. \] So every prime counted by $I_k(n)$ lies in the interval \[ (2n+1)^{1/(k+1)}\le p\le n^{1/k}. \] Hence \[ I_k(n)\le \sum_{(2n+1)^{1/(k+1)}\le p\le n^{1/k}}\frac1p. \] Now use the classical Mertens asymptotic \[ \sum_{p\le x}\frac1p=\log\log x + B_1 + o(1). \] Taking the difference at the two endpoints yields \[ I_k(n)\le \log\log(n^{1/k})-\log\log((2n+1)^{1/(k+1)})+o(1). \] Since \[ \log\log(n^{1/k})=\log\log n - \log k \] and \[ \log\log((2n+1)^{1/(k+1)}) = \log\log(2n+1)-\log(k+1), \] we obtain \[ I_k(n)\le \log\!\left(\frac{k+1}{k}\right) + \log\!\left(\frac{\log n}{\log(2n+1)}\right) +o(1) = \log\!\left(\frac{k+1}{k}\right)+o(1). \] This proves the lemma. $\square$

Theorem 5.2 (large-prime contribution is uniformly bounded)

Fix $m\ge 1$. Then \[ \sum_{\substack{n^{1/(m+1)}<p\le n\\ p\nmid C_n}}\frac1p \le \log(m+1)+o(1) \qquad (n\to\infty). \]

Proof.

For primes $p\le n$, the condition $n^{1/(m+1)}<p\le n$ partitions uniquely into the windows \[ n^{1/(k+1)}<p\le n^{1/k}, \qquad k=1,2,\dots,m. \] Therefore \[ \sum_{\substack{n^{1/(m+1)}<p\le n\\ p\nmid C_n}}\frac1p = \sum_{k=1}^m I_k(n). \] Applying Lemma 5.1 to each fixed $k$ and summing, \[ \sum_{\substack{n^{1/(m+1)}<p\le n\\ p\nmid C_n}}\frac1p \le \sum_{k=1}^m \left(\log\!\left(\frac{k+1}{k}\right)+o(1)\right). \] Because $m$ is fixed, \[ \sum_{k=1}^m o(1)=o(1), \] and the logarithms telescope: \[ \sum_{k=1}^m \log\!\left(\frac{k+1}{k}\right)=\log(m+1). \] Hence \[ \sum_{\substack{n^{1/(m+1)}<p\le n\\ p\nmid C_n}}\frac1p \le \log(m+1)+o(1). \] This proves the theorem. $\square$

Corollary 5.3 (all possible unboundedness comes from very small primes)

Assume that $f(n)$ is unbounded. Then for every fixed $m\ge 1$ there exists a sequence $n_j\to\infty$ such that \[ \sum_{\substack{p\le n_j^{1/(m+1)}\\ p\nmid C_{n_j}}}\frac1p \to \infty. \]

Proof.

By definition, \[ f(n) = \sum_{\substack{p\le n^{1/(m+1)}\\ p\nmid C_n}}\frac1p + \sum_{\substack{n^{1/(m+1)}<p\le n\\ p\nmid C_n}}\frac1p. \] The second sum is at most $\log(m+1)+o(1)$ by Theorem 5.2. So if $f(n)$ is unbounded, the first sum must be unbounded along some sequence. $\square$

Special case

Taking $m=1$ gives \[ \sum_{\substack{\sqrt{n}<p\le n\\ p\nmid C_n}}\frac1p\le \log 2+o(1). \] Thus primes in the range $\sqrt{n}<p\le n$ can never be responsible for an unbounded growth of $f(n)$.

6) ADVERSARIAL VERIFICATION

Checks on the new argument:

• Number of digits. For $n^{1/(k+1)}<p\le n^{1/k}$, indeed $p^k\le n<p^{k+1}$, so the base-$p$ expansion has exactly $k+1$ digits. No edge case is missed.

• Could the top digit be smaller than $(p-1)/2$ and ruin the bound? No. Replacing the top digit by the maximal allowed value only enlarges the right-hand side, so the inequality \[ n\le \frac{p^{k+1}-1}{2} \] remains valid.

• Dependence on $m$. The theorem is for each fixed $m$. The $o(1)$ term may depend on $m$, which is harmless.

• Does this prove boundedness of $f(n)$? No. It only proves that the contribution from primes in the range $n^{1/(m+1)}<p\le n$ is uniformly bounded for each fixed $m$. The unresolved part is the cumulative contribution of much smaller primes.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The new theorem is: for every fixed $m\ge 1$, \[ \sum_{\substack{n^{1/(m+1)}<p\le n\\ p\nmid \binom{2n}{n}}}\frac1p \le \log(m+1)+o(1). \] In particular, \[ \sum_{\substack{\sqrt{n}<p\le n\\ p\nmid \binom{2n}{n}}}\frac1p \le \log 2+o(1). \] Therefore any possible unboundedness of $f(n)$ must come from primes \[ p\le n^{1/(m+1)} \] for every fixed $m$. This sharply localizes the remaining difficulty.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 57%

9) REFERENCES

[EGRS75] P. Erdős, R. L. Graham, I. Z. Ruzsa, and E. G. Straus, On the prime factors of $\binom{2n}{n}$, Math. Comp. 29 $1975$, 83--92.

[RS62] J. B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 $1962$, 64--94.

Problem 377: separating a trivial uniform bound from digit-count information

1) OBJECTIVE AND SOURCE REVIEW

Attempt dated 2026-09-23. The target is boundedness of $f(n)=\sum_{p\le n,\ p\nmid\binom{2n}{n}}1/p$. I read all of 377.tex and checked the 1975 primary paper. The source's bound $\log(m+1)+o(1)$ above $n^{1/(m+1)}$ already follows by dropping the nondivisibility restriction and applying the prime reciprocal asymptotic. Its digit-window lemma is valid, but its stated leading constant is not an improvement over that trivial estimate. Here I give a self-contained averaged consequence of the digit condition, without presenting it as a new literature result.

2) WORK

For an odd prime $p$, put $r_p=(p+1)/2$ and $L=\lfloor\log X/\log p\rfloor$. Nondivisibility means that every base-$p$ digit of $n$ belongs to $\{0,\ldots,(p-1)/2\}$. Hence the number $G_p(X)$ of such integers $0\le n\le X$ is at most $r_p^{L+1}$. Since $X\ge p^L$, \[ \frac{G_p(X)}{pX}\le\left(\frac{r_p}{p}\right)^{L+1}. \] Fix $0<c<\sqrt{\log2}$ and set $y=\exp(c\sqrt{\log X})$. Choose a constant $c_0$ with $c^2<c_0<\log2$. For all sufficiently large fixed $P$, every prime $p\ge P$ has $\log(p/r_p)\ge c_0$. Since $L+1>\log X/\log p$, we obtain \[ \sum_{P\le p\le y}\frac{G_p(X)}{pX} \le y\exp\left(-\frac{c_0\log X}{\log y}\right) =\exp\left((c-c_0/c)\sqrt{\log X}\right)\to0. \] For each of the finitely many primes below $P$, $G_p(X)/(pX)\to0$ directly from the digit bound; prime two contributes nothing for positive $n$. Interchanging two finite sums therefore proves \[ \frac1{\lfloor X\rfloor}\sum_{1\le n\le X} \sum_{\substack{p\le\min(n,y)\\p\nmid\binom{2n}{n}}}\frac1p\longrightarrow0. \] By Markov's inequality, the contribution from this growing small-prime range is $o(1)$ outside a set of $o(X)$ integers, in the usual convergence-in-density sense.

3) ADVERSARIAL VERIFICATION

An averaged estimate permits exceptional integers with large contributions. It therefore does not conflict with the source's observation that any unboundedness must arise from small primes relative to $n$. The cutoff uses $X$, the averaging range, rather than silently replacing it by each individual $n$. The primary paper already establishes stronger average behavior for the full function; this proof is an elementary verification of one mechanism, not an improvement on that theorem.

4) FINAL

UNRESOLVED. Typical digit behavior is controlled, while boundedness at every exceptional integer remains open in this attempt. No new verified worst-case bound for $f$ is obtained.

5) SOURCES CHECKED

The complete supplied version; P. Erdős, R. L. Graham, I. Z. Ruzsa and E. G. Straus, On the Prime Factors of $\binom{2n}{n}$, digit criterion and Theorem 2 checked at https://renyi.hu/~p_erdos/1975-27.pdf, 2026-09-23.

6) COMPLETION ESTIMATE

Subjective progress toward uniform boundedness or an unbounded sequence. COMPLETION: 10%

Problem 377. Is $\displaystyle f(n)=\sum_{p\le n}1_{p\nmid \binom{2n}{n}}\,\frac1p$ bounded?

FORMAL RESTATEMENT

Define for $n\ge 1$ \[ f(n)\;:=\;\sum_{\substack{p\le n\\ p\text{ prime}}} \mathbf{1}_{p\nmid \binom{2n}{n}}\,\frac{1}{p}. \] Is there an absolute constant $C$ such that $f(n)\le C$ for all $n$?

QUICK LITERATURE / CONTEXT CHECK

Erdős--Graham--Ruzsa--Straus $1975$ introduced $f(n)$ and proved:

• $\displaystyle \lim_{x\to\infty}\frac1x\sum_{n\le x} f(n)=\sum_{k\ge 2}\frac{\log k}{2^k}=:\gamma_0$ and $\lim_{x\to\infty}\frac1x\sum_{n\le x} f(n)^2=\gamma_0^2$, hence for almost all $n$, $f(n)=\gamma_0+o(1)$.
• For all sufficiently large $n$, $f(n)\le c\log\log n$ for some absolute constant $c<1$.
• They remark explicitly that they cannot decide whether $f(n)$ is unbounded.

The Erdős problems database (Problem 377) records the same status.

Numerically, $\gamma_0\approx 0.5078339229$.

ATTACK PLAN

To prove boundedness one would need a mechanism showing that for every $n$ there are "enough" primes $p\le n$ that do divide $\binom{2n}{n}$, forcing the complement (weighted by $1/p$) to have bounded harmonic mass.

To disprove boundedness one would need to construct infinitely many $n$ for which many small primes simultaneously satisfy $p\nmid\binom{2n}{n}$, so that $\sum 1/p$ over those primes grows.

Kummer's theorem again translates $p\nmid\binom{2n}{n}$ into the digit condition "all base-$p$ digits of $n$ are $\le (p-1)/2$", making the problem a question about how often $n$ can have small digits in many bases at once.

WORK

1. A simple implication: bounded $f(n)$ would bound the smallest odd prime factor

Let $g(n)$ be the smallest odd prime divisor of $\binom{2n}{n}$ (if it exists). If $g(n)>y$ then no odd prime $p\le y$ divides $\binom{2n}{n}$, hence \[ f(n)\ge \sum_{3\le p\le y} \frac1p. \] Since $\sum_{p\le y}1/p\to\infty$ with $y$, it follows that \[ \sup_n f(n)<\infty \ \Longrightarrow\ \sup_n g(n)<\infty. \] EGRS $1975$ note that even the boundedness of $g(n)$ is unknown.

2. Relation to Problem 376 and "avoiding many primes"

If for some finite set of primes $\mathcal{P}$ we can find $n$ with $p\nmid\binom{2n}{n}$ for all $p\in\mathcal{P}$, then \[ f(n)\ge \sum_{p\in\mathcal{P}}\frac1p. \] Thus unboundedness of $f(n)$ would follow from the ability to simultaneously avoid an increasing collection of small primes.

However, even avoiding $\{3,5,7\}$ (Problem 376) is open; and avoiding any two odd primes is known to be possible infinitely often (EGRS), which only yields a bounded lower bound.

3. Computation for small $n$ (evidence only)

Using Kummer's digit criterion to test $p\nmid\binom{2n}{n}$, a brute-force search over $1\le n\le 20000$ gives:

• the maximum value of $f(n)$ in this range is \[\max_{1\le n\le 20000} f(n) \approx 1.1792429058\quad\text{attained at }n=3250,\]
• other large values occur at $n=3160$ ($\approx 1.1155$) and at $n=756$ ($\approx 1.0770$), both of which are also solutions to Problem 376 (coprime to $105$).

This does not decide boundedness but is consistent with the possibility that $f(n)$ has a modest global supremum.

VERIFICATION

The logical implications in §1--§2 are direct. The numerical values in §3 were computed exactly from the digit condition (not by evaluating $\binom{2n}{n}$).

FINAL

LABEL: UNRESOLVED.
SUB-LABEL: N/A.
The existence of an absolute constant $C$ with $f(n)\le C$ for all $n$ remains open. Known results show $f(n)$ is typically close to the constant $\gamma_0\approx 0.5078$ and always satisfies $f(n)\le c\log\log n$ for some $c<1$ for large $n$, but no boundedness/unboundedness proof is known.

COMPLETION ESTIMATE

A full solution would require either:

• a construction of integers $n$ for which $p\nmid\binom{2n}{n}$ for enough small primes $p$ that $\sum 1/p$ grows without bound (proving unboundedness), or
• a uniform argument forcing the set of avoided primes to have bounded harmonic weight for every $n$ (proving boundedness).

Both directions appear to hinge on deep control of simultaneous small-digit expansions (or carries) in many bases.

Bibliography (informal)

References

• [EGRS75] P. Erdős, R. L. Graham, I. Z. Ruzsa, and E. G. Straus, On the prime factors of $\binom{2n}{n}$, Math. Comp. 29 $1975$, 83--92.
• [EG76] P. Erdős and R. L. Graham, On products of factorials, Bull. Inst. Math. Acad. Sinica 4 $1976$, 337--355.
• [DNSS14] A. Dujella, F. Najman, N. Saradha, and T. N. Shorey, Products of three factorials, Publ. Math. Debrecen 85 $2014$, 3--13.
• [BlCr25] T. F. Bloom and E. Croot, Integers with small digits in multiple bases, arXiv:2509.02835 $2025$.
• [Yu22] H. Yu, Fractal projections with an application in number theory, Proc. Lond. Math. Soc. 125 $2022$, 1060--1109.