Erdős Problem #730

Erdős Problem #730: equal prime supports of neighboring central binomial coefficients

Exact transition criterion and finite-prime progress, 24 September 2026.

Statement and current scope

Set $B_n=\binom{2n}{n}$ and $S(n)=\{p:p\mid B_n\}$. Are there infinitely many distinct $n,m$ with $S(n)=S(m)$? The current discussion reports a solution, attributed to GPT Pro prompted by Price, including $\gg\sqrt x$ consecutive collisions up to $x$. We do not treat that report as a proof. The older local attempt supplies the basic valuation formula; here we derive a sharper exact local transition test, useful obstructions and an infinite finite-prime compatibility construction. The global infinitude remains unproved in this attempt.

The carry criterion

Counting prime powers in factorials gives \[ v_p(B_n)=\sum_{j\geq1} \left(\left\lfloor\frac{2n}{p^j}\right\rfloor -2\left\lfloor\frac n{p^j}\right\rfloor\right). \] Equivalently it counts carries in adding $n+n$ in base $p$: writing the digit sums as $s_p$ gives $(2s_p(n)-s_p(2n))/(p-1)$. For odd $p$, absence of all carries is equivalent to every base-$p$ digit of $n$ being at most $(p-1)/2$. Indeed a first carry occurs precisely at a digit exceeding this threshold. For $p=2$, $v_2(B_n)=s_2(n)>0$ whenever $n>0$, so two never enters or leaves the support.

Only the bridge factors matter

The exact ratio is \[ \frac{B_{n+1}}{B_n}=\frac{2(2n+1)}{n+1}. \tag{1} \] For an odd prime dividing neither bridge number $n+1$ nor $2n+1$, the valuation is unchanged. The bridge numbers are coprime, so the remaining cases separate.

If $p^a\parallel n+1$ and $u=(n+1)/p^a$, then \[ v_p(B_n)=a+v_p(B_u),\qquad v_p(B_{n+1})=v_p(B_u). \tag{2} \] To verify the first identity directly, the first $a$ floor differences are one, since $n=p^au-1$. For the higher differences, write $j=a+h$; they become $\lfloor(2u-1)/p^h\rfloor-2\lfloor(u-1)/p^h\rfloor$. Their sum is $v_p((2u-1)!/(u-1)!^2)=v_p((u/2)B_u)=v_p(B_u)$, because $p$ is odd and $p\nmid u$. The second identity follows from $1$. Thus $p$ disappears exactly when all digits of $u$ are at most $(p-1)/2$.

If instead $p^a\parallel2n+1$ and $u=(2n+1)/p^a$, write \[ n=p^a\frac{u-1}{2}+\frac{p^a-1}{2}. \] The lowest $a$ digits all equal $(p-1)/2$; doubling them creates no carries and sends no carry to the remaining digits. Hence \[ v_p(B_n)=v_p\left(B_{(u-1)/2}\right). \tag{3} \] Equation $1$ adds $a$ to this valuation. Thus $p$ enters exactly when all digits of $(u-1)/2$ are at most $(p-1)/2$, with $B_0=1$.

Equations $2$--$3$, checked only on prime factors of two integers, are a necessary and sufficient test for $S(n)=S(n+1)$. No scan over all primes up to $2n+2$ is needed.

Consequences and a certificate for $(87,88)$

If $p>\sqrt{2n+1}$ divides $2n+1$, it occurs to exponent one and its quotient $u$ is less than $p$. Then $(u-1)/2<(p-1)/2$, so $3$ says that $p$ enters. Such a large prime divisor is therefore forbidden in a collision. Likewise, if an odd $p>\sqrt{2(n+1)}$ divides $n+1$, its quotient is $u<p/2$ and $2$ says that $p$ disappears. Pure odd prime powers in either bridge number are also ruled out by these criteria.

For $n=87$, the bridge factorizations are $88=2^3\cdot11$ and $175=5^2\cdot7$. For the disappearing candidate $11$, the quotient $u=8$ has a digit exceeding $5$, so $11$ remains. For $5$, $(175/25-1)/2=3$ has a digit exceeding $2$, so $5$ was already present. For $7$, $(175/7-1)/2=12$ has base-seven digits $15$, including a digit exceeding $3$, so $7$ was already present. Two is always present and every other prime is unchanged. This proves the collision without factoring either huge binomial coefficient.

An infinite finite-coordinate statement

Fix any bound $P\geq3$ and let $Q$ be the product of $p^2$ over odd primes $p\leq P$. For every positive $n\equiv-2\pmod Q$, and each such $p$, \[ n\bmod p^2=p^2-2\geq p^2/2,\qquad (n+1)\bmod p^2=p^2-1\geq p^2/2. \] The $j=2$ term in the valuation formula is one for both $n$ and $n+1$. Thus every prime at most $P$ divides both $B_n$ and $B_{n+1}$. This gives an infinite progression on which all these prime-support coordinates agree, with natural density $1/Q$. The cutoff is fixed before $n$ grows; primes above it remain uncontrolled. Consequently a sequence of these statements for increasing $P$ does not prove a global collision.

Remaining gap and sources

Attempt status: unresolved. The exact transition test, two large-prime obstructions, explicit collision and finite-prime infinite families are proved. The missing step is uniform control of every prime factor of the bridge numbers for an infinite family of $n$; the reported quadratic-family/digit estimates are not reconstructed. Sources: https://www.erdosproblems.com/730; https://www.erdosproblems.com/forum/discuss/730; the linked proof is https://www.overleaf.com/read/gpttrsmhbhbk. No novelty, global resolution, or local formal verification is claimed.

COMPLETION ESTIMATE

COMPLETION: 40%

Are there infinitely many pairs of integers $n\neq m$ such that $\binom{2n}{n}$ and $\binom{2m}{m}$ have the same set of prime divisors? A problem of Erdős, Graham, Ruzsa, and Straus [EGRS75], who believed there is 'no doubt' that the answer is yes. For example $(87,88)$ and $(607,608)$. Those $n$ such that there exists some suitable $m>n$ are listed as A129515 in the OEIS. A triple of such $n$ for which $\binom{2n}{n}$ all share the same set of prime divisors is $(10003,10004,10005)$. It is not known whether there are such pairs of the shape $(n,n+k)$ for every $k\geq 1$. References [EGRS75] Erdős, P. and Graham, R. L. and Ruzsa, I. Z. and Straus, E. G., On the prime factors of $(\sp{2n}\sb{n})$ . Math. Comp. $1975$, 83-92.

1) FORMAL RESTATEMENT.

For each integer $n\ge 1$, define the  prime divisor set  \[ S(n) := \{\,p\text{ prime}: p\mid \binom{2n}{n}\,\}. \] Question: are there infinitely many pairs of integers $(n,m)$ with $n\neq m$ such that $S(n)=S(m)$?

Conventions/edge cases:

• $\binom{2n}{n}=(2n)!/(n!)^2\in\mathbb Z$ for $n\ge 0$; we restrict to $n\ge 1$.
• "Same set of prime divisors" means equality of sets $S(n)=S(m)$ (multiplicities ignored).

Stress points: $S(n)$ always contains all primes in $(n,2n]$ (Lemma 730.1), so equality forces strong constraints relating prime intervals.

2) QUICK LITERATURE/CONTEXT CHECK.

The problem statement itself records examples $(87,88)$ and $(607,608)$ and a triple $(10003,10004,10005)$, and notes the related OEIS entry A129515. I do not rely on any additional literature claims beyond what is written above.

3) ATTACK PLAN.

Proof-track ideas.

• Use $p$-adic valuations of $\binom{2n}{n}$ to translate membership of $p$ in $S(n)$ into a digit/carry condition (Lemma 730.2 and Corollary 730.3). Try to build infinite families $n\neq m$ with identical carry patterns across all primes $p\le 2\max\{n,m\}$.
• Focus on the empirically frequent consecutive collisions $S(n)=S(n+1)$ and analyze the ratio $\binom{2(n+1)}{n+1}/\binom{2n}{n} = \frac{2(2n+1)}{n+1}$ to derive necessary/sufficient conditions for equal prime sets.

Disproof-track ideas.

• Try to show $S(n)$ changes infinitely often because of primes in $(n,2n]$; but this does not preclude collisions, and examples suggest collisions exist.

Best path here: develop exact criteria for $p\mid\binom{2n}{n}$ and document computational "reality checks".

4) WORK.

Fast reality check (computation). Using a direct Legendre-formula computation of $v_p\left(\binom{2n}{n}\right)$ for primes $p\le 2n$:

• Verified the example pair $(87,88)$: both have \[ S(87)=S(88)=\{2,3,5,7,11,13,19,23,31,47,53,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173\}. \]
• Exhaustive search for $1\le n\le 5000$ found $39$ collisions of prime divisor sets, all of the form $S(n)=S(n+1)$ (consecutive pairs). The first few are \[(87,88),(199,200),(237,238),(467,468),(607,608),(967,968),\dots\] and the last few in this range are \[(4287,4288),(4360,4361),(4479,4480),(4927,4928),(4987,4988). \] No set occurred with multiplicity $\ge 3$ for $n\le 5000$.

Lemma 730.1 (Large primes always divide). Let $n\ge 1$ and let $p$ be a prime with $n<p\le 2n$. Then $p\in S(n)$, and moreover \[v_p\!\left(\binom{2n}{n}\right)=1.\]

Proof. Write $\binom{2n}{n}=(2n)!/(n!)^2$. Since $p>n$, the factorial $n!$ contains no multiple of $p$, hence $v_p(n!)=0$. Since $p\le 2n<2p$, the factorial $(2n)!$ contains exactly one multiple of $p$ (namely $p$ itself) and no multiple of $p^2$, hence $v_p((2n)!)=1$. Therefore \[ v_p\!\left(\binom{2n}{n}\right)=v_p((2n)!)-2v_p(n!)=1-0=1, \] so in particular $p$ divides $\binom{2n}{n}$ and $p\in S(n)$. $\square$

Lemma 730.2 (Legendre valuation formula for $\binom{2n}{n}$). For any integer $n\ge 1$ and any prime $p$, \[ v_p\!\left(\binom{2n}{n}\right)=\sum_{k\ge 1}\left(\lfloor\frac{2n}{p^k}\rfloor -2\lfloor\frac{n}{p^k}\rfloor\right). \]

Proof. First, for any integer $N\ge 1$, we prove Legendre's formula \[ v_p(N!)=\sum_{k\ge 1}\lfloor\frac{N}{p^k}\rfloor. \] Indeed, among the integers $1,2,\dots,N$, exactly $\lfloor N/p\rfloor$ are divisible by $p$, exactly $\lfloor N/p^2\rfloor$ are divisible by $p^2$, etc. Each multiple of $p^k$ contributes at least one factor of $p$ to $N!$, and counting these contributions with multiplicity gives precisely the sum above.

Applying Legendre's formula to $N=2n$ and $N=n$ and using $\binom{2n}{n}=(2n)!/(n!)^2$ yields \[ v_p\!\left(\binom{2n}{n}\right)=v_p((2n)!)-2v_p(n!) =\sum_{k\ge 1}\lfloor\frac{2n}{p^k}\rfloor-2\sum_{k\ge 1}\lfloor\frac{n}{p^k}\rfloor, \] which is the claimed identity. $\square$

Corollary 730.3 (Carry criterion via base-$p$ digit sums). Let $s_p(N)$ denote the sum of the base-$p$ digits of a nonnegative integer $N$. Then for $n\ge 1$, \[ v_p\!\left(\binom{2n}{n}\right)=\frac{2s_p(n)-s_p(2n)}{p-1}. \] In particular, $p\in S(n)$ if and only if adding $n+n$ in base $p$ produces at least one carry.

Proof. Write $n$ in base $p$ as $n=\sum_{j\ge 0} a_j p^j$ with $0\le a_j\le p-1$ and only finitely many nonzero digits. Then \[ \lfloor \frac{n}{p^k}\rfloor = \sum_{j\ge k} a_j p^{j-k}. \] Summing over $k\ge 1$ gives \[ \sum_{k\ge 1}\lfloor\frac{n}{p^k}\rfloor =\sum_{k\ge 1}\sum_{j\ge k} a_j p^{j-k} =\sum_{j\ge 1} a_j \sum_{k=1}^{j} p^{j-k} =\sum_{j\ge 1} a_j\,(p^{j-1}+\cdots+p+1). \] The inner geometric sum equals $(p^j-1)/(p-1)$, so \[ \sum_{k\ge 1}\lfloor\frac{n}{p^k}\rfloor =\frac{1}{p-1}\sum_{j\ge 1} a_j(p^j-1) =\frac{1}{p-1}\left(\sum_{j\ge 0} a_j p^j - \sum_{j\ge 0} a_j\right) =\frac{n - s_p(n)}{p-1}. \] By Lemma 730.2, \[ v_p\!\left(\binom{2n}{n}\right)=\sum_{k\ge 1}\left(\lfloor\frac{2n}{p^k}\rfloor -2\lfloor\frac{n}{p^k}\rfloor\right) =\frac{2n-s_p(2n)}{p-1}-2\frac{n-s_p(n)}{p-1} =\frac{2s_p(n)-s_p(2n)}{p-1}. \] Now, when adding $n+n$ in base $p$, the digit-sum identity \[ s_p(2n)=2s_p(n) - (p-1)\cdot(\#\text{ carries}) \] holds because each carry reduces the digit sum by exactly $p-1$ (a carry replaces a contribution $a+b\ge p$ by $(a+b-p)$ in the current digit and increases the next digit by $1$, net change $-(p-1)$). Therefore $2s_p(n)-s_p(2n)$ is a nonnegative multiple of $p-1$ equal to $(p-1)\cdot(\#\text{ carries})$, proving the stated formula and the carry criterion. $\square$

5) VERIFICATION.

• Lemma 730.1: checked the valuation count carefully: $p\le 2n<2p$ ensures exactly one multiple of $p$ and no multiple of $p^2$ occurs in $(2n)!$.
• Lemma 730.2: Legendre's formula proof counts multiples of $p^k$ with multiplicity and uses finite support (since $p^k>2n$ gives zero terms).
• Corollary 730.3: the digit-sum computation is a direct evaluation of the floor-sum; the carry effect on digit sum is verified locally per digit.
• Computational check: the reported pairs and sets were produced by exact integer floor computations of $v_p$ (no probabilistic primality).

6) FINAL. UNRESOLVED

(i) Strongest proved partial result: exact characterizations of $S(n)$ via valuations (Lemma 730.2) and carries (Corollary 730.3), and the unconditional inclusion $(n,2n]\cap\mathbb P\subseteq S(n)$ with $v_p=1$ (Lemma 730.1). Computation found 39 collisions for $n\le 5000$, all consecutive.

(ii) First gap: prove (or disprove) that there are infinitely many distinct $n\neq m$ with $S(n)=S(m)$ (even the special case $S(n)=S(n+1)$ for infinitely many $n$).

(iii) Top 3 next moves:

1. Analyze the equality condition $S(n)=S(n+1)$ using $\binom{2(n+1)}{n+1}=\binom{2n}{n}\cdot \frac{2(2n+1)}{n+1}$, aiming for a clean necessary-and-sufficient condition in terms of carries/valuations for primes dividing $2(2n+1)$ and $n+1$.
2. Try to construct parametric families of $n$ where, for every prime $p\le 2n+2$, the carry pattern for $n$ and $n+1$ in base $p$ is identical (e.g., impose congruences on $n$ modulo many prime powers and check stability).
3. Extend the computation to larger ranges with additional statistics (e.g., gap distribution between consecutive collisions, and whether all collisions continue to be consecutive).

(iv) Minimal counterexample structure (if the answer were "no"): there would exist $N$ such that for all $n\ge N$ and all $m\neq n$, the sets $S(n)$ are pairwise distinct. In particular, beyond $N$ there would be no consecutive collisions, so each step $n\mapsto n+1$ would introduce or delete at least one prime divisor, despite Lemma 730.1 forcing large blocks of primes in $(n,2n]$.