Erdoes #890 - working report - Erdős Problem a Day

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

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

[a] elementary-rigorous: proved directly here (or a direct transcription/source fact).
[b] rigorous modulo named theorem: the deduction is rigorous assuming the cited theorem or hypothesis.
[c] plausible/structural-unverified: heuristic, a comment not independently proved here, or a literature-search miss.
[d] computational-only: an exact finite computation, with no asymptotic inference.

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:

status OPEN;
page last edited 03 April 2026;
7 comments;
0 claimed proofs;
“Currently working on this problem”: None;
“Interested in collaborating”: None;
all other interest/difficulty/formalisation-work markers: None;
“Formalised statement?”: Yes.

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 \]

> Is it true that

> \[ > \limsup_{n\to \infty}\left(\sum_{0\leq i \]

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

2. Thomas Bloom (24 Aug 2025) initially questions that reading of the original.

3. 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)$.

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

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

reports revising the first question to the current definition.

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

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

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

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

$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[a] Exact multiplicity bookkeeping gives

\[ B_k(n)=\omega(\Delta_k(n)) +\sum_{pOnly $p \[ 0\le\sum_{pa 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.

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

| 1 | 1 | 5000011 | 316194 | 8 | 9699690 |

| 2 | 2 | 5000011 | 58186 | 11 | 5088314 |

| 3 | 2 | 5308416 | 28551 | 16 | 5617820 |

| 4 | 3 | 5308416 | 2845 | 19 | 5084835 |

| 5 | 4 | 7464956 | 2872 | 23 | 5778770 |

| 6 | 6 | 5034933 | 367 | 27 | 9702065 |

| 7 | 6 | 5334330 | 679 | 30 | 6140076 |

| 8 | 7 | 5334330 | 137 | 33 | 6028484 |

| 9 | 9 | 5270970 | 21 | 37 | 8081458 |

| 10 | 10 | 5618537 | 1 | 40 | 6811077 |

| 11 | 11 | 5461406 | 5 | 43 | 5253000 |

| 12 | 13 | 5037852 | 0 | 47 | 8193515 |

| 13 | 14 | 5023622 | 0 | 51 | 8216394 |

| 14 | 15 | 5083394 | 0 | 53 | 6811077 |

| 15 | 16 | 5250672 | 0 | 57 | 7899098 |

| 16 | 18 | 5097247 | 0 | 60 | 5702760 |

| 17 | 18 | 8553269 | 0 | 64 | 7899096 |

| 18 | 20 | 5097245 | 0 | 67 | 8650339 |

| 19 | 20 | 5778432 | 0 | 70 | 7565970 |

| 20 | 22 | 5688385 | 0 | 73 | 7041281 |

[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$;

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

the entire arrays entry by entry;

3. the exhaustive sliding-window scan;

4. independent trial division of every minimum and maximum witness;

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

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