Erdős problem #375 / Grimm's conjecture — wave8z

Date: 2026-07-28 UTC

Outcome

Computer-assisted fixed-length theorem. Grimm's conjecture holds for every block length \(1\leq k\leq 59\). This is not a solution of the uniform conjecture. The theorem is rigorous modulo the published 2006 theorem of Laishram--Shorey and the finite computation in runs/erdos375_wave8z_reverify.py.

Claim labels used below:

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

The combined \(k\leq59\) result is (b+d). The finite reduction is (a).

Step 0: live-page audit

I accessed the live page and its discussion through a Bright Data cloud browser, not datacenter curl:

• problem page;
• LaTeX-source view;
• discussion thread.

Access time was 2026-07-28 UTC. The page says it was last edited 2026-01-24.

Verbatim current statement

Is it true that for any $n,k\geq 1$, if $n+1,\ldots,n+k$ are all composite then there are distinct primes $p_1,\ldots,p_k$ such that $p_i\mid n+i$ for $1\leq i\leq k$?

Stop-condition fields

• Page badge/status: FALSIFIABLE, with the site's open-problem warning.
• Claimed proofs: 0.
• Currently working on this problem: None.
• Interested in collaborating: None.
• Formalised statement: Yes.
• Likes: None.
• “This problem looks difficult”: Aron.
• “This problem looks tractable”: None.
• “The results on this problem could be formalisable”: None.
• “I am working on formalising the results”: None.
• No current worker and no claimed solution were present, so the requested stop

condition did not trigger.

Known results stated on the live page

The page says:

1. the assertion is trivial for \(k\leq2\), and Grimm originally conjectured

it;

1. Grimm proved it for

\(k\ll\log n/\log\log n\);

1. Erdős--Selfridge improved this to

\(k\leq(1+o(1))\log n\);

1. Ramachandra--Shorey--Tijdeman improved this to

\[ k\ll\left(\frac{\log n}{\log\log n}\right)^3; \]

1. Laishram--Shorey verified it for every \(k\) when

\(n\leq1.9\cdot10^{10}\);

1. it is Guy's problem B32, and the page cross-references problem #860.

All four live comments

The site explicitly warns that comments are not verified.

1. TerenceTao, 2026-01-16 16:46. He says the provenance of the claimed

power-saving prime-gap consequence is murky: Erdős--Selfridge Theorem 1 gives the weaker \(p_{j+1}-p_j\ll p_j^{1/2}/\sqrt{\log p_j}\), while their claimed use of Ramachandra for a power saving omits details. He sketches the binomial- coefficient argument and says a positive-density form of Ramachandra's result seems necessary.

1. Dogmachine, 2026-01-06 22:23. Notes Langevin's stronger conjecture that

every all-composite consecutive block is multiplicatively independent.

1. Alfaiz, 2025-12-03 11:30. Points to the 2006

\(1.9\cdot10^{10}\) verification and speculates that stronger distribution conjectures might improve the RST bound; the comment records that an earlier careless mistake was edited and the page was updated.

1. StijnC, 2025-12-04 09:14. Notes that the cubic RST range is stronger

than a quadratic range and says Cramér's conjecture plus RST and finite verification would imply a positive answer.

I do not use the comments as theorems.

Primary-source literature audit

I searched by the exact conjecture title, the names in the live bibliography, fixed-\(k\) bounds, smooth-number formulations, and recent computational verification claims.

1. Grimm (1969). C. A. Grimm, *A conjecture on consecutive composite

numbers*, American Mathematical Monthly 76, 1126--1128, DOI. This is the original source.

1. Erdős--Selfridge (1971). *Some problems on the prime factors of

consecutive integers II*, pp. 13--21, Erdős archive PDF. It formulates the matching function and proves the logarithmic lower range.

1. Ramachandra--Shorey--Tijdeman (1975). *On Grimm's problem relating to

factorisation of a block of consecutive integers*, J. Reine Angew. Math. 273, 109--124, DOI. The bibliographic record exists, and the later primary sources below quote its \((\log n/\log\log n)^3\) result.

1. Laishram--Shorey (2006). Grimm's conjecture on consecutive integers,

International Journal of Number Theory 2, 207--211, author-hosted PDF, DOI. Its Theorem 1 states that the conjecture holds for every \(k\) when \[ n\leq p_{850000000}=19\,236\,701\,629. \] The paper reports about one week of Mathematica computation. This exact cutoff is the named theorem used below. (b)

1. Zhang (arXiv:0811.0966, v4 2011). *A Refinement of the Function

\(g(m)\) on Grimm Conjecture*, arXiv. Its Theorem 1 uses the threshold \(\prod_{p\leq k}p^{\lfloor\log_p k\rfloor} =\operatorname{lcm}(1,\ldots,k)\) for a stronger coprime binomial decomposition. It also accurately records the older logarithmic and cubic ranges.

1. **Laishram--Murty (Michigan Math. J. 61 (2012), 151--160;

arXiv:1306.0765).** Grimm's Conjecture and Smooth Numbers, arXiv. It relates the matching function to smooth numbers, proves an unconditional upper bound \(g(n)<n^\alpha\) for a permissible \(0.45<\alpha<0.46\), and does not solve Grimm's conjecture.

1. Hands (2022). *On Graphical Representations of Grimm's Conjecture and

Minimal Interval Lengths*, University of Texas at Arlington honors thesis, repository record and PDF. Theorem 3 contains essentially the lcm obstruction rederived below, and the thesis reports a several-hour Python computation proving \(k\leq31\).

I found no later primary paper giving a larger fixed-\(k\) value. A January 2026 Reddit post claims a scan to \(10^{11}\), and a June 2026 comment claims \(10^{13}\), but both say code is available only on request; my searches found no public code, certificate, paper, or archived data. Those claims are (c/d, externally unverified) and are not used here. I therefore claim only that the present \(k\leq59\) computation improves the fixed-\(k\) primary-source result I located, not unconditional priority over unpublished work.

Elementary finite reduction

Let \(I=\{n+1,\ldots,n+K\}\), and make the bipartite graph whose left vertices are the integers in \(I\), whose right vertices are their prime divisors, and where divisibility gives the edges.

Lemma 1: divisor-of-lcm obstruction (a)

If this graph has no matching covering all of \(I\), then some \(x\in I\) divides

Proof.

By Hall's theorem choose an inclusion-minimal deficient set \(S\subseteq I\). Write \(P=N(S)\) for all prime divisors of members of \(S\). Minimality gives

Consequently every \(p\in P\) divides at least two members of \(S\). Two members of a length-\(K\) interval differ by at most \(K-1\), so every such prime satisfies \(p<K\).

For every \(p\in P\), choose \(y_p\in S\) on which \(v_p\) is maximal. At most \(|P|=|S|-1\) vertices have been chosen, so choose

For each \(p^a\Vert x\), maximality gives \(p^a\mid y_p\). Hence

Thus \(a\leq\lfloor\log_p(K-1)\rfloor\) for every \(p\mid x\), and therefore

\(\square\)

This proof is independent of the computation. It is closely related to Hands's Theorem 3 and Zhang's lcm threshold.

Lemma 2: exact smooth-number reduction (a)

Call an integer in \(I\) “\(K\)-smooth” here if all its prime factors are strictly less than \(K\). Any non-smooth member has a prime factor \(q\geq K\). Such a \(q\) cannot divide two members of \(I\), since it would divide their nonzero difference, which is \(<K\).

It follows that the full interval has a prime-divisor matching if and only if its \(K\)-smooth members have a matching to the primes \(<K\): assign one of the unique large primes to every non-smooth member. This is an exact equivalence, not a heuristic or merely a sufficient condition.

Corollary: the exact finite search space (a)

If a length-\(K\) interval starting after a bound \(B\) fails, it contains a divisor \(d\mid L_K\). Its start must therefore be one of

Enumerating all divisors of \(L_K\) and these short neighborhoods is exhaustive.

Why one length \(K\) proves every shorter length (a)

Suppose a length-\(k\) interval fails for some \(k\leq K\). Extend it to the right to length \(K\). The original Hall-deficient subset and all of its neighbors are unchanged, so the extended interval also fails. Therefore a check of all length-\(K\) intervals above \(B\), even intervals containing primes, rules out every shorter all-composite counterexample above \(B\).

The \(K=59\) exact computation (d)

For \(K=59\),

Thus \(\tau(L_{59})=884\,736\).

The standalone verifier is:

runs/erdos375_wave8z_reverify.py

Run from the repository root:

python runs/erdos375_wave8z_reverify.py

The complete executable is standard-library-only. Its core audit is:

for d in divisors(lcm(1, ..., K - 1)):
    for n in range(max(B + 1, d - K), d):
        masks = factor_masks_of_K_smooth_terms(n + 1, ..., n + K)
        assert augmenting_path_matching(masks) == subset_dp_matching(masks)
        assert augmenting_path_matching(masks)

The actual program merges duplicate start intervals, uses repeated gcd with \(L_{59}\) to recognize smooth numbers exactly, and slides the windows so it does not refactor the same local block \(59\) times.

Exact output table

| Quantity | Verified value | |---|---:| | divisors of \(L_{59}\) | 884,736 | | divisors yielding starts above the published cutoff | 602,688 | | merged divisor neighborhoods | 602,688 | | candidate length-59 starts | 35,558,592 | | exact smoothness evaluations | 70,514,496 | | smooth hits in those local evaluations | 602,806 | | starts with exactly one smooth member | 35,555,719 | | starts with exactly two smooth members | 2,873 | | starts with three or more smooth members | 0 | | distinct factor-mask graphs checked by two matchers | 43,682 | | failed matchings | 0 |

The maximum smooth count was only two. As a separate elementary check, two distinct integers \(>19\,236\,701\,629\) and less than 59 apart cannot both be powers of the same prime; hence any two such smooth vertices have at least two prime neighbors and are matchable. (a)

One maximum-count witness was the interval

Its two 59-smooth members were its endpoints:

For example, assign 5 to the first and 3 to the second; all non-smooth members have distinct prime factors at least 59.

Independent checks and reproducibility

1. Every encountered graph was checked both by augmenting paths and by an

independent subset-DP matcher; all 43,682 results agreed.

1. A direct self-test fully factored 3,975 small intervals of lengths at most
2. Full matching and the smooth reduction agreed on every interval. It

found 113 arbitrary-interval matching failures (not Grimm counterexamples) and independently confirmed that every one contained a divisor of the appropriate lcm.

1. The full \(K=59\) computation was run twice, the second time with

PYTHONHASHSEED=123. All non-runtime JSON fields were identical.

1. Run times were 115.739 and 116.410 seconds of elapsed time on one core;

peak RSS was about 243 MB.

1. Deterministic hashes:

• divisor list:

ddc792821243cc4eeb7c116b9ffb51ccb11805bd314aecddf3d712c0d587659e;

• scanned intervals and smooth masks:

617dc740504484f81a67a129c61745a52bb8de71b82e613ee1b3dd4cf2b75731;

• verifier source:

7c2385921a9147dbcb3eee276aad845a1a398de524477d07fa20871f1d125db7.

Fixed-length theorem (b+d)

Theorem. Grimm's conjecture holds for every \(1\leq k\leq59\).

Proof. Suppose there is a counterexample \((n,k)\), \(k\leq59\).

• If \(n\leq19\,236\,701\,629\), this contradicts Laishram--Shorey Theorem 1.
• Otherwise extend the failed interval to length 59. By the persistence of its

Hall-deficient subset, the extended interval also has no matching. Lemma 1 says it contains a divisor of \(L_{59}\), so its start is one of the 35,558,592 starts exhaustively checked above. Every such interval passed the exact matching test, a contradiction.

This proves the stated fixed-\(k\) regime, conditional only on the cited published cutoff theorem and the finite auditable computation. It does not assert the full conjecture.

What remains, and the precise wall

The unresolved part is \(k\geq60\), uniformly in \(n\). The exact missing uniform statement is:

For every all-composite interval of length \(k\), every subset of its \(k\)-smooth members has at least as many distinct prime divisors as members.

That is Hall's condition. Analytically, one must rule out a cluster of \(r+1\) integers in a length-\(k\) interval whose prime support has size at most \(r\). Available smooth-number distribution results do not provide this at the prime-gap scale. This is the same obstruction behind the prime-gap consequences discussed by Erdős--Selfridge, Laishram--Murty, and the live Tao comment. (b/c diagnosis)

The next fixed case is finite but more expensive. For \(K=60\), \(\tau(\operatorname{lcm}(1,\ldots,59))=1\,769\,472\); the same program would inspect approximately 82.1 million starts and 162.9 million smoothness values. Scaling from the measured \(K=59\) run gives about 4.5 single-core minutes (\(0.075\) core-hours) and roughly 0.5 GB peak memory. I did not run it because it crosses the requested few-CPU-minute budget. (d cost estimate)

PROVED: Rigorous modulo Laishram--Shorey (2006) plus a twice-reproduced exact computation, Grimm's conjecture holds uniformly for every block length k <= 59; the full problem remains open.