ERDŐS/DAILY ▸

← back to the ledger

ERDőS #890 · PARTIAL

Erdős problem #890 — live audit, reductions, and exact finite data

Access date: 2026-07-27 (UTC). This report uses the following labels throughout:

0. Mandatory live-page audit

[a] I fetched the live problem page, its LaTeX source, and the discussion thread through a Bright Data browser. Direct extraction showed:

Thus neither stop condition is present. In particular, the thread mentions a formal counterexample to an older formalisation, but the subsequent comment says that it no longer works after the definition was corrected; the current page itself lists zero proof claims.

Verbatim current statement

If $\omega_k(n)$ counts the number of distinct prime factors of $n$ which are $>k$, then is it true that, for every $k\geq 1$, \[ > \liminf_{n\to \infty}\sum_{0\leq i<k}\omega_k(n+i)\leq k? > \] Is it true that \[ > \limsup_{n\to \infty}\left(\sum_{0\leq i<k}\omega(n+i)\right) \frac{\log\log n}{\log n}=1, > \] where $\omega$ counts the number of distinct prime factors without restriction?

Results and comments actually present on the live page

[b] The page records Erdős–Selfridge's lower bound

\[ \liminf_{n\to\infty}\sum_{0\le i<k}\omega_k(n+i)\ge k-1. \]

It follows from Pólya's theorem that gaps between successive \(k\)-smooth integers tend to infinity: eventually at most one member of a length-\(k\) block is \(k\)-smooth.

[b] The page also records the classical maximal order

\[ \limsup_{n\to\infty}\omega(n)\frac{\log\log n}{\log n}=1. \]

[a/source] The page warns that the 1967 paper states the first question with unrestricted \(\omega\) and the bound \(k+\pi(k)\). The page's present \(\omega_k\) formulation is its correction of that apparent error.

[a/source, c as to unproved comment content] I read all seven comments:

  1. Agustín Meza (20 Aug 2025) points out the small-prime obstruction in the

unrestricted formulation and gives a prime-\(k\)-tuples route.

  1. Thomas Bloom (24 Aug 2025) initially questions that reading of the original.
  2. Terence Tao (12 Oct 2025) agrees with Meza and notes that the original

small-prime contribution should be \(\sum_{p\le k}\lfloor k/p\rfloor\), not merely \(\pi(k)\).

  1. Moritz Firsching (03 Apr 2026, 12:40) asks whether compositeness was omitted

and links a formal counterexample at \(k=26\) to the then-formalised version.

  1. Thomas Bloom (03 Apr 2026, 13:18) says compositeness was not intended and

reports revising the first question to the current definition.

  1. Moritz Firsching (03 Apr 2026, 13:50) says the \(k=26\) counterexample no

longer applies and that the Formal Conjectures statement will be updated.

  1. Steve Fan (18 Jul 2026) derives \(O(k\log(k+1))\) from Lau's recent theorem

and notes a \(k=2\) upper bound of \(3\) from Chen's theorem.

The website explicitly says comments are not verified; the two substantive recent deductions were therefore checked against sources below.

1. Source and literature check

[a/source] The original source exists and was read: P. Erdős and J. L. Selfridge, “Some problems on the prime factors of consecutive integers”, Illinois J. Math. 11 (1967), 428–430. Page 429–430 contains the maximal-order question and the lower/upper liminf discussion. Its printed formulation has exactly the small-prime issue described on the live page, so I do not use that printed formula in place of the authoritative live statement.

[b] Cheuk Fung Lau, “On the Number of Prime Factors of Consecutive Integers,” arXiv:2604.15042v2 (submitted 16 Apr 2026, revised 24 Jun 2026), Theorem 1.1, proves that for an absolute \(C>0\) there are infinitely many \(m\) such that

\[ \Omega(m+j)\le C\log j\qquad(j\ge2). \]

For fixed \(k\), put \(n=m+2\). Then

\[ \sum_{i=0}^{k-1}\omega_k(n+i) \le \sum_{j=2}^{k+1}\omega(m+j) \le C\sum_{j=2}^{k+1}\log j =O(k\log(k+1)). \]

This verifies Fan's stated consequence, but the unspecified absolute constant does not approach the desired coefficient \(1\).

[b] The needed arithmetic-progression form of Chen's sieve theorem is quoted precisely in von zur Gathen–Knopfmacher–Luca–Lucht–Shparlinski, “Average order in cyclic groups,” Theorem 4.5 proof, pp. 119–120: for every fixed even \(d\), infinitely many primes \(p\equiv1\pmod d\) have \((p-1)/d\) with at most two prime factors. With \(d=2\) and \(n=p-1\),

\[ \omega_2(n)+\omega_2(n+1)\le2+1=3. \]

The original paper's publisher page was also checked: J.-R. Chen, “On the representation of a larger even integer as the sum of a prime and the product of at most two primes”, Scientia Sinica 16 (1973), 157–176, DOI 10.1360/ya1973-16-2-157. The publisher exposes the paper and its main abstract; the exact \(p-1\) formulation above was verified from the later paper's explicit statement rather than inferred from that abstract.

[a/source] I also checked the related primary block literature: Laishram–Shorey, “Number of prime divisors in a product of consecutive integers” (Acta Arith. 113 (2004), 327–341), and Balasubramanian–Laishram–Shorey–Thangadurai, “The number of prime divisors of a product of consecutive integers” (2012). These give lower bounds or results with \(k\) varying (the latter under Schinzel's Hypothesis), not either fixed-\(k\) assertion here.

[c] Exact-formula searches, searches by the 1967 title and citation chain, and the recent arXiv papers above found no source proving or disproving either current question. This is an honest search miss, not a claim that no such literature exists.

2. Exact reductions

Put

\[ \Delta_k(n)=\prod_{i=0}^{k-1}(n+i),\qquad A_k(n)=\sum_{i=0}^{k-1}\omega_k(n+i),\qquad B_k(n)=\sum_{i=0}^{k-1}\omega(n+i). \]

2.1 The first question is an almost-prime polynomial problem

[a] For every \(n,k\),

\[ \boxed{A_k(n)=\omega_{>k}(\Delta_k(n)).} \]

Indeed, a prime \(p>k\) cannot divide two terms \(n+i,n+j\), since that would give \(p\mid i-j\) with \(0<|i-j|<k<p\). Thus each large prime is counted once on both sides.

[b, conditional on the prime-\(k\)-tuples conjecture] There is a completely explicit sufficient prime-tuple reduction. Let \(W=(2k)!\) and

\[ L_j(t)=\frac{W}{j}t+1\qquad(1\le j\le k). \]

For every prime \(p\le2k\), \(W/j\) remains divisible by \(p\), so \(L_j(t)\equiv1\pmod p\). For \(p>2k\), the \(k<p\) forms exclude at most \(k\) residue classes. Hence the tuple is admissible. Dickson's prime-\(k\)-tuples conjecture would give infinitely many \(t\) for which every \(L_j(t)\) is prime. With \(n=Wt+1\),

\[ n+j-1=jL_j(t), \]

so each term has exactly one prime divisor \(>k\), and \(A_k(n)=k\).

[c] Current lower-bound sieve methods do not prove simultaneous primality of these \(k\) forms. Even the \(k=2\) instance asks for two linked linear forms to be prime; Chen's parity-breaking result replaces one by a \(P_2\) and therefore gives \(3\), not \(2\). The precise sufficient missing lemma is:

\[ \text{infinitely often }\quad \sum_{j=1}^{k}\omega(L_j(t))\le k. \]

Since every \(L_j(t)>1\), this forces every form to be a prime power. It is a parity-level almost-prime tuple statement; Lau's \(O(\log j)\) theorem does not supply it.

2.2 The second question is a maximal-order theorem for \(\Delta_k\)

For a prime \(p\), let

\[ c_p(n)=\#\{0\le i<k:p\mid n+i\}. \]

[a] Exact multiplicity bookkeeping gives

\[ B_k(n)=\omega(\Delta_k(n)) +\sum_{p<k}\bigl(c_p(n)-1\bigr)_+. \]

Only \(p<k\) can divide two terms, and

\[ 0\le\sum_{p<k}(c_p(n)-1)_+ \le C_k:=\sum_{p<k}\left(\left\lceil\frac{k}{p}\right\rceil-1\right), \]

a constant depending only on \(k\). Consequently the second question is exactly equivalent to

\[ \boxed{\limsup_{n\to\infty} \omega(\Delta_k(n))\frac{\log\log n}{\log n}=1.} \]

[b] The classical maximal-order theorem applied to \(\Delta_k(n)=n^{k+o(1)}\) gives only

\[ 1\le \limsup_{n\to\infty}B_k(n)\frac{\log\log n}{\log n} \le k. \]

The lower bound follows already from \(B_k(n)\ge\omega(n)\) and primorial values of \(n\); the upper bound treats \(\Delta_k(n)\) as an arbitrary integer of size \(n^k\).

[c] Thus the exact missing uniform lemma for the second question is

\[ \omega\!\left(\prod_{i=0}^{k-1}(n+i)\right) \le(1+o_k(1))\frac{\log n}{\log\log n} \quad\text{for every sufficiently large }n. \]

The generic bound has \(k+o(1)\) in place of \(1+o(1)\). CRT constructions explain the constant \(1\) lower bound, but CRT only places a solution below the full modulus and gives no deterministic lower bound on an exceptionally small representative of a root class. That is the point at which the elementary radical/primorial argument stalls.

3. Exact finite computation

[d] I exhaustively evaluated every

\[ 5{,}000{,}001\le n\le10{,}000{,}000,\qquad 1\le k\le20. \]

The columns below are the exact minimum of \(A_k(n)\), its least witness, the exact count of \(n\) satisfying the proposed \(A_k(n)\le k\) bound, the exact maximum of \(B_k(n)\), and its least witness.

\(k\)\(\min A_k\)least \(n\)count \(A_k\le k\)\(\max B_k\)least \(n\)
11500001131619489699690
22500001158186115088314
32530841628551165617820
4353084162845195084835
5474649562872235778770
665034933367279702065
765334330679306140076
875334330137336028484
99527097021378081458
101056185371406811077
111154614065435253000
121350378520478193515
131450236220518216394
141550833940536811077
151652506720577899098
161850972470605702760
171885532690647899096
182050972450678650339
192057784320707565970
202256883850737041281

[d] These are sharp finite inequalities: equality occurs at every listed witness. For example, at \(k=3,n=5308416\), the distinct-prime radicals are

\[ (2\cdot3),\quad 5308417,\quad 2\cdot2654209, \]

so \(A_3(n)=2=k-1\). At the unique \(k=10\) target hit \(n=5618537\), the ten radical factorizations are

\[ \begin{split} &5618537;\ 2\cdot3\cdot104047;\ 5618539;\ 2\cdot5\cdot280927;\ 3\cdot1872847;\\ &2\cdot2809271;\ 7\cdot802649;\ 2\cdot3\cdot117053;\ 5\cdot1123709;\ 2\cdot2809273, \end{split} \]

and every term contributes exactly one prime \(>10\).

[d] The zero counts for \(12\le k\le20\) concern only this finite dyadic interval. They are not counterexamples to a liminf assertion.

Reproduction and independent checks

The standalone checker is runs/erdos890_wave6q_verify.py. It uses only the Python standard library:

python3 runs/erdos890_wave6q_verify.py --limit 10000000 --k-max 20

[d] The final run took 48.671 seconds. It performed:

  1. an additive Eratosthenes computation of every \(\omega(m)\) through

\(10{,}000{,}019\);

  1. an independent Euler linear sieve based on least prime factors, comparing

the entire arrays entry by entry;

  1. the exhaustive sliding-window scan;
  2. independent trial division of every minimum and maximum witness;
  3. direct checks of both structural identities in Section 2 on all witnesses.

The two full arrays agreed. The table-row digest was

acd80cca430964ca88247b943b505bc3d30d27c91ed16edcdc89c3aee66a7ef1

and the run ended with PASS.

4. What remains, and realistic compute cost

[a] The report proves the two exact reductions and the sharp finite table; it does not prove either asymptotic assertion.

[c] For the first question, the missing input is a parity-breaking almost-prime-tuple lemma strong enough to leave only \(k\) distinct large primes across \(k\) forms. Dickson/Schinzel supplies it conjecturally; Chen reaches \(3\) rather than \(2\) in the first nontrivial case; Lau supplies \(O(k\log k)\).

[c] For the second question, the missing input is the coefficient-\(1\) uniform maximal-order bound for the reducible polynomial \(\Delta_k(X)=X(X+1)\cdots(X+k-1)\). The ordinary maximal-order theorem loses the full factor \(k\).

[d] A dense extension of the present Python check to \(10^9\) would, by measured linear extrapolation, take at least 1.35 core-hours and peak near 10 GB if both full-array algorithms and Python prime lists were retained; it was therefore not run. A segmented compiled search could lower memory and constants, but no finite cutoff can establish either required infinitude/uniform asymptotic statement.

PARTIAL: Exact identities reduce #890 to a parity-level almost-prime tuple problem and a coefficient-1 maximal-order bound for \(\omega(\prod_{i<k}(n+i))\); an independently rechecked exhaustive scan on \(5{,}000{,}001\le n\le10^7\), \(k\le20\), gives the sharp table above but does not close either open question.

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