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

Erdős problem 961 — live check, reduction, exact small cases, and a certified construction

Access date: 2026-07-28 UTC.

Claim labels used throughout:

(a) elementary-rigorous: proved below from elementary facts.
(b) rigorous-modulo-named-theorem: the dependence is named explicitly.
(c) plausible/structural-unverified: heuristic or an unverified extrapolation.
(d) computational-only: established by the accompanying deterministic computation, not by a separately written formal proof.

0. Mandatory live-page gate

The live page was retrieved through the Bright Data browser route, not datacenter curl: Erdős problem 961. The rendered discussion page was separately opened at the problem 961 discussion. (d: live-page observation)

The page's exact current statement is:

Let $f(k)$ be the minimal $n$ such that every set of $n$ consecutive integers $>k$ contains an integer divisible by a prime $>k$. Estimate $f(k)$.

The live page showed all of the following. (d: live-page observation)

Status: OPEN; last edited 03 April 2026.
Claimed proofs: 0.
“Currently working on this problem”: None.
“Interested in collaborating”: None.
One comment, by seewoo5 on 29 January 2026. It asks what “this” means in the asserted equivalence with problem 683, and specifically whether the conjectural polylogarithmic bound here corresponds to the conjectural $e^{c\sqrt{k}}$ binomial-coefficient bound there. It is a clarification question for a formal-conjectures pull request, not a result, claimed proof, or current-work marker.
The page lists OEIS A213253 and says the statement has been formalised.

Therefore the mandatory stop condition did not trigger.

The known results stated on the live page, treated as ground truth, are: (b: the cited theorems on the live page)

f(k)\leq k

by Sylvester and Schur;

f(k)<3\frac{k}{\log k}

by Erdős; and

f(k)\ll \frac{\log\log\log k}{\log\log k}\frac{k}{\log k}

by Jutila and by Ramachandra–Shorey. The page conjecturally expects

f(k)\ll(\log k)^{O(1)}

and says this is essentially equivalent to problem 683. (c: the conjectural bound; b: the stated relationship is analysed rigorously below)

1. Outcome

This run does not solve the asymptotic problem. It does produce four verifiable pieces of progress:

A precise elementary identity reducing the question to uniform largest-prime-factor bounds for binomial coefficients, including both quantitative directions. In particular,

\[ f(k)\ll(\log k)^A \quad\Longleftrightarrow_{\text{quantitatively}}\quad P^+\!\binom Nm\geq \min\!\left(N-m+1,\exp(c\,m^{1/A})\right) \] in the ranges and with the constants made precise in Section 3. For $A=2$, this explains exactly the $e^{c\sqrt m}$ comment on the live page. (a)

A deterministic Størmer–Pell enumeration independently recovers the exact table

\[ f(1)=1,\quad f(2)=2,\quad f(3)=f(4)=3,\quad f(k)=4\ (5\leq k\leq12),\quad f(k)=6\ (13\leq k\leq40). \] Completeness is conditional only on the named Carmichael–Lehmer primitive-divisor cutoff used in the published algorithms; all arithmetic is recomputed from scratch. (b+d)

Consecutive-prime certificates

\[ p=1\,294\,268\,491,\qquad q=1\,294\,268\,779,\qquad q-p=288 \] give the explicit construction \[ f(647\,134\,389)\geq288. \] The checker trial-divides both endpoints and completely factors all 287 interior integers. (d, using the elementary lemma in Section 4)

The published witness $1330,\ldots,1344$ is independently factored; its largest prime factor is $223$. Hence

\[ f(k)\geq16\qquad(223\leq k\leq1329), \] in particular $f(269)\geq16$. (a+d)

The standalone checker is runs/erdos961_wavew025_verify.py. Its SHA-256 is

3cf74b9d88d1441c76280fb9d6c69e5d35c20fdb1da0d951f86229bb6cf28b6a

2. Literature audit

2.1 Sources checked

The following sources were found and their stated claims were checked against the actual paper or an author/journal copy.

P. Erdős, “On consecutive integers”, Nieuw Arch. Wisk. 3 (1955), 124–128. The paper defines this $f(k)$, proves a constant multiple of $k/\log k$, derives the Rankin prime-gap lower bound, and says the Cramér heuristic suggests order $(\log k)^2$. (b: contents checked in the primary PDF)
K. Ramachandra and T. N. Shorey, “On gaps between numbers with a large prime factor”, Acta Arith. 24 (1973), 99–111. The journal record, DOI, authors, volume, and pages were verified. (d: bibliographic verification; b for the theorem as cited by the live page and later survey)
T. N. Shorey, “On gaps between numbers with a large prime factor II”, Acta Arith. 25 (1974), 365–373. The journal record and paper were verified. (d: bibliographic verification; b for the theorem as cited by the live page and later survey)
T. N. Shorey and R. Tijdeman, “Prime factors of arithmetic progressions and binomial coefficients”, survey/chapter, especially §1.2. It records the Rankin lower bound, the sequence of upper-bound improvements, and the $(\log k)^2$ expectation. (b: contents checked in the authors' PDF)
M. Bauer and M. A. Bennett, “Prime factors of consecutive integers”, Math. Comp. 77 (2008), 2455–2459, DOI 10.1090/S0025-5718-08-02134-0. It gives the Pell/primitive-divisor algorithm and proves all exact values through $k=178$. (b: contents checked in the primary PDF)
F. Najman, “Large strings of consecutive smooth integers”, arXiv:1108.3710, Arch. Math. 97 (2011), 319–324, DOI 10.1007/s00013-011-0301-y. It improves the Bauer–Bennett computation with compact Pell representations and proves all exact values through $k=268$. (b: contents checked in the arXiv/author PDF)
OEIS A213253 contains the same exact table through 268 and links to the above papers. (d: database cross-check, not used as a proof)

The full text of M. Jutila, “On numbers with a large prime factor II,” J. Indian Math. Soc. 38 (1974), 125–130, was not located in an openly searchable primary scan during this run. Its bibliographic existence was verified in multiple journal bibliographies, and the bound attributed to it was cross-checked in the Shorey–Tijdeman survey and the later papers. I therefore do not attribute any finer statement to Jutila than what the live page and those checked sources say. (d: honest source-access limitation)

Targeted searches found no later paper claiming an improved asymptotic for this exact $f(k)$, and no later exact table beyond Najman's $k=268$. This is a search result, not a proof that no such literature exists. (c)

A very recent adjacent paper, W. van Doorn and Q. Tang, “Consecutive integers free of certain prime factors”, studies a block whose product avoids primes in $(k,2k)$. That condition allows prime factors $>2k$, so its theorem does not imply that the block is $k$-smooth and does not directly improve problem 961. (a: non-implication from the definitions; b: description of their stated theorem)

2.2 Published exact state

Combining Bauer–Bennett and Najman gives the published exact table (b):

| $k$ | $f(k)$ | |---:|---:| | $1$ | $1$ | | $2$ | $2$ | | $3$–$4$ | $3$ | | $5$–$12$ | $4$ | | $13$–$40$ | $6$ | | $41$–$46$ | $7$ | | $47$–$58$ | $8$ | | $59$–$60$ | $9$ | | $61$–$113$ | $14$ | | $114$ | $13$ | | $115$–$150$ | $12$ | | $151$–$222$ | $14$ | | $223$–$268$ | $16$ |

The drop $f(113)=14$, $f(114)=13$, $f(115)=12$ shows that $f$ is not monotone. (b: immediate consequence of the published table)

3. Exact binomial-coefficient reduction

Write $P^+(r)$ for the largest prime factor of $r$, with $P^+(1)=1$, and

\Pi(x,m)=x(x+1)\cdots(x+m-1).

Lemma 3.1

For positive integers $m\leq k$ and $x$,

P^+(\Pi(x,m))\leq k \quad\Longleftrightarrow\quad P^+\!\binom{x+m-1}{m}\leq k. \tag{3.1}

Proof. The identity

\Pi(x,m)=m!\binom{x+m-1}{m}

holds in the integers. Since $m\leq k$, every prime factor of $m!$ is at most $k$. Thus either side of (3.1), together with this identity, implies the other. (a)

Sylvester–Schur gives $f(k)\leq k$, so (3.1) yields the exact reformulation

f(k)=\min\left\{1\leq m\leq k: \ P^+\!\binom{x+m-1}{m}>k\ \text{for every }x>k \right\}. \tag{3.2}

(b: elementary Lemma 3.1 plus the named Sylvester–Schur theorem)

Proposition 3.2: binomial lower bound implies an $f$-upper bound

Suppose an increasing function $H$ satisfies, for all sufficiently large $m$ and every $N\geq2m$,

P^+\!\binom Nm\geq\min(N-m+1,H(m)). \tag{3.3}

Then, for all sufficiently large $k$,

f(k)\leq \min\{m\leq k:H(m)>k\}. \tag{3.4}

Proof. Choose $m\leq k$ with $H(m)>k$, and take any $x>k$. Put $N=x+m-1$. Since $x>k\geq m$, $N\geq2m$. Both $x=N-m+1$ and $H(m)$ exceed $k$, so (3.3) gives

P^+\!\binom{x+m-1}{m}>k.

Now apply (3.1). (a)

Consequences:

The conjectured bound in problem 683 with $H(m)=m^{1+c}$ would give

\[ f(k)\ll k^{1/(1+c)}. \] (a)

The heuristic $H(m)=e^{c\sqrt m}$ would give

\[ f(k)\ll(\log k)^2. \] (a)

Proposition 3.3: a polylogarithmic $f$-bound implies a binomial lower bound

Conversely, suppose that for some $A,C>0$,

f(q)\leq C(\log q)^A \tag{3.5}

for every sufficiently large $q$. Then for all sufficiently large $m$ and every $N\geq2m$,

P^+\!\binom Nm \geq \min\left( N-m+1,\ \exp\!\left(((m+1)/C)^{1/A}\right) \right). \tag{3.6}

Changing constants absorbs the harmless $+1$, so this has the usual form

P^+\!\binom Nm \geq \min(N-m+1,e^{c m^{1/A}}). \tag{3.7}

Proof. Put

x=N-m+1,\qquad K=P^+\!\binom Nm,\qquad Q=\max(m,K).

The identity $\Pi(x,m)=m!\binom Nm$ shows that every prime factor of every integer in the block $x,\ldots,x+m-1$ is at most $Q$.

If $x\leq Q$, then $x\geq m+1>m$, so $Q\neq m$. Hence $Q=K\geq x$.

If $x>Q$, the displayed block is a $Q$-smooth run of length $m$ lying entirely above $Q$. Therefore $f(Q)\geq m+1$. Combining this with (3.5) gives

m+1\leq C(\log Q)^A, \qquad Q\geq \exp\!\left(((m+1)/C)^{1/A}\right).

For sufficiently large $m$, the last lower bound exceeds $m$; hence again $Q=K$. The two cases prove (3.6). (a)

Propositions 3.2 and 3.3 make the live page's “essentially equivalent” precise:

f(k)\ll(\log k)^A \quad\text{corresponds to}\quad P^+\!\binom Nm\geq \min(N-m+1,e^{c m^{1/A}}).

In particular, $A=2$ corresponds exactly to the $e^{c\sqrt m}$ scale mentioned by the lone commenter. (a)

4. Explicit construction from a prime gap

Lemma 4.1

Let $p<q$ be consecutive odd primes, set $k=(q-1)/2$, and suppose $p>k$. Then

f(k)\geq q-p. \tag{4.1}

Proof. Every integer $n$ with $p<n<q$ is composite. A composite $n$ has $P^+(n)\leq n/2$, and here

n\leq q-1=2k.

Thus $P^+(n)\leq k$. The $q-p-1$ integers $p+1,\ldots,q-1$ form a $k$-smooth run lying above $k$, so the defining minimal length satisfies $f(k)\geq(q-p-1)+1=q-p$. (a)

The checker proves by exhaustive trial division through $35975=\lfloor\sqrt q\rfloor$ that

p=1\,294\,268\,491,\qquad q=1\,294\,268\,779

are prime and that all 287 interior integers are composite. It also completely factors every interior integer. (d)

Here

q-p=288,\qquad k=\frac{q-1}{2}=647\,134\,389,\qquad p>k.

Lemma 4.1 therefore gives

\boxed{f(647\,134\,389)\geq288}.

(a+d)

The largest prime factor actually encountered in the run is $647\,134\,387$, still below $k$. The SHA-256 of the checker's canonical 287-line factorization transcript is

dbc11e2326789843df60fde26ace16030d954fb8c614937e2d6e093ac1a2d1ee

(d)

This construction is a concrete instance of the prime-gap mechanism Erdős used with Rankin's theorem. It is not an asymptotic improvement over the known Rankin lower bound. (a: mechanism; b: comparison with the cited theorem)

5. Exact computation for $1\leq k\leq40$

5.1 Why the enumeration is finite

Let $S$ be the primes at most $k$. If $a,a+1$ are both $k$-smooth, put $X=2a+1$, and write

\[ a(a+1)=D z^2 \]

with $D>1$ squarefree. Every prime factor of $D$ lies in $S$, and with $Y=2z$,

X^2-DY^2=1. \tag{5.1}

Conversely, every solution of (5.1) with odd $X$, $S$-smooth $Y$, and

\[ a=(X-1)/2 \]

gives a consecutive $S$-smooth pair after direct division checks. (a)

For each of the at most

2^{\pi(k)}-1

possible squarefree $D$, the positive Pell solutions are

X_r+Y_r\sqrt D=(X_1+Y_1\sqrt D)^r.

The Carmichael primitive-divisor theorem for these Pell/Lucas sequences, together with Lehmer's rank-of-apparition divisibility, implies that if every prime divisor of $Y_r$ is at most $p=\max S$, then

r\leq\max\left(12,\frac{p+1}{2}\right). \tag{5.2}

This is the same named cutoff used by Bauer–Bennett and Najman. (b)

For $k\leq40$, $p\leq37$, so $r\leq19$, and a fixed $k$ requires at most $2^{12}-1=4095$ Pell equations. Thus all consecutive $k$-smooth pairs, not merely pairs below a search ceiling, are enumerated. Grouping consecutive pair starts gives every smooth run of length at least two. For $k\geq2$, powers of two supply an isolated smooth integer if no pair exists; $k=1$ is handled separately. (a+b)

5.2 What the checker independently verifies

For every $D$ and every allowed exponent, the program checks with exact integers:

the continued-fraction fundamental solution satisfies $X_1^2-DY_1^2=1$;
every generated power satisfies its Pell equation;
the recovered $a(a+1)$ identity;
smoothness by repeated exact division;
the squarefree kernel is exactly $D$;
every reported maximal-run witness is smooth;
the complete Pell pair list agrees exactly, up to 200,000, with an independent direct-division scan that does not use Pell equations.

(d)

The resulting exact table is (b+d):

| $k$ | exact $f(k)$ | one maximal smooth-run witness | |---:|---:|---:| | $1$ | $1$ | no $1$-smooth integer $>1$ | | $2$ | $2$ | isolated $2$-smooth integers | | $3$–$4$ | $3$ | $8,\ldots,9$ | | $5$–$7$ | $4$ | $8,\ldots,10$ | | $8$–$12$ | $4$ | $14,\ldots,16$ | | $13$–$23$ | $6$ | $24,\ldots,28$ | | $24$–$31$ | $6$ | $32,\ldots,36$ | | $32$–$40$ | $6$ | $48,\ldots,52$ |

This agrees with the published table, but the calculation here is independent code rather than a transcription of OEIS or the papers. (d)

The same program directly factors

1330=2*5*7*19
1331=11^3
1332=2^2*3^2*37
1333=31*43
1334=2*23*29
1335=3*5*89
1336=2^3*167
1337=7*191
1338=2*3*223
1339=13*103
1340=2^2*5*67
1341=3^2*149
1342=2*11*61
1343=17*79
1344=2^6*3*7

so this length-15 block is $223$-smooth. (a+d) Its factorization-transcript SHA-256 is

69699b8ec6f927c4a1294a01964dc751f4092b15a1d5a8612a50ea7b2673d910

6. Reproduction

Environment used:

Python 3.12.3

Run:

cd /home/exedev/MathDyad
python runs/erdos961_wavew025_verify.py

The clean run completed with:

ELEMENTARY PRIME-GAP CERTIFICATE:
k=647134389, certified smooth-run length=287, hence f(k)>=288
largest prime factor actually seen in the run: 647134387
factorization transcript sha256: dbc11e2326789843df60fde26ace16030d954fb8c614937e2d6e093ac1a2d1ee
NAJMAN LOWER-WITNESS ARITHMETIC CHECK:
1330..1344 has length=15 and largest prime factor=223
factorization transcript sha256: 69699b8ec6f927c4a1294a01964dc751f4092b15a1d5a8612a50ea7b2673d910
STRUCTURAL/COUNT CROSS-CHECKS:
product/binomial equivalence grid cases: 12600
M268=1168680703, M269=1320356607, incremental=151675904
PASS; elapsed=11.385s

The full exact $k=1,\ldots,40$ table is printed before this excerpt. The finite structural grid checks (3.1) for every $1\leq m\leq k\leq20$ and $1\leq x\leq60$; it is an independent regression check, not a replacement for the elementary proof. (d)

7. Exact wall at $k=269$

The witness $1330,\ldots,1344$ proves $f(269)\geq16$. To prove $f(269)=16$, one must rule out every length-16 run of $269$-smooth integers beginning above 269. (a)

Using the Bauer–Bennett/Najman pairing scheme with $m=16$, $t=\pi(269)=57$, $t_0=\pi(15)=6$, and

N=\left\lfloor\frac{57-6}{\lfloor16/4\rfloor+\lfloor17/4\rfloor}\right\rfloor=6,

the direct discriminant count is

\begin{aligned} M &=-1+2^6\sum_{j=0}^{6}\binom{51}{j}\\ &=1\,320\,356\,607. \end{aligned} \tag{7.1}

(a: arithmetic; b: applicability of the published algorithm)

Najman's $k\leq268$ computation already required $1\,168\,680\,703$ Pell equations for its $(t,m)=(56,16)$ stage. Advancing by one prime adds $151\,675\,904$ candidate discriminants if all prior certified intermediate data are available and reusable; those data and the original implementation are not available in this workspace. (a: count difference; b: Najman's reported count)

Bauer–Bennett report just over 58 hours of processing time for $12\,293\,376$ easier discriminants on a dual-core 2.5 GHz PowerPC. Treating the reported processing time as 58 core-hours, flat scaling gives about

58\cdot\frac{1\,320\,356\,607}{12\,293\,376} \approx 6\,230

legacy core-hours for a clean $k=269$ run, or about 716 legacy core-hours for only the incremental discriminants. If their “processing time” was wall time with both cores saturated, both figures should be doubled. The larger discriminants are harder, while modern CPUs and Najman's compact representations are faster, so a realistic present-day planning range is roughly $10^3$–$10^4$ core-hours plus implementation and certification work, not a few-CPU-minute calculation. At a nominal \$0.04–\$0.10 per core-hour, raw compute alone would be roughly \$40–\$1,000; this is an order-of-magnitude engineering estimate, not a theorem. (c: cost extrapolation from the published timing)

A naive continued-fraction extension in this workspace was stopped after 150 seconds without producing the $k=41$–46 extension; the default checker is consequently capped at $k=40$. This does not challenge the published $k\leq268$ result; it records the limitation of the simple from-scratch implementation. (d)

8. Why the asymptotic problem remains open

The exact missing uniform lemma is now isolated by Section 3:

Prove that there is an $A<\infty$ and $c>0$ such that, uniformly for all sufficiently large $m$ and all $N\geq2m$, \[ > P^+\!\binom Nm\geq > \min(N-m+1,e^{c m^{1/A}}). > \]

By Propositions 3.2–3.3, this is quantitatively equivalent, up to constants, to a polylogarithmic bound $f(k)\ll(\log k)^A$. (a)

The currently listed conjectural target in problem 683 only asks for the much weaker $m^{1+c}$ scale, which would yield a power saving $f(k)\ll k^{1/(1+c)}$, not a polylogarithmic bound. (a, relative to the live statement of problem 683)

Prime-gap constructions explain the known large lower bounds, but they cannot supply an upper bound: a $k$-smooth run can occur far above $2k$, where “composite implies largest prime factor $\leq k$” is no longer available. (a)

The Pell method proves exact fixed-$k$ statements, but its squarefree-discriminant space grows exponentially in $\pi(k)$ and therefore does not give a uniform asymptotic estimate. (a: size of the enumerated family; c: practical asymptotic diagnosis)

Thus the genuine wall is not a missing finite check. It is a uniform largest-prime-factor theorem for binomial coefficients at the exponential-in-a-power scale. No checked source supplies that theorem. (a: reduction; c: literature-search limitation)

PARTIAL: live gate cleared; proved the quantitative binomial reduction, independently certified exact f(k) for k<=40 modulo the Carmichael-Lehmer cutoff, and constructed f(647134389)>=288; the uniform exponential-scale binomial prime-factor lemma remains open.

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