ERDŐS/DAILY ▸

← back to the ledger

ERDőS #461 · PARTIAL

Erdős problem #461 — wave 5w

Date: 2026-07-26 UTC

Outcome

The live page was OPEN, with 0 claimed proofs and no current worker, so the

mandatory stop condition did not apply. The problem remains open. The new

verifiable output is:

1. an elementary finite-period reduction for fixed \(t\);

2. exact exhaustive minima for every \(1\leq t\leq 13\); and

3. an explicit 424-digit CRT certificate with

\[ f(n,500)=218=0.436\cdot 500. \]

In particular, any constant \(c\) valid in the uniform inequality

\(f(n,t)\geq ct\) must satisfy \(c\leq 109/250=0.436\).

Claim labels used below are the requested ones:

0. Mandatory live-page check

I fetched both the problem page and its discussion thread through the Bright

Data browser path:

The page reported:

formalisation-worker markers.

Thus there was no claimed solution or worker collision.

Verbatim live statement

> Let \(s_t(n)\) be the \(t\)-smooth component of \(n\) - that is, the

> product of all primes \(p\) (with multiplicity) dividing \(n\) such that

> \(p

> \(s_t(m)\) for \(m\in [n+1,n+t]\). Is it true that

> \[ > f(n,t)\gg t > \]

> (uniformly, for all \(t\) and \(n\))?

The only known result in the page body is:

> Erdős and Graham report they can show

> \[ > f(n,t)\gg \frac{t}{\log t}. > \]

All six live comments

The site explicitly warns that comments are user-supplied and unverified.

Here is the complete mathematical content, in chronological order:

1. Woett, 09:42 on 06 May 2026. Proposed a bipartite matching from

\(\{1,\ldots,\lfloor t/2\rfloor\}\) to the distinct smooth components,

joining \(i\) to components divisible by \(i\). The proposed Hall

condition fails at \(n=1407302,t=38\), with

\(D=\{13,15,16,17,18,19\}\) having only five neighbours, at offsets

\(9,10,13,26,28\). I independently recomputed the 38 components; the

stated Hall obstruction is arithmetically correct. (d)

2. Pr_Huang, 16:02 on 12 June 2026. Gave an averaging argument which,

using Mertens' product theorem, yields

\[ \inf_n f(n,t)\leq (1-e^{-\gamma}+o(1))t. \]

Thus the temporary strengthening \(f(n,t)\geq t/2\) cannot hold

asymptotically. The post did not claim to solve #461. The density

calculation in the post is correct:

\[ \Pr(s_t(m)=u)=\frac1u\prod_{p

The asymptotic conclusion is (b) modulo Mertens' product theorem.

3. Thomas Bloom, 09:35 on 16 June 2026. Confirmed that this is an upper

bound, questioned the provenance of the \(t/2\) strengthening, and

suggested the averaging observation is likely standard.

4. Nat Sothanaphan, 17:30 on 16 June 2026. Explained that \(t/2\) came

from Woett's failed matching idea, not from Erdős and Graham.

5. Pr_Huang, 20:44 on 16 June 2026. Clarified the same point and again

stated that the averaging argument does not settle the original

\(\gg t\) question.

6. Pr_Huang, 05:09 on 19 July 2026. Explained an obstruction to a

Shannon-entropy proof. For random genuine prime-power residue (“ruler”)

data, the post calculates an expected entropy deficit of

\[ \left(\frac{e^{-\gamma}}2+o(1)\right)t\log t. \]

Therefore a uniform \(O(t)\), or even \(O(t\log\log t)\), entropy-deficit

estimate cannot be the missing proof. This was presented as a negative

observation, not a proof of #461.

1. Primary source and literature search

The cited source is:

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

Combinatorial Number Theory*, Monographies de L'Enseignement Mathématique

28 (1980), MR 0592420.

A scan hosted with Ronald Graham's papers is available at

<https://mathweb.ucsd.edu/~ronspubs/80_11_number_theory.pdf>. I inspected

printed pages 91–92. The source defines

\(n+i=a_i b_i\), with all prime factors of \(a_i\) below \(t\) and all

prime factors of \(b_i\) at least \(t\), asks for a uniform positive lower

bound on \(f(n,t)/t\), and says “We can only show”

\[ f(n,t)>\frac{ct}{\log t}. \]

This agrees with the live page.

I searched exact quotations from pages 91–92, the phrases “smooth

component”, “largest smooth divisor”, and variants involving \(f(n,t)\),

consecutive integers, Erdős, and Graham. Exact-phrase web searches returned

the monograph and the tracker, but no later paper treating this exact

question. I also screened the title/abstract metadata of all 372 works which

OpenAlex lists as citing the monograph; the apparent keyword hits concerned

different problems. For example, Bauer–Bennett, *Prime factors of consecutive

integers*, Math. Comp. 77 (2008), 2455–2459, studies the minimum length of a

block containing a number with a prime factor exceeding \(k\), not #461.

Google Scholar itself was unavailable through the browser because its

robots.txt blocked the Bright Data path. Therefore this is an honest search

miss, not a claim that no relevant literature exists.

No paper or arXiv identifier is asserted here as resolving or improving the

lower bound for #461.

2. An exact finite reduction

Fix an integer \(t\geq1\), and put

\[ P_t=\prod_{pLemma 1: only labels below \(t\) can repeat

If \(1\leq i \[ s_t(n+i)=s_t(n+j)=d, \]

then \(d\mid n+i\) and \(d\mid n+j\), hence \(d\mid(j-i)\). Since

\(0(a)

Thus every component at least \(t\) is a singleton within the interval.

Lemma 2: exact description of a small label

For \(1\leq d \[ s_t(m)=d \quad\Longleftrightarrow\quad d\mid m\ \text{ and }\ \gcd(m/d,P_t)=1. \tag{1} \]

Indeed, \(d

quotient contains no further prime below \(t\) exactly when the full

\(t\)-smooth component has already been extracted. (a)

The indicator of (1) has period \(dP_t\). Consequently all collision

information has period

\[ \begin{aligned} Q_t &=\mathop{\mathrm{lcm}}_{1\leq dwhere the last exponent denotes the least \(a\) with \(p^a\geq t\).

(a)

Define

\[ A_d(n)=\#\{1\leq i\leq t:s_t(n+i)=d\}. \]

Lemma 1 gives the exact identity

\[ f(n,t) =t-\sum_{1\leq dEquations (1)–(3) show that \(f(n,t)\), although its large numerical labels

need not themselves be periodic, has the same value after \(n\mapsto n+Q_t\).

Therefore

\[ \min_n f(n,t)=\min_{0\leq nThis is a finite exact reduction, with no distributional assumption. (a)

3. Exact small cases

The verifier sieves the values \(\min(t,s_t(m))\) for

\(1\leq m\leq Q_t+t\), examines every window start modulo \(Q_t\), and

counts equal capped labels only when the label is below \(t\). Lemma 1

justifies treating every capped value \(t\) as a distinct singleton.

The resulting complete table is:

| \(t\) | \(Q_t\) | \(\min_n f(n,t)\) | first minimizing \(n\bmod Q_t\) |

|---:|---:|---:|---:|

| 1 | 1 | 1 | 0 |

| 2 | 1 | 1 | 0 |

| 3 | 4 | 2 | 0 |

| 4 | 36 | 3 | 3 |

| 5 | 72 | 3 | 9 |

| 6 | 1,800 | 4 | 56 |

| 7 | 1,800 | 4 | 176 |

| 8 | 88,200 | 5 | 1,255 |

| 9 | 176,400 | 5 | 2,515 |

| 10 | 529,200 | 6 | 2,514 |

| 11 | 529,200 | 6 | 5,034 |

| 12 | 64,033,200 | 7 | 55,433 |

| 13 | 64,033,200 | 7 | 55,433 |

In particular,

\[ \min_n f(n,t)=\left\lfloor\frac t2\right\rfloor+1 \quad(3\leq t\leq13). \]

The table and this displayed finite-range identity are (d): they are

complete exhaustive computations resting on the elementary period proof

above, not a conjectural sample.

The full verifier repeated both 64,033,200-state enumerations and finished

in 30.33 seconds on this VM. The next period is

\[ Q_{14}=10,821,610,800. \]

A direct extension of this array method would require about 21.6 GB merely

for one uint16 label array, and scaling the measured run gives roughly

42 minutes (about 0.7 core-hours), before overhead. It was not run.

4. Explicit \(t=500\) construction

For every prime \(p

\(t\). A residue choice

\[ n\equiv r_p\pmod {q_p}\qquad(pis jointly realizable by the Chinese remainder theorem, since the \(q_p\)

are pairwise coprime. Within an interval of length \(t\), these residues

determine all repeated labels: divisibility by \(q_p\) already forces a

component at least \(t\).

I generated the distinct valuation patterns for each prime and used seeded

coordinate descent, trying every pattern for one prime at a time. This search

is heuristic and makes no optimality claim (c). Its second restart for

\(t=500\), seed 461500, produced the residue vector stored in the standalone

verifier. CRT gives the least nonnegative solution

n =
3466274494863435506775245645185646215164834924872516049238373596594822082200172097878880114356845940107553838288020360546702413888028491996807760048548848814065488595473682560959051764690964853991633965679373780304657010028444840646819441119846648800433637222565601472002522447033648816101379825075374811319634541287199066545847040716977959471532003716110472135594619798394398365162076610801187869688160130352006730623788205.

The verifier does not trust the capped search labels. It independently:

1. regenerates all 95 primes \(p<500\);

2. reconstructs \(n\) from the stored residues by a fresh CRT;

3. for every \(1\leq i\leq500\), repeatedly divides \(n+i\) by every

\(p<500\), retaining the complete prime multiplicities; and

4. inserts the resulting 500 exact integers into a set.

It obtains

\[ \boxed{f(n,500)=218}. \tag{5} \]

For auditability, the comma-separated sequence of all 500 components has

SHA-256

1c76b4e40b5bc9e8afe9cbdbbd1e67b4fae4c69dc91d322625da534d88b1781d

and the histogram

(multiplicity -> number of labels)
1->167, 2->16, 3->7, 4->8, 5->4, 6->2, 7->2, 8->3,
10->1, 11->1, 12->2, 15->1, 16->1, 20->1, 29->1, 53->1.

These figures give 218 labels, 500 positions, and collision excess

\(500-218=282\). The largest class has multiplicity 53. Every repeated

component is also checked to be below 500, independently confirming Lemma 1

on the certificate. Equation (5) is a finite arithmetic statement (d);

the checker consists only of CRT and trial division.

It follows immediately from (5) that a uniform lower-bound constant must

obey

\[ c\leq\frac{218}{500}=\frac{109}{250}=0.436. \tag{6} \]

This consequence is (a). It is a slightly stronger numerical cap than

the comment's asymptotic \(1-e^{-\gamma}\approx0.438541\), and it is an

explicit finite example rather than an averaging existence argument. It

also gives a concrete counterexample to \(f(n,t)\geq t/2\). It does not

disprove the existence of some smaller positive uniform constant.

5. Exact remaining obstruction

The original question is now equivalently the following uniform

collision-excess statement:

> Does there exist an absolute \(\delta>0\) such that, for every \(t\) and

> every \(n\bmod Q_t\),

> \[ > \sum_{d \]

> where

> \[ > A_d(n)=\#\left\{1\leq i\leq t: > d\mid n+i,\ > \gcd\left(\frac{n+i}{d},P_t\right)=1\right\}? > \]

The equivalence is equation (3), so this reduction is (a). This is also

the precise missing lemma. It must control the support of many

simultaneous rough-number sieves uniformly in the entire prime-power residue

datum; an average over \(n\), a bound for any one \(A_d\), or a Shannon

entropy bound does not supply it.

The modulus itself is exponential:

\[ Q_t=\exp((2+o(1))t) \]

by the prime number theorem applied to (2), so this asymptotic is (b)

modulo the prime number theorem. Exhausting \(Q_t\) cannot give a uniform

proof. The concrete jump from \(Q_{13}=64,033,200\) to

\(Q_{14}=10,821,610,800\) already demonstrates the computational wall.

Thus the exact unresolved step is not finite arithmetic or CRT

realizability. It is a uniform support-sensitive sieve inequality for the

quantities \(A_d(n)\).

6. Reproduction

Standalone verifier:

runs/erdos461_wave5w_reverify.py

Run:

python runs/erdos461_wave5w_reverify.py

Observed final output:

explicit certificate: t=500, f(n,t)=218, f/t=0.436, n has 424 digits, values_sha256=1c76b4e40b5bc9e8afe9cbdbbd1e67b4fae4c69dc91d322625da534d88b1781d
...
exact period: t=13, Q_t=64033200, min f= 7, first n=55433
small-table exhaustive time: 30.33s
ALL CHECKS PASSED

PARTIAL: Explicit CRT arithmetic gives f(n,500)=218 (hence any uniform constant is at most 0.436), and exhaustive periodic enumeration gives the exact minima for every t<=13; Erdős #461 remains open.

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