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:

• (a) elementary-rigorous;
• (b) rigorous modulo a named theorem;
• (c) plausible/structural-unverified;
• (d) computational-only.

0. Mandatory live-page check

I fetched both the problem page and its discussion thread through the Bright Data browser path:

• <https://www.erdosproblems.com/461>
• <https://www.erdosproblems.com/forum/discuss/461>
• LaTeX view: <https://www.erdosproblems.com/latex/461>

The page reported:

• status: OPEN;
• last edited: 28 October 2025;
• 0 claimed proofs;
• “Currently working on this problem”: None;
• “Interested in collaborating”: None;
• six comments;
• one “Likes this problem” marker (Aron), and no difficulty, tractability, or

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<t\). Let \(f(n,t)\) count the number of distinct possible values for \(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)

1. 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<t}(1-1/p) \quad (u<t). \] The asymptotic conclusion is (b) modulo Mertens' product theorem.

1. 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.

1. 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.

1. 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.

1. 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”

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

Lemma 1: only labels below \(t\) can repeat

If \(1\leq i<j\leq t\) and

then \(d\mid n+i\) and \(d\mid n+j\), hence \(d\mid(j-i)\). Since \(0<j-i<t\), necessarily \(d<t\). (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<t\),

Indeed, \(d<t\) is automatically composed only of primes below \(t\). The 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

where the last exponent denotes the least \(a\) with \(p^a\geq t\). (a)

Define

Lemma 1 gives the exact identity

Equations (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

This 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:

In particular,

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

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\), let \(q_p\) be the least power of \(p\) at least \(t\). A residue choice

is 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

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

It obtains

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

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<t}(A_d(n)-1)_+\leq(1-\delta)t, > \] 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:

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.