ERDŐS/DAILY ▸

← back to the ledger

ERDőS #377 · PARTIAL

Erdős problem #377 — wave8z report

Access/research date: 2026-07-28 UTC.

Outcome

[d: computational-only] I did not solve the uniform problem. I obtained an exact exhaustive result:

\[ \max_{1\le n\le 10^8} f(n)=f(3250) =1.17924290579448139699650384642370596966118\ldots . \]

The maximizer is unique in this range. The computation is certified with integer fixed-point intervals, rather than inferred from floating-point comparisons. A standalone re-verifier is runs/erdos377_wave8z_reverify.py; the optimized scanner used by it is also available separately as runs/erdos377_wave8z_scan.cpp.

[a: elementary-rigorous] I also give exact carry, shell, recurrence, and two-base-digit reformulations below.

[b: rigorous-modulo-named-theorem] A primary-source literature search found a directly relevant theorem of J. W. Sander (1993) which is not mentioned on the live problem page:

\[ \sum_{\substack{p\le n\\p\nmid {2n\choose n}}}\frac{\log p}{p} =(1-\log 2)\log n+o(\log n) \]

for every integer \(n\to\infty\). This does not settle the unweighted sum, but it rigorously confirms that the unresolved mass is a small-prime/digit-depth issue.

Claim labels used throughout:

0. Mandatory live-page check

[d: live-page observation] I used a Bright Data browser session, not datacenter curl, to load both <https://www.erdosproblems.com/377> and its discussion thread. The direct curl request was separately confirmed to receive a Cloudflare HTTP 403.

[d: live-page observation] At access time the page showed:

There was therefore no skip condition.

Verbatim current statement

Is there some absolute constant \(C>0\) such that \[ > \sum_{p\leq n}1_{p\nmid \binom{2n}{n}}\frac{1}{p}\leq C > \] for all \(n\) (where the summation is restricted to primes \(p\leq n\))?

Results and remarks listed on the page

Put

\[ f(n)=\sum_{\substack{p\le n\\p\nmid {2n\choose n}}}\frac1p. \]

[b: EGRS75, as listed on the live page] Erdős, Graham, Ruzsa, and Straus proved

\[ \lim_{x\to\infty}\frac1x\sum_{n\le x}f(n) =\sum_{k=2}^{\infty}\frac{\log k}{2^k}=\gamma_0 \]

and

\[ \lim_{x\to\infty}\frac1x\sum_{n\le x}f(n)^2=\gamma_0^2. \]

Consequently \(f(m)=\gamma_0+o(1)\) for almost all integers \(m\).

[b: EGRS75, as listed on the live page] They also proved that, for all sufficiently large \(n\),

\[ f(n)\le c\log\log n \]

for an absolute \(c<1\). The page notes the immediate Mertens bound \(f(n)\le(1+o(1))\log\log n\).

[b: implication using Mertens] A positive answer would imply

\[ \sum_{\substack{p\le n\\p\mid {2n\choose n}}}\frac1p =(1-o(1))\log\log n. \]

The page reports that Erdős, Graham, Ruzsa, and Straus had “no doubt” about this latter asymptotic, and that the question is mentioned in Guy's problem B33.

The one live comment

[c: unverified comment, accurately summarized] Terence Tao, at 22:25 on 29 August 2025, wrote that the latter asymptotic looks accessible with current technology. He proposed controlling, for fixed \(\varepsilon>0\) and \(1\le k\le \log^{1-\varepsilon}n\), the shell

\[ n^{1/(k+1)}<p\le n^{1/k} \]

using the necessary conditions \(\{n/p^j\}\le 1/2\). He suggested using only \(j=k-1,k-2,\ldots,k-J\), with \(J\asymp\log(1/\varepsilon)\), plus prime number theorems in short intervals. He explicitly identified the very small primes as the hard part of the main problem, analogous to problem #376. The site warns that comments are not verified.

1. Primary-source literature audit

Sources actually opened and checked

  1. [b] P. Erdős, R. L. Graham, I. Z. Ruzsa, and E. G. Straus,

“On the Prime Factors of \({2n\choose n}\),” Mathematics of Computation 29 (1975), 83–92, DOI 10.1090/S0025-5718-1975-0369288-3; author-archive PDF.

[b] Page 83 defines exactly the present \(f(n)\) and says that the authors could not decide whether \(f(n)\) is unbounded. Page 84 gives the base-\(p\) digit criterion used below. The paper proves the mean and second moment quoted by the live page.

  1. [b] P. Erdős, “Some Unconventional Problems in Number Theory,”

Mathematics Magazine 52 (1979), 67–70, DOI 10.1080/0025570X.1979.11976756; author-archive PDF. On page 67 Erdős states exactly the conjecture that \(f(n)<C\) for all \(n\), citing EGRS75.

  1. [b] P. Erdős and R. L. Graham, *Old and New Problems and Results in

Combinatorial Number Theory* (1980); primary scan. Its binomial-coefficient section repeats that boundedness was undecided.

  1. [b] J. W. Sander, “On primes not dividing binomial coefficients,”

Mathematical Proceedings of the Cambridge Philosophical Society 113 (1993), 225–232, DOI 10.1017/S0305004100075927; repository PDF.

[b] Sander explicitly defines the same \(f(n)\), says its boundedness was unknown, and proves the log-weighted theorem displayed in the Outcome. This is relevant literature not currently listed on the live page.

  1. [b] J. W. Sander, “On a sum over primes,” Hardy–Ramanujan Journal

17 (1994), 32–39; journal PDF.

[b] For primes satisfying \(n=kp+r\) with \(p/2<r<p\), it proves, for every fixed \(\delta>0\),

\[ \sum_{p\le n}^{*}\frac{\log p}{p} =\frac12\log n+O_\delta((\log n)^{5/6+\delta}). \]

This is a log-weighted version of the related conjecture, not the required unweighted result.

Forward and current searches

[d: database/search observation] I queried the OpenAlex forward citations of the verified EGRS75 DOI. It returned 20 works, from 1979 through 2024. I checked the titles and records; Sander's 1993 paper was the only hit directly about the present nondividing-prime sum. I also queried the forward citations of Sander's DOI.

[d: database/search observation] Exact-phrase web searches for the title, for “cannot decide if \(f(n)\) is unbounded,” for the displayed reciprocal-prime sum, and for “Erdős problem 377” found the live page, the original sources, Sander's work, and later surveys which still call it open. The arXiv API returned zero results for the exact phrase “primes not dividing binomial coefficients”; a broader central-binomial/reciprocal/prime query returned one unrelated congruence paper.

[c: scope warning] This is evidence, not proof of absence: citation databases are incomplete, and I found no newer primary paper claiming to settle the uniform unweighted question. I do not infer “solved” or “definitively open” from the search; the live page remains the authoritative status source for this task.

2. Exact structural reformulations

2.1 Carry/digit criterion

[a] For every prime \(p\), Legendre's formula gives

\[ \begin{aligned} v_p{2n\choose n} &=\sum_{j\ge1} \left(\left\lfloor\frac{2n}{p^j}\right\rfloor -2\left\lfloor\frac n{p^j}\right\rfloor\right)\\ &=\sum_{j\ge1}\left\lfloor 2\left\{\frac n{p^j}\right\}\right\rfloor. \end{aligned} \]

Every summand is \(0\) or \(1\). Hence

\[ p\nmid {2n\choose n} \quad\Longleftrightarrow\quad \left\{\frac n{p^j}\right\}<\frac12 \quad\hbox{for every }j\ge1. \tag{2.1} \]

[a] For an odd prime, (2.1) is equivalent to every base-\(p\) digit of \(n\) lying in

\[ \left\{0,1,\ldots,\frac{p-1}{2}\right\}. \tag{2.2} \]

This is also Kummer's “no carry in \(n+n\)” criterion. Prime \(2\) never contributes for positive \(n\), because a nonzero binary digit creates a carry.

2.2 Exact digit-depth shells

[a] For \(r\ge1\), define

\[ F_r(n)= \sum_{\substack{p\ {\rm prime}\\p^r\le n<p^{r+1}\\ \text{all base-}p\text{ digits of }n\le(p-1)/2}} \frac1p. \]

The sets of primes are disjoint and

\[ f(n)=\sum_{r\ge1}F_r(n). \tag{2.3} \]

[c: heuristic only] The harmonic mass of the unrestricted \(r\)-th shell is asymptotically \(\log(1+1/r)\), and the no-carry condition heuristically costs a factor \(2^{-r}\). This exactly matches the known mean because

\[ \sum_{r\ge1}\frac1{2^r}\log\left(1+\frac1r\right) =\sum_{k\ge2}\frac{\log k}{2^k}=\gamma_0. \]

This identity is rigorous; treating its summands as pointwise estimates is not.

2.3 Exact polynomial-tail reduction

[b: Mertens theorem] For every fixed \(0<\alpha<1\),

\[ \sum_{n^\alpha<p\le n}\frac1p =\log\frac1\alpha+o(1). \tag{2.4} \]

Therefore the contribution to \(f(n)\) from \(p>n^\alpha\) is uniformly bounded.

[b: Mertens theorem] Consequently, for any one fixed \(0<\alpha<1\), problem #377 is equivalent to the precise small-prime lemma

\[ \boxed{\quad \sum_{\substack{p\le n^\alpha\\p\nmid {2n\choose n}}}\frac1p=O_\alpha(1) \quad\text{uniformly in }n.\quad} \tag{2.5} \]

In particular, it is equivalent to bounding only the primes \(p\le\sqrt n\). If \(f(n)\) is unbounded, then along an unbounded subsequence the obstruction must lie below \(n^\alpha\) for every fixed \(\alpha>0\).

[b: Sander 1993] Sander's theorem gives the complementary refinement

\[ \sum_{\substack{n^\alpha\le p\le n\\p\nmid {2n\choose n}}}\frac1p \le \frac{1-\log2+o(1)}{\alpha}. \tag{2.6} \]

Indeed \(\log p\ge\alpha\log n\) in this range. Equation (2.6) again does not control (2.5).

2.4 Exact two-digit formula for \(p>\sqrt n\)

[a] If \(p>\sqrt n\), write

\[ n=kp+r,\qquad 0\le r<p. \]

Then \(k<p\), so \(r,k\) are exactly the two base-\(p\) digits of \(n\). Thus

\[ p\nmid {2n\choose n} \quad\Longleftrightarrow\quad 2k<p\ \hbox{ and }\ 2r<p. \tag{2.7} \]

Equivalently, for each possible \(k=\lfloor n/p\rfloor\), the contributing primes are exactly those in the integer interval

\[ \begin{aligned} \max\bigg\{& \lfloor\sqrt n\rfloor+1,\, \left\lfloor\frac n{k+1}\right\rfloor+1,\, 2k+1,\, \left\lceil\frac{2n+1}{2k+1}\right\rceil \bigg\}\\ &\hspace{35mm}\le p\le \left\lfloor\frac nk\right\rfloor. \end{aligned} \tag{2.8} \]

The intervals are disjoint because \(k=\lfloor n/p\rfloor\). Formula (2.8) is a closed exact description of the entire \(p>\sqrt n\) part. The verifier checks (2.7) against the full digit and Legendre tests.

3. Exact exhaustive computation through \(10^8\)

3.1 Recurrence

Let \(B_n={2n\choose n}\). Then

\[ \frac{B_n}{B_{n-1}}=\frac{2(2n-1)}n, \]

so, for every prime \(p\),

\[ v_p(B_n)=v_p(B_{n-1}) +1_{p=2}+v_p(2n-1)-v_p(n). \tag{3.1} \]

[a] Starting with \(B_0=1\), (3.1) exactly updates all valuations by factoring only \(n\) and \(2n-1\). When a valuation crosses between zero and positive, the reciprocal-prime score is updated. A prime \(p=n\) is inserted only after the \(n\)-th recurrence update, which handles the moving restriction \(p\le n\).

The core update used in the scanner is:

// B_n/B_{n-1} = 2(2n-1)/n.
change_exponent(2, 1, n);
apply_factorization(2 * n - 1, 1, n);
apply_factorization(n, -1, n);

// The new endpoint p=n has only now become eligible.
if (n >= 2 && least_prime[n] == n && exponent[n] == 0)
    score += SCALE / n;

The complete runnable implementations are in the two files named above.

3.2 Integer ordering certificate

[a] Set \(S=2^{60}\) and define

\[ W(n)=\sum_{\substack{p\le n\\p\nmid B_n}}\left\lfloor\frac Sp\right\rfloor. \]

For every \(n\le N\),

\[ W(n)\le S f(n)<W(n)+\pi(N). \tag{3.2} \]

Thus, if the largest computed \(W\)-score exceeds every other score by more than \(\pi(N)\), its ordering as an \(f\)-score is mathematically certified. There is no floating-point assumption in this step.

[d: exhaustive certified computation] At \(N=10^8\), the scanner found

\[ \begin{array}{c|r} n & W(n)\\ \hline 3250 & 1\,359\,574\,505\,245\,523\,668\\ 19\,723\,377 & 1\,344\,512\,879\,520\,316\,444 \end{array} \]

where the second row is the largest fixed score away from \(n=3250\). The exact gap is

\[ 15\,061\,625\,725\,207\,224, \]

whereas

\[ \pi(10^8)=5\,761\,455. \]

The gap is over \(2.6\times10^9\) times the worst-case integer rounding allowance in (3.2). Therefore \(n=3250\) is the unique exact maximizer of \(f(n)\) on \(1\le n\le10^8\).

3.3 Verified table

[d: exhaustive certified computation] The same interval certificate was checked at every row.

| range \(1\le n\le X\) | maximizing \(n\) | exact recomputed \(f(n)\), decimal | |---:|---:|---:| | \(10\) | \(10\) | \(0.67619047619047619047\ldots\) | | \(100\) | \(27\) | \(0.79727534098243480395\ldots\) | | \(1\,000\) | \(756\) | \(1.07697743830023377213\ldots\) | | \(10\,000\) | \(3250\) | \(1.17924290579448139700\ldots\) | | \(100\,000\) | \(3250\) | same | | \(1\,000\,000\) | \(3250\) | same | | \(10\,000\,000\) | \(3250\) | same | | \(100\,000\,000\) | \(3250\) | same |

[d: exhaustive computation] The positive fixed-point \(W\)-score record locations through \(10^8\) are

\[ 3,7,9,10,27,120,121,255,364,756,3160,3250. \]

There is no later \(W\)-record in the scanned range. This diagnostic list is not being used as a claim about every prefix record of the exact real-valued \(f\); the exact claims in the table and the global maximum use the interval gap certificates.

[d: direct recomputation] At the maximizer there are 271 contributing primes. Splitting at \(\sqrt{3250}\) gives

\[ \begin{aligned} \sum_{\substack{p\le\sqrt{3250}\\p\nmid {6500\choose3250}}}\frac1p &=0.88936791320346948985333209730973028960\ldots,\\ \sum_{\substack{\sqrt{3250}<p\le3250\\p\nmid {6500\choose3250}}}\frac1p &=0.28987499259101190714317174911397568006\ldots. \end{aligned} \]

The eight contributing primes below \(\sqrt{3250}\) are

\[ 3,5,7,13,19,23,47,53. \]

This concrete split illustrates that the unusually large value is driven mostly by the small-prime component isolated in (2.5).

3.4 Independent checks performed

[d] runs/erdos377_wave8z_reverify.py:

  1. compiles a fresh temporary C++17 scanner and exhausts every

\(1\le n\le10^8\);

  1. independently constructs a Python Eratosthenes sieve and verifies

\(\pi(10^8)=5\,761\,455\);

  1. recomputes the winner and fixed-score runner-up directly from every

relevant prime's base-\(p\) digits;

  1. checks Kummer's digit answer against Legendre's valuation formula for every

such prime;

  1. computes the literal integer \({6500\choose3250}\) and checks its residue

modulo every prime \(p\le3250\);

  1. performs a separate pure-Python brute-force scan through \(n=10\,000\);
  2. verifies the fixed-point gap certificate at every table cutoff.

The final successful output began:

PASS: exhaustive recurrence scan and independent checks agree
N=100000000
winner=3250 fixed_score=1359574505245523668
f=1.17924290579448139699650384642370596966118379121251463318885

The complete score-stream FNV-64 checksum was 9772412495857686415.

[d] SHA-256 checksums after the successful run:

cd392c113163590ab05289398adaf966ddadb409ec1d534ea3b44ea554b36bed  runs/erdos377_wave8z_reverify.py
3dfa05cd68c0f9d8ed70f1ce579057aeb687068094ac07aecdd1d51a403bfce7  runs/erdos377_wave8z_scan.cpp

[d] The standalone run took about 30 seconds on this VM. The raw single-thread scanner took 29.02 seconds and 1,218,900 KiB peak RSS at \(N=10^8\).

4. What exactly remains

Exact missing lemma

[b: equivalence modulo Mertens] It is enough, and is equivalent, to prove (2.5) for one fixed \(\alpha\in(0,1)\). For example, the still-missing statement can be written without any large primes:

\[ \sum_{\substack{p\le\sqrt n\\ \text{every base-}p\text{ digit of }n\le(p-1)/2}}\frac1p=O(1). \tag{4.1} \]

This is the exact analytic/digital lemma needed after the elementary polynomial-tail reduction.

A sufficient shell estimate

[a] A stronger sufficient statement would be: there exist absolute \(A>0\) and \(0<\rho<1\) such that, uniformly for all \(n\) and all digit depths \(r\),

\[ F_r(n)\le \frac{A\rho^r}{r}. \tag{4.2} \]

Summing (4.2) in (2.3) would immediately prove boundedness.

[c: diagnosis] The average theorem supports decay on the scale \(2^{-r}/r\), but none of the primary sources located gives a pointwise bound uniform in unbounded \(r\). Enforcing only a fixed number \(J\) of the conditions in (2.1) can produce a fixed saving and is the mechanism in Tao's comment. For \(p=n^{o(1)}\), however, the number of relevant powers \(p^j\) is unbounded. A summable estimate requires control that continues to improve with this digit depth. The needed prime counts then lie in many \(n\)-dependent intersections/short intervals whose constants and resolution deteriorate with \(r\). That is the precise point at which the located short-interval/exponential-sum machinery stops.

[c: computation limit] A larger finite scan cannot supply the uniformity in (4.1). The present in-memory recurrence uses approximately \(12N\) bytes and linear-time work. Extrapolating the measured run, \(N=10^{10}\) would require roughly 0.8 single-core hours and 122 GB RAM; \(N=10^{12}\) would require roughly 80 core-hours and 12 TB RAM. A segmented redesign could reduce memory but would still only give a finite check, not (4.1). I did not run those heavier computations.

5. Reproduction

From the repository root:

python runs/erdos377_wave8z_reverify.py

For a smaller diagnostic run:

python runs/erdos377_wave8z_reverify.py --limit 1000000

To run the separate scanner directly:

g++ -O3 -std=c++17 -Wall -Wextra -pedantic \
  runs/erdos377_wave8z_scan.cpp -o /tmp/erdos377_scan
/tmp/erdos377_scan 100000000

[d] The default standalone verifier was run successfully after all final edits. The result is finite computational progress only; it neither proves a global constant nor produces an unbounded sequence.

PARTIAL: Exactly certified max_{n<=10^8} f(n)=f(3250)=1.1792429057944813969965..., found the omitted Sander log-weighted theorem, and reduced the unresolved issue precisely to a uniform small-prime/digit-depth lemma.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger