Erdős Problem #731

Erdős Problem 731 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

Find some reasonable function $f(n)$ such that, for almost all integers $n$, the least integer $m$ such that $m\nmid \binom{2n}{n}$ satisfies\[m\sim f(n).\] A problem of Erdős, Graham, Ruzsa, and Straus [EGRS75], who say it is 'not hard to show that', for almost all $n$, the minimal such $m$ satisfies\[m=\exp((\log n)^{1/2+o(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 \[ M(n):=\min\{\,m\in\mathbb Z_{\ge 2}:\; m\nmid \binom{2n}{n}\,\}. \] Problem: find a "reasonable" function $f(n)$ such that \[ M(n)\sim f(n)\quad\text{for almost all }n, \] where "almost all" means: for $x\to\infty$, the proportion of $n\le x$ for which the asymptotic holds tends to $1$.

2) QUICK LITERATURE/CONTEXT CHECK.

The problem statement records that Erdős--Graham--Ruzsa--Straus say it is "not hard" to show $M(n)=\exp((\log n)^{1/2+o(1)})$ for almost all $n$. I do not use any external results beyond what is explicitly stated.

3) ATTACK PLAN.

Proof-track.

• First reduce $M(n)$ to a minimum over prime powers using an elementary divisibility argument (Lemma 731.1), then express it in terms of $p$-adic valuations of $\binom{2n}{n}$ (Lemma 731.2).
• The remaining analytic difficulty is to understand, for typical $n$, the smallest prime power that fails to divide $\binom{2n}{n}$.

Disproof-track.

• Try to falsify the quoted asymptotic by explicit computation for growing $n$ (sanity check only; cannot disprove an "almost all" statement with finite computation).

4) WORK.

Fast reality check (computation). For $1\le n\le 30$, the values of $M(n)$ computed via the prime-power formula in Lemma 731.2 are: \[ \begin{array}{c|cccccccccc} n&1&2&3&4&5&6&7&8&9&10\\\hline M(n)&4&4&3&3&5&5&5&4&3&3 \end{array} \quad \begin{array}{c|cccccccccc} n&11&12&13&14&15&16&17&18&19&20\\\hline M(n)&5&3&3&7&7&4&7&8&9&8 \end{array} \] (all are prime powers, as Lemma 731.1 predicts).

For $1\le n\le 10000$, the same computation gave:

• $\min_{n\le 10000} M(n)=3$ and $\max_{n\le 10000} M(n)=121$ (attained at $n=5534$).
• Most frequent values among $n\le 10000$ were $M(n)=13,7,11,9,17,19,\dots$.
• Sample: $M(100)=7$, $M(1000)=3$, $M(5000)=17$, $M(10000)=25$.

Lemma 731.1 (The least nondivisor is a prime power). Let $N\ge 1$ be an integer and define \[ \mu(N):=\min\{\,m\in\mathbb Z_{\ge 2}:\; m\nmid N\,\}. \] Then $\mu(N)=q^a$ for some prime $q$ and integer $a\ge 1$.

Proof. Let $m=\mu(N)$ and write the prime factorization $m=\prod_{j=1}^r q_j^{a_j}$ with distinct primes $q_j$ and exponents $a_j\ge 1$.

Suppose for contradiction that $r\ge 2$. Fix $q_1$ and set $u=q_1^{a_1}$ and $v=m/u=\prod_{j=2}^r q_j^{a_j}$. Then $u\ge 2$, $v\ge 2$, $u<m$ and $v<m$, and $\gcd(u,v)=1$.

By minimality of $m$, every integer $\ge 2$ and $<m$ divides $N$, hence in particular $u\mid N$ and $v\mid N$. Since $\gcd(u,v)=1$, the divisibility $uv\mid N$ follows. But $uv=m$, contradicting that $m\nmid N$.

Therefore $r=1$ and $m$ is a prime power. $\square$

Lemma 731.2 (Prime-power formula for $M(n)$). For each $n\ge 1$, \[ M(n)=\min_{p\le 2n\atop p\text{ prime}} p^{\,v_p\left(\binom{2n}{n}\right)+1}. \] Equivalently, the least $m\ge 2$ that fails to divide $\binom{2n}{n}$ is the smallest prime power strictly exceeding the $p$-part of $\binom{2n}{n}$.

Proof. Set $N=\binom{2n}{n}$ and write its prime factorization as $N=\prod_p p^{v_p(N)}$.

For each prime $p$, the largest power of $p$ dividing $N$ is $p^{v_p(N)}$, so the smallest power of $p$ that does not divide $N$ is $p^{v_p(N)+1}$.

By Lemma 731.1, $M(n)=\mu(N)$ is a prime power $q^a$. Since $q^a\nmid N$ but $q^{a-1}\mid N$, we have $a=v_q(N)+1$, so $M(n)=q^{v_q(N)+1}$ for some prime $q$. Minimizing over $q$ gives the stated formula. $\square$

5) VERIFICATION.

• Lemma 731.1: checked the coprime factor step: if $u\mid N$ and $v\mid N$ with $\gcd(u,v)=1$ then $uv\mid N$.
• Lemma 731.2: verified both directions: any prime power $p^{v_p+1}$ does not divide $N$, and any minimal nondivisor must equal such a prime power.
• Computations were done using exact integer floor sums for $v_p\left(\binom{2n}{n}\right)$ (Legendre), then applying Lemma 731.2.

6) FINAL. UNRESOLVED

(i) Strongest proved partial result: an exact reduction \[M(n)=\min_{p\le 2n} p^{v_p\left(\binom{2n}{n}\right)+1}\] (Lemmas 731.1--731.2), together with computed values up to $n=10000$ (e.g., $3\le M(n)\le 121$ in that range).

(ii) First gap: prove an asymptotic formula for $M(n)$ for almost all $n$ (e.g., justify or refute $M(n)=\exp((\log n)^{1/2+o(1)})$) from the valuation/carry structure of $\binom{2n}{n}$.

(iii) Top 3 next moves:

1. Translate $v_p\left(\binom{2n}{n}\right)$ into base-$p$ carry statistics (Corollary 730.3) and study, for "typical" $n$, the smallest prime $p$ with zero carries in $n+n$ in base $p$ (which would force $p\nmid\binom{2n}{n}$ and hence $M(n)\le p$).
2. Prove upper/lower bounds on $M(n)$ for a density-one set of $n$ by showing that for most $n$ there exists a prime $p$ in a controllable range for which doubling $n$ in base $p$ has no carries (or at most a bounded number, controlling $v_p$).
3. Extend computation to larger $n$ (e.g. $10^6$) to better guess the correct "reasonable" $f(n)$: track $\log M(n)$ versus $\sqrt{\log n}$ and record fluctuations.

(iv) Minimal counterexample structure (to any proposed $f(n)$): a set of integers $n$ of positive lower density along which $M(n)$ systematically deviates from $f(n)$, which (by Lemma 731.2) would correspond to atypical carry/valuation behavior across all primes $p$ in the range where the minimum is expected to occur.

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.

Find some reasonable function $f(n)$ such that, for almost all integers $n$, the least integer $m$ such that $m\nmid \binom{2n}{n}$ satisfies\[m\sim f(n).\] A problem of Erdős, Graham, Ruzsa, and Straus [EGRS75], who say it is 'not hard to show that', for almost all $n$, the minimal such $m$ satisfies\[m=\exp((\log n)^{1/2+o(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 \[ M(n):=\min\{\,m\in\mathbb Z_{\ge 2}:\; m\nmid \binom{2n}{n}\,\}. \] Problem: find a "reasonable" function $f(n)$ such that \[ M(n)\sim f(n)\quad\text{for almost all }n, \] where "almost all" means: for $x\to\infty$, the proportion of $n\le x$ for which the asymptotic holds tends to $1$.

2) QUICK LITERATURE/CONTEXT CHECK.

The problem statement records that Erdős--Graham--Ruzsa--Straus say it is "not hard" to show $M(n)=\exp((\log n)^{1/2+o(1)})$ for almost all $n$. I do not use any external results beyond what is explicitly stated.

3) ATTACK PLAN.

Proof-track.

• First reduce $M(n)$ to a minimum over prime powers using an elementary divisibility argument (Lemma 731.1), then express it in terms of $p$-adic valuations of $\binom{2n}{n}$ (Lemma 731.2).
• The remaining analytic difficulty is to understand, for typical $n$, the smallest prime power that fails to divide $\binom{2n}{n}$.

Disproof-track.

• Try to falsify the quoted asymptotic by explicit computation for growing $n$ (sanity check only; cannot disprove an "almost all" statement with finite computation).

4) WORK.

Fast reality check (computation). For $1\le n\le 30$, the values of $M(n)$ computed via the prime-power formula in Lemma 731.2 are: \[ \begin{array}{c|cccccccccc} n&1&2&3&4&5&6&7&8&9&10\\\hline M(n)&4&4&3&3&5&5&5&4&3&3 \end{array} \quad \begin{array}{c|cccccccccc} n&11&12&13&14&15&16&17&18&19&20\\\hline M(n)&5&3&3&7&7&4&7&8&9&8 \end{array} \] (all are prime powers, as Lemma 731.1 predicts).

For $1\le n\le 10000$, the same computation gave:

• $\min_{n\le 10000} M(n)=3$ and $\max_{n\le 10000} M(n)=121$ (attained at $n=5534$).
• Most frequent values among $n\le 10000$ were $M(n)=13,7,11,9,17,19,\dots$.
• Sample: $M(100)=7$, $M(1000)=3$, $M(5000)=17$, $M(10000)=25$.

Lemma 731.1 (The least nondivisor is a prime power). Let $N\ge 1$ be an integer and define \[ \mu(N):=\min\{\,m\in\mathbb Z_{\ge 2}:\; m\nmid N\,\}. \] Then $\mu(N)=q^a$ for some prime $q$ and integer $a\ge 1$.

Proof. Let $m=\mu(N)$ and write the prime factorization $m=\prod_{j=1}^r q_j^{a_j}$ with distinct primes $q_j$ and exponents $a_j\ge 1$.

Suppose for contradiction that $r\ge 2$. Fix $q_1$ and set $u=q_1^{a_1}$ and $v=m/u=\prod_{j=2}^r q_j^{a_j}$. Then $u\ge 2$, $v\ge 2$, $u<m$ and $v<m$, and $\gcd(u,v)=1$.

By minimality of $m$, every integer $\ge 2$ and $<m$ divides $N$, hence in particular $u\mid N$ and $v\mid N$. Since $\gcd(u,v)=1$, the divisibility $uv\mid N$ follows. But $uv=m$, contradicting that $m\nmid N$.

Therefore $r=1$ and $m$ is a prime power. $\square$

Lemma 731.2 (Prime-power formula for $M(n)$). For each $n\ge 1$, \[ M(n)=\min_{p\le 2n\atop p\text{ prime}} p^{\,v_p\left(\binom{2n}{n}\right)+1}. \] Equivalently, the least $m\ge 2$ that fails to divide $\binom{2n}{n}$ is the smallest prime power strictly exceeding the $p$-part of $\binom{2n}{n}$.

Proof. Set $N=\binom{2n}{n}$ and write its prime factorization as $N=\prod_p p^{v_p(N)}$.

For each prime $p$, the largest power of $p$ dividing $N$ is $p^{v_p(N)}$, so the smallest power of $p$ that does not divide $N$ is $p^{v_p(N)+1}$.

By Lemma 731.1, $M(n)=\mu(N)$ is a prime power $q^a$. Since $q^a\nmid N$ but $q^{a-1}\mid N$, we have $a=v_q(N)+1$, so $M(n)=q^{v_q(N)+1}$ for some prime $q$. Minimizing over $q$ gives the stated formula. $\square$

5) VERIFICATION.

• Lemma 731.1: checked the coprime factor step: if $u\mid N$ and $v\mid N$ with $\gcd(u,v)=1$ then $uv\mid N$.
• Lemma 731.2: verified both directions: any prime power $p^{v_p+1}$ does not divide $N$, and any minimal nondivisor must equal such a prime power.
• Computations were done using exact integer floor sums for $v_p\left(\binom{2n}{n}\right)$ (Legendre), then applying Lemma 731.2.

6) FINAL. UNRESOLVED

(i) Strongest proved partial result: an exact reduction \[M(n)=\min_{p\le 2n} p^{v_p\left(\binom{2n}{n}\right)+1}\] (Lemmas 731.1--731.2), together with computed values up to $n=10000$ (e.g., $3\le M(n)\le 121$ in that range).

(ii) First gap: prove an asymptotic formula for $M(n)$ for almost all $n$ (e.g., justify or refute $M(n)=\exp((\log n)^{1/2+o(1)})$) from the valuation/carry structure of $\binom{2n}{n}$.

(iii) Top 3 next moves:

1. Translate $v_p\left(\binom{2n}{n}\right)$ into base-$p$ carry statistics (Corollary 730.3) and study, for "typical" $n$, the smallest prime $p$ with zero carries in $n+n$ in base $p$ (which would force $p\nmid\binom{2n}{n}$ and hence $M(n)\le p$).
2. Prove upper/lower bounds on $M(n)$ for a density-one set of $n$ by showing that for most $n$ there exists a prime $p$ in a controllable range for which doubling $n$ in base $p$ has no carries (or at most a bounded number, controlling $v_p$).
3. Extend computation to larger $n$ (e.g. $10^6$) to better guess the correct "reasonable" $f(n)$: track $\log M(n)$ versus $\sqrt{\log n}$ and record fluctuations.

(iv) Minimal counterexample structure (to any proposed $f(n)$): a set of integers $n$ of positive lower density along which $M(n)$ systematically deviates from $f(n)$, which (by Lemma 731.2) would correspond to atypical carry/valuation behavior across all primes $p$ in the range where the minimum is expected to occur.