Erdős problem #889 — wave w020

Date: 2026-07-28 UTC

Claim labels

• [a] elementary-rigorous: proved here without an external theorem.
• [b] rigorous-modulo-named-theorem: a consequence of an explicitly

named published theorem.

• [c] plausible/structural-unverified: a search miss, heuristic, or cost

extrapolation; not asserted as a theorem.

• [d] computational-only/source-verified: an exact finite computation or

a direct observation from a fetched source.

[d] All newly reported arithmetic is recomputed from scratch by runs/erdos889_wavew020_reverify.py.

0. Mandatory live-page and collision audit

[d: live-page observation] Before doing any mathematics, I fetched the rendered live problem page through the Bright Data cloud browser. I then followed its comment link and fetched the rendered discussion thread. The access date was 2026-07-28.

Verbatim live statement

For \(k \geq 0\) and \(n \geq 1\) let \(v(n,k)\) count the prime factors of \(n+k\) which do not divide \(n+i\) for \(0\leq i<k\). Equivalently, \(v(n,k)\) counts the number of prime factors of \(n+k\) which are \(>k\).

Is it true that \[ > v_0(n)=\max_{k\geq 0}v(n,k)\to\infty > \] as \(n\to\infty\)?

[d] The source formula in Erdős–Selfridge makes clear that “prime factors” here means distinct prime factors.

Verbatim listed known result

A question of Erdős and Selfridge [ErSe67], who could only show that \(v_0(n)\geq 2\) for \(n\geq 17\). More generally, they conjecture that \[ > v_l(n)=\max_{k\geq l}v(n,k)\to\infty > \] as \(n\to\infty\), for every fixed \(l\), but could not even prove that \(v_1(n)\geq 2\) for all large \(n\).

This is problem B27 of Guy's collection [Gu04].

Complete marker/status audit

[d]

| live-page field | rendered value | |---|---| | status | OPEN | | comments | 1 | | claimed proofs | 0 | | likes this problem | Dogmachine | | interested in collaborating | None | | currently working on this problem | None | | problem looks difficult | Dogmachine | | problem looks tractable | None | | formalised statement? | Yes | | related OEIS sequences | Possible | | results could be formalisable | None | | working on formalising the results | None | | last edited | 02 January 2026 |

There was no claimed proof, solved/falsified status, current worker, or interested collaborator. The mandatory stop condition therefore did not apply.

The sole comment, verbatim

[d: comment record] LorenzoLuccioli, 15:40 on 03 Jan 2026:

The general version of the conjecture with \(l>0\) follows easily from the case \(l=0\), using the inequality \(v(n+1,k)\leq v(n,k+1)+1\).

This reduction was noticed with the help of Aristotle.

[d+a] The site warns that comments are not verified. The reduction itself is proved independently in Section 2 below.

1. Primary-source and literature audit

The original paper

[d] The cited primary source exists:

P. Erdős and J. L. Selfridge, Some problems on the prime factors of consecutive integers, Illinois Journal of Mathematics 11 (1967), 428–430, DOI 10.1215/ijm/1256054564, MR0229570.

I checked the three-page scan, rather than relying on tracker metadata.

[b: Erdős–Selfridge 1967] On printed page 428 the authors define

and prove the stronger exact statement

Thus \(v_0(n)\ge2\) for every \(n\ge17\).

[d: source record] They also report that

for

and no other \(n<2500\), while explicitly saying they had no method to prove that 330 was the last such value. This is a computation/conjectural observation in their paper, not a theorem of eventuality.

[d: source distinction] Printed page 429 introduces a different, apparently easier function \(V(n,k)\), which counts prime powers \(p^a\parallel n+k\) with \(p^a>k\). Its numerical values around \(10^5\) must not be confused with the present \(v(n,k)\). None of the finite results below uses that modified function.

The 1998 repetition and Guy

[d] The second cited source also exists:

P. Erdős, Some of my new and almost new problems and results in combinatorial number theory, in Number Theory: Diophantine, Computational and Algebraic Aspects (Eger, 1996), de Gruyter (1998), 169–180, MR1628841.

The publisher metadata verifies the chapter and pagination. The searchable scan of page 178 repeats the definition, says that one expects \(v_0(n)\to\infty\), repeats the \(v_0(n)>1\) result, and says “Probably \(v_1(n)>1\) for all \(n>330\)” before referring back to the 1967 paper. It supplies no later proof.

[d] Richard K. Guy's Unsolved Problems in Number Theory, third edition (Springer, 2004), lists this as B27, “The number of prime factors of \(n+k\) which don't divide \(n+i\), \(0\le i<k\),” in the divisibility chapter.

Later-literature search

[d] I searched exact phrases, the exact \(v(n,k)\), \(v_0(n)\), and \(v_1(n)\) notation, “Erdős problem 889,” “B27,” the 1967 title, and the 1967 paper's citation graph. OpenAlex identifies the paper as W1561472112, DOI 10.1215/ijm/1256054564, with 14 indexed citing works. I checked the plausible primary-source descendants, including:

• Erdős–Selfridge,

Some problems on the prime factors of consecutive integers II (1971);

• Erdős–Sárközy,

On the prime factors of \(\binom nk\) and of consecutive integers (1979);

• Erdős–Lacampagne–Selfridge,

Prime factors of binomial coefficients and related problems (1988);

• Erdős–Sárközy,

Some solved and unsolved problems in combinatorial number theory, II (1993).

Those papers cite the 1967 work for nearby questions about products of consecutive integers, binomial coefficients, or Grimm-type problems; I found no theorem in them establishing eventual lower bounds for this \(v_0\).

[d] I also checked the recent primary source arXiv:2604.15042, On the Number of Prime Factors of Consecutive Integers. Its Theorem 1.1 constructs infinitely many \(n\) for which \(\Omega(n+k)\le C\log k\) for every \(k\ge2\), and it explicitly connects its corollaries to Erdős problems #248, #413, #826, and #679. That is an upper bound on a different quantifier pattern and does not give the uniform lower bound required here.

[c: honest search miss] The exact searches, primary texts, citation graph, and current 2025–2026 arXiv search found no claimed solution or later partial theorem for the uniform \(v_0\) question beyond the results recorded on the live page. A literature search cannot prove that no uncatalogued result exists.

2. Exact elementary reduction

For \(r\ge1\), define \(P_r(m)\) to be the \(r\)-th largest distinct prime factor of \(m\), with \(P_r(m)=0\) when \(\omega(m)<r\).

Interval-covering lemma

Lemma [a]. For every \(n\ge1\), \(k\ge0\), and \(r\ge1\),

Consequently,

Proof. The value \(v(n,k)\) is the number of distinct prime divisors of \(m=n+k\) exceeding \(k\). At least \(r\) do so exactly when the \(r\)-th largest distinct prime divisor \(P_r(m)\) exceeds \(k=m-n\). The last inequality is equivalent to

which gives (3). \(\square\)

Corollary [a]. The original conjecture is equivalent to:

for every fixed \(r\), the integer intervals in (3) cover every sufficiently large positive integer.

The known theorem (1) says that the \(r=2\) interval family covers every integer from 17 onward. The first unresolved uniform layer is already \(r=3\).

Exact offset truncation

Lemma [a]. If \(v(n,k)\ge r\), then

Proof. There are \(r\) distinct primes \(p_1,\ldots,p_r>k\) whose product divides \(n+k\). Hence

which rearranges to (4). \(\square\)

Let

Then determining whether \(v_0(n)\ge r\) for every \(n\le N\) only requires factoring

For the reported \(r=3\), \(N=50{,}000{,}000\) computation,

because

Thus only \(m\le50{,}000{,}368\) can certify a three-prime witness for this prefix.

Verification of the live-page comment

Proposition [a].

Therefore, for every fixed \(\ell\ge0\),

In particular, the \(\ell=0\) conjecture implies all the fixed-\(\ell\) versions.

Proof. Both terms in (8) inspect prime divisors of the same integer \(n+k+1\). The left side admits primes \(p>k\), while \(v(n,k+1)\) admits \(p>k+1\). The only possible lost prime is \(p=k+1\), so at most one is lost. Iterating (8) gives

Maximizing over \(k\ge0\) gives

equivalent to (9). \(\square\)

What standard normal-order theory does give

Proposition [b: Hardy–Ramanujan theorem]. Hardy and Ramanujan, The normal number of prime factors of a number \(n\), Quarterly Journal of Mathematics 48 (1917), 76–92, prove the normal order used here. For almost all \(n\),

In particular, for every fixed \(r\),

This proves the conjectured divergence on a density-one set. It does not control the worst exceptional \(n\), which is the quantifier needed by the live problem.

3. Exact computation of the first open layer

Define

Algorithm

[a] A prime sieve through \(N+K_3(N)\) visits the primes in increasing order and records the largest three distinct prime divisors of every \(m\):

for p in primes:
    multiples = slice(p, maximum + 1, p)
    third[multiples] = second[multiples]
    second[multiples] = first[multiples]
    first[multiples] = p

Each prime visits a multiple exactly once, regardless of exponent, so third[m] is exactly \(P_3(m)\).

[a] Formula (3) is then evaluated with an exact difference array. For every \(m\) with \(P_3(m)>0\), the code adds one to the integer range

After a cumulative sum, the zero locations are exactly \(E_3(N)\):

left = m - q3 + 1
right = minimum(m, N)
add_at(delta, left, 1)
delta[right + 1] -= 1
coverage = cumsum(delta)
exceptions = flatnonzero(coverage[1:N + 1] == 0) + 1

No probable-prime test or external factor table is used.

Independent checks

[d] The standalone verifier performs all of the following in its default run:

1. It repeats the interval calculation with \(P_2(m)\) and obtains exactly

\(\{1,2,3,4,7,8,16\}\) as the \(v_0(n)<2\) set through \(50{,}000{,}000\), matching (1).

1. It directly trial-factors every \(n+k\) for every reported member of

\(E_3(50{,}000{,}000)\), for every \(0\le k\le K_3(n)\), and confirms that none has three eligible primes. This second audit uses a separate standard-library prime sieve and does not use the stored \(P_3\) values.

1. It compares the interval result and the direct definition on every

\(1\le n\le10{,}000\), checking both covered and uncovered cases.

1. It checks all table constants and the SHA-256 digest of the complete

comma-separated exception list.

The exact command is:

python runs/erdos889_wavew020_reverify.py

The completed run on this VM printed:

limit=50,000,000; K2=7071; K3=368; sieving through 50,007,071
factor sieve: 14.152s
v0(n)<3 count: 2,112; last: 14,433,526
exception-list sha256: 1c39d5d70e2a8b9a9abb16abc222924cf1cfb644a2beb4c1beebec1a4b4dd458
independent direct audit: 0.481s
total: 26.280s
PASS

Exact table

Theorem [d: exhaustive computation]. The following table is exact. The last column is the largest member of \(E_3(B)\).

| \(B\) | \(\#E_3(B)\) | last \(n\le B\) with \(v_0(n)<3\) | |---:|---:|---:| | 10 | 10 | 10 | | 100 | 84 | 100 | | 1,000 | 361 | 992 | | 10,000 | 980 | 9,992 | | 100,000 | 1,705 | 99,985 | | 1,000,000 | 2,054 | 958,534 | | 10,000,000 | 2,110 | 9,919,351 | | 20,000,000 | 2,112 | 14,433,526 | | 50,000,000 | 2,112 | 14,433,526 |

Equivalently,

This is a finite theorem only; it does not assert that 14,433,526 is the global last exception.

[d] There are 58 exceptions above one million:

1033957, 1034524, 1057981, 1057982, 1065646, 1105413,
1112167, 1155477, 1189358, 1265671, 1305352, 1317214,
1353907, 1353908, 1402495, 1403404, 1417915, 1441941,
1526296, 1557727, 1558497, 1653205, 1837096, 1847671,
1862776, 1948246, 2008624, 2122864, 2127603, 2317551,
2329881, 2402811, 2580261, 2580262, 2653718, 2709753,
2771344, 2812135, 3086374, 3386133, 3543754, 4264462,
4281236, 4815307, 4815308, 4933831, 5303733, 5738827,
5738828, 6037202, 6353734, 6359876, 6408056, 6408057,
7299274, 9919351, 13403007, 14433526

[b+d] Together with (1), the 2,112 exceptions consist of seven values with \(v_0(n)=1\) and 2,105 values with \(v_0(n)=2\).

Direct boundary certificates

[d] For \(n=14{,}433{,}526\), (4) reduces a search for three eligible primes to \(0\le k\le243\), since

The independent trial-factor audit checks all 244 offsets and finds no value of \(v(n,k)\) above 2. At \(k=0\),

with \(7{,}216{,}763\) prime, so \(v_0(14{,}433{,}526)=2\).

[d] The very next integer has the explicit witness

where \(601{,}397\) is prime. All three distinct primes exceed \(k=1\), so

[d] At the other endpoint,

so \(v(50{,}000{,}000,1)=4\).

4. Exact remaining obstruction

The interval reduction isolates the missing statement with no heuristic language.

[a] Even the first open uniform layer would require proving:

Equivalently, the \(P_3\)-radius intervals in (3) must have only finitely many uncovered positive integers.

[b] Hardy–Ramanujan controls almost all \(n\) through the easy choice \(k=0\), but supplies no maximal-gap bound for the exceptional set in (14). Results producing almost-primes or prescribed prime-factor behavior in many short intervals likewise have the wrong quantifier: (14) needs a witness in a moving interval for every starting integer \(n\), with all three selected prime factors larger than their offset.

[a] Proving (14) alone would establish eventual \(v_0(n)\ge3\), but would still not prove \(v_0(n)\to\infty\). The full problem needs the analogous eventual coverage for every fixed \(r\). Conversely, a finite search can never disprove (14) unless supplemented by a construction of infinitely many uncovered integers.

[c: cost estimate, not run] The dense verifier scales essentially like \(O(X\log\log X)\). Extrapolating its measured 26.3-second \(X=5\cdot10^7\) run to \(X=10^9\) gives roughly 0.15–0.3 single-core hours and about 14 GB peak RAM (three 32-bit factor arrays, a Boolean prime sieve, and the difference array). That exceeds the “few CPU-minutes” budget, so it was not run. A segmented implementation would reduce memory, but any larger finite prefix would remain logically incapable of supplying the uniform finiteness step.

[a+c] The concrete wall is therefore not factorization speed. It is the missing uniform interval-covering lemma (14), already for \(r=3\).

PARTIAL: exact interval reduction and exhaustive verification give \(v_0(n)\ge3\) for every \(14{,}433{,}527\le n\le50{,}000{,}000\), with exactly 2,112 smaller-prefix exceptions and last \(14{,}433{,}526\); eventual coverage remains unproved.