Erdoes #376 - working report - Erdős Problem a Day

Erdős problem 376 — wave8z report

Live-page access, literature search, and computation: 2026-07-28 UTC.

Claim labels

(a) elementary-rigorous: proved here from elementary facts.
(b) rigorous-modulo-named-theorem: depends on the named theorem or on a

theorem checked in a primary source.

(c) plausible/structural-unverified: heuristic or conditional route,

never used as a theorem.

(d) computational-only: an exact finite computation. The search

algorithm's completeness proof is (a), but its execution over a finite range is labelled (d).

Step 0: mandatory authoritative-page audit

I fetched the live page and its discussion thread through the Bright Data browser, rather than datacenter curl:

<https://www.erdosproblems.com/376>
<https://www.erdosproblems.com/forum/discuss/376>

The problem page says it was last edited 28 December 2025. It is marked OPEN, has 0 claimed proofs, and displays:

Interested in collaborating: None
Currently working on this problem: None
Likes this problem: None
This problem looks difficult: None
This problem looks tractable: None
The results could be formalisable: None
Working on formalising the results: None

The external-data section says the statement has been formalised and links OEIS A030979. The mandatory stop condition therefore did not apply.

Verbatim current statement

Are there infinitely many $n$ such that $\binom{2n}{n}$ is coprime to $105$?

The live page attaches [ErGr80,p.71] to the statement. Contrary to the stale tracker metadata supplied with the task, the live page says that Graham offered $1000 for a solution.

Results listed on the live page

The following are page attributions, checked against primary sources below.

Erdős, Graham, Ruzsa, and Straus proved that for any two odd primes

$p,q$, infinitely many $n$ have $\binom{2n}{n}$ coprime to $pq$.

By Kummer's theorem, the problem is equivalent to asking for infinitely

many $n$ whose digits lie in $\{0,1\}$ in base 3, in $\{0,1,2\}$ in base 5, and in $\{0,1,2,3\}$ in base 7.

These $n$ form OEIS A030979.
The page calls Bloom and Croot's 2025 result the best result in this

direction: for three sufficiently large primes, infinitely many $n$ have almost all digits below half the base in all three bases. In divisibility language, for every fixed $\epsilon>0$, the component of $\binom{2n}{n}$ supported on those primes can be at most $n^\epsilon$ infinitely often.

The problem appears as B33 in Guy and is discussed by Pomerance.

All three live comments

The thread contained exactly three comments:

Alfaiz, 26 Oct 2025: noted Graham's $1000 prize and pointed to

Pomerance's Section 4. The site says it was updated in response.

Terence Tao, 8 Jan 2026: pointed to Croot–Mousavi–Schmidt,

Mathematika 70 (2024), e12249. He accurately described it as producing unusually low $p$-adic multiplicities for a fixed set of small primes, but not zero. His edit notes that Bloom–Croot improves it.

Thomas Bloom, 8 Jan 2026: defined the $P$-supported component

$f_P(n)$ of $\binom{2n}{n}$, explained the change in quantifiers between Croot–Mousavi–Schmidt and Bloom–Croot, recorded the explicit three-base threshold 1094 in the latter, and suggested that a refined proof may give $f_P(n)\le \exp(O(\sqrt{\log n}))$. He explicitly distinguished this from the conjectural conclusion $f_P(n)=1$.

The site warns that comments are not verified. No comment claims a proof.

Mathematical normalization

For an odd prime $p$, Kummer's theorem says that

v_p\!\binom{2n}{n}

is the number of carries when adding $n+n$ in base $p$. Therefore

p\nmid\binom{2n}{n} \quad\Longleftrightarrow\quad \text{every base-\(p\) digit of \(n\) is at most \((p-1)/2\)}. \tag{1}

This is (b) as stated via Kummer. The checker independently evaluates the same valuations using the elementary Legendre formula

v_p(m!)=\sum_{j\ge1}\left\lfloor\frac{m}{p^j}\right\rfloor, \qquad v_p\!\binom{2n}{n}=v_p((2n)!)-2v_p(n!), \tag{2}

so its arithmetic does not rely on an implementation of Kummer's theorem.

Write

\mathcal S_b=\left\{n\ge0: \text{all base-\(b\) digits of \(n\) are at most \((b-1)/2\)}\right\}.

The target sequence, including the OEIS convention $0$, is exactly

\mathcal S_3\cap\mathcal S_5\cap\mathcal S_7. \tag{3}

Primary-source literature audit

I searched the exact problem, the three-base digit formulation, and the central-binomial-coefficient formulation. The sources below exist and say what is recorded here.

Established progress

(b) 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, prove the two-base/two-prime theorem. Their Theorem 1 is a more general restricted-digit statement.

(c) Carl Pomerance,

Divisors of the middle binomial coefficient, Amer. Math. Monthly 122 (2015), 636–644, gives the independence heuristic \[ A(x)\asymp x^\delta,\qquad \delta=\log_3 2+\log_5 3+\log_7 4-2 =0.0259503222734869\ldots, \tag{4} \] where $A(x)$ counts positive solutions through $x$. This is explicitly a heuristic, not a lower-bound theorem.

(b) E. Croot, H. Mousavi, and M. Schmidt,

arXiv:2201.11274, published in Mathematika 70 (2024), e12249, prove low multiplicity for sufficiently large primes, with the lower threshold depending on both the number of primes and $\epsilon$. Their theorem does not give multiplicity zero.

(b) T. Bloom and E. Croot,

arXiv:2509.02835, prove the page's “almost all digits” result with the base threshold independent of $\epsilon$. Their paper explicitly gives 1094 as a sufficient threshold for three bases. Thus it does not apply to $3,5,7$, and it still permits a positive number of bad digits.

(b) S. Burrell and H. Yu,

arXiv:1905.00832, published in J. Number Theory 226 (2021), 284–306, obtain (conditional on Schanuel) an upper bound of order $x^{0.026}$ for the number of solutions. An upper bound cannot prove that the count is unbounded.

(c) H. Yu,

arXiv:2004.05924, published in Ergodic Theory Dynam. Systems 43 (2023), gives a precise conditional route: a radial-projection interior conjecture for products of self-similar sets, together with Schanuel (or the needed $\mathbb Q$-linear independence of the logarithmic ratios), implies an affirmative answer. The paper expressly says the projection conjecture is not proved.

A January 2026 preprint, arXiv:2601.09510, was also screened. It studies the density of exponents $k$ for which a fixed odd $m$ fails to divide $\binom{2^{k+1}}{2^k}$; it does not supply solutions to (3).

I found no primary source proving either finiteness or infinitude. This agrees with the live OPEN status.

The old arXiv “solution” does not reach the target

The title and abstract of R. J. Betts, arXiv:1010.3070, claim infinitude for three fixed odd primes. The preprint exists, so omitting it without inspection would be a literature-search failure. Its application to this problem, however, has an elementary fatal mismatch.

The preprint defines a $(p,A)$-good integer to have all base-$p$ digits at most $A$. Its Theorem 3 assumes

p/2\le A,\quad q/2\le B,\quad r/2\le C. \tag{5}

For problem 376, (1) instead requires

A=(p-1)/2<p/2. \tag{6}

Already for $p=3$, (5) forces the integer $A\ge2$, while (6) requires $A=1$. Thus the theorem's stated hypotheses exclude the no-carry digit bounds. The later assertion that its theorem gives zero $p,q,r$-adic valuations does not follow. This diagnosis is (a) and is enough to show that this preprint does not establish the live statement; no judgment about every other argument in the preprint is needed.

Exact finite result

Define

A(X)=\#\{1\le n\le X:\gcd(\binom{2n}{n},105)=1\}.

The exhaustive computation proves the following finite statement:

(d) $A(10^{100})=14273$.

Including the OEIS convention $n=0$, the count is 14,274. The cumulative positive counts are:

| inclusive $X$ | $A(X)$ | |---:|---:| | $10^0$ | 1 | | $10^{10}$ | 14 | | $10^{20}$ | 61 | | $10^{30}$ | 134 | | $10^{40}$ | 175 | | $10^{50}$ | 357 | | $10^{60}$ | 698 | | $10^{70}$ | 1,373 | | $10^{80}$ | 4,833 | | $10^{90}$ | 10,214 | | $10^{100}$ | 14,273 |

Extension of the public OEIS table

On 2026-07-28, the A030979 b-file contained 1,374 values including zero and said it was complete through $10^{70}$. The search here independently finds exactly 1,374 values through that cutoff. Hashing the newline-separated decimal values gives, for both lists,

521a96dae129dd7a381c24b0df0a29cc7ad2ac91c59d2b43741d0c45f1f6734e

Relative to that public cutoff, the computation finds exactly 12,900 additional values in

10^{70}<n\le10^{100}. \tag{7}

This is a new finite extension relative to the cited public table, not a claim that no private or unindexed computation exists.

The first value in (7) is

\begin{split} n_0={}&41793835224715561827991803724419285037533255120531924813793252461031887. \end{split}

Its three representations are:

base 3:
10001100101111001101010110101111100010111111110100010100110000001011000111011011010010100000100000101001000000110100100000010101100001010010110011010

base 5:
101221111022002222011010002200220010000210021002102022212102110122020102121022222022002122020011010022

base 7:
300201130231000003223111213103200123023131300013331230301322112213013212000211031201

Every displayed digit is in the required alphabet, so this particular certificate is directly checkable. Formula (2) independently gives $v_3=v_5=v_7=0$.

The last solution not exceeding $10^{100}$ is

2584188430335227008294057915765677982067982325562479244352839872083286874869430708974022736877147525

Canonical hashes are:

all 14,274 values through 10^100:
802a10536581a896b9bb80c0cdc6987341d6382dc27b79738055a870cbc27676

the 12,900-value extension only:
0310d470ba1e61d82cf185ea89545c6a8441d6469fe0e313c6d21f3107cbdbfa

Exact search and completeness proof

The standalone checker is runs/erdos376_wave8z_reverify.py. It uses only the Python standard library.

Fix an inclusive upper bound $X$. For each $b\in\{3,5,7\}$, choose the least $k_b$ with $b^{k_b}>X$ and pad every base-$b$ expansion with leading zeroes to length $k_b$.

If an allowed most-significant prefix has numerical value $a$ and $r$ digits remain, all integers with this prefix lie in the cylinder

I_b(a,r)=[ab^r,(a+1)b^r-1]. \tag{8}

A search node stores one such cylinder for each base and their common intersection with $[0,X]$. It refines one cylinder by its allowed next digits:

\begin{array}{c|c} b&\text{children}\\ \hline 3&0,1\\ 5&0,1,2\\ 7&0,1,2,3. \end{array}

The child cylinders in (8) are pairwise disjoint and comprise exactly the numbers having an allowed next digit. A child is pruned only if its interval has empty intersection with the other two cylinders. Once the common intersection is a singleton, the program checks that integer from scratch in all three bases.

This proves completeness and uniqueness by induction on the number of unfixed digits (a):

every qualifying $n\le X$ begins in the three root cylinders;
at every split, it lies in exactly one allowed child;
that child's intersection cannot be pruned because it contains $n$;
the path reaches the singleton $\{n\}$;
disjoint children prevent duplicates.

Choosing a currently coarse cylinder only affects speed, not correctness. The checker actually performs the full search twice with different scoring rules—largest parent cylinder and largest prospective child cylinder—and asserts that the sorted lists agree.

Independent verification layers

The default run performs all of the following:

It linearly scans $0\le n\le200000$ using the Legendre valuations (2),

not the digit predicate, and compares this list with the prefix search.

It checks every full-search output both by direct base remainders and by

(2).

It recomputes the full range with the alternate search tree.
It checks that the independently computed prefix through $10^{70}$

matches the count and value-only hash of the OEIS b-file.

It asserts the recorded full count, endpoints, and hashes.

Run:

python3 runs/erdos376_wave8z_reverify.py

Use --print-solutions to emit the complete list. On this VM, Python 3.12 visited 3,671,764 nodes in the primary search and 3,514,812 in the alternate search. In the final clean run they took 15.97 and 18.12 seconds internally; the full process took 37.43 wall-seconds and used 26,012 KiB maximum resident memory.

What remains and the precise wall

The computation does not settle the problem. Any finite list, however long, is compatible both with eventual termination and with infinitude.

The standard mechanisms stall at two exact points:

No lower-bound/interior theorem at the critical fractal slice.

The three digit-set dimensions have excess \[ \log_3 2+\log_5 3+\log_7 4-2 =0.025950322\ldots>0. \] Independence heuristics turn this into the predicted growing count (4), but no unconditional theorem supplies even $A(X)\to\infty$. Han Yu's conditional reduction names a sufficient missing ingredient: the nonempty-interior radial-projection statement for the corresponding product Cantor set, together with the required logarithmic $\mathbb Q$-independence.

“Almost all digits” cannot be rounded to “all digits.”

Bloom–Croot applies only to bases at least 1094 in the three-base case, not $3,5,7$. More fundamentally, for every fixed $\epsilon>0$, a bound of $\epsilon\log n$ bad digits does not imply zero bad digits. One would need a uniform theorem allowing $\epsilon(n)<1/\log n$, or a separate exact digit-repair mechanism. Even the suggested $O(\sqrt{\log n})$ bad-digit bound remains far from zero.

Thus the concrete missing lemma is an unconditional positive lower bound for the three-way restricted-digit intersections at arbitrarily large scales (or an exact self-replicating construction). The finite prefix algorithm gives no such uniformity. Extending the cutoff further would add data but would not bridge this logical gap.

PARTIAL: exact exhaustive enumeration gives 14,273 positive solutions through $10^{100}$, extending the public $10^{70}$ table by 12,900 verified values, but supplies no uniform infinitude argument.

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