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

Erdős problem #850 — wave 6n report

Date: 2026-07-27 UTC

Disposition: PARTIAL. (d, live-page observation) The problem remains open. The outputs are (i) an (a) elementary necessary-condition reduction, (ii) a (d) from-scratch exact exclusion for the larger member $y\le 10^9$, and (iii) a (b) stronger exclusion $y<1.4\cdot 10^{12}$ modulo a directly relevant published computational theorem that is not cited on the live problem page.

Claim labels

The requested labels are used on every substantive mathematical conclusion:

(a) elementary-rigorous;
(b) rigorous modulo the explicitly named theorem;
(c) plausible/structural-unverified or a cost estimate;
(d) computational-only.

Unlabelled material below is a definition, verbatim quotation, command, bibliographic record, or description of what a source says.

0. Mandatory live-page check

(d, live-page observation) I accessed both the live problem page and its discussion thread through the Bright Data browser path on 2026-07-27. The problem page displayed:

OPEN;
0 claimed proofs for this problem;
Interested in collaborating None;
Currently working on this problem None;
Likes this problem 0xashrk;
This problem looks difficult aminb_el, Dogmachine;
This problem looks tractable None;
The results on this problem could be formalisable None;
I am working on formalising the results on this problem None.

Thus no mandatory stop condition was present.

Verbatim live statement

Can there exist two distinct integers $x$ and $y$ such that $x,y$ have the same prime factors, $x+1,y+1$ have the same prime factors, and $x+2,y+2$ also have the same prime factors?

(d, live-page observation) The four comments, all dated 19 January 2026, were also read. Neel Somani asked whether positive integers should be made explicit; Thomas Bloom replied that the intended restriction is $x,y\ge 1$; Somani acknowledged this; Terence Tao suggested making such contextual hypotheses explicit, especially for automated attacks, and noted that the Lean formalisation has the intended domain. None of the comments claims a proof or says that anyone is currently working on the problem. Accordingly, this report uses positive integers.

(d, live-page observation) The page's listed mathematical context is:

the name “Erdős-Woods conjecture”;
for only the first two comparisons, the family

$x=2(2^r-1)$, $y=x(x+2)$;

Makowski's additional first-two-term pair $(75,1215)$;
no other first-two-term examples known, with OEIS A343101 cited;
Shorey and Tijdeman's negative answer to the three-term question under

Baker's strong explicit $abc$ conjecture;

cross-reference #677, the 2011 Benelux olympiad problem, and Guy B19.

The page said it was last edited 28 September 2025.

1. Primary-source literature audit

These are the specific hits I opened and checked; none claims an unconditional solution of #850.

(d, search observation) Exact-title/statement searches over arXiv and the web, including 2025–2026 date terms, found no later primary source claiming a resolution. The newest directly relevant primary items I found were Hercher and Lebowitz-Lockard below. This is a search report, not a theorem that no other literature exists.

P. Erdős, [*Quelques problèmes de la théorie des

nombres*](https://static.renyi.hu/~p_erdos/1963-14.pdf), Enseignement Mathématique 6 (1963), Problem 60. The source records the standard two-term family and asks for other two-term examples.

A. Makowski, [*On a problem of

Erdős*](https://www.e-periodica.ch/cntmng?pid=ens-001%3A1968%3A14%3A%3A87), Enseignement Mathématique 14 (1968), p. 193. The paper explicitly gives $75,1215$ for the two-term problem.

R. Balasubramanian, T. N. Shorey, and M. Waldschmidt,

On the maximal length of two sequences of consecutive integers with the same prime divisors, Acta Math. Hung. 54 (1989), 225–236, DOI 10.1007/BF01952052. It gives unconditional bounds on the possible length, not a resolution at length three.

T. N. Shorey and R. Tijdeman, [*Arithmetic properties of blocks of

consecutive integers*](https://arxiv.org/abs/1612.05438), arXiv:1612.05438, Theorem 9.1. I checked the source text of the theorem and proof: Baker's explicit $abc$ conjecture implies that no positive $n_1<n_2$ have equal prime supports at offsets $0,1,2$.

N. Lebowitz-Lockard, [*On pairs of consecutive sequences with the same

radicals*](https://arxiv.org/abs/2507.09899), arXiv:2507.09899 (14 July 2025). This preprint explicitly says the three-term problem is unresolved and proves broader length/counting bounds. It does not settle existence at length three.

Most importantly, C. Hercher, [*On One of Erdős' Problems—An Efficient

Search for Benelux Pairs*](https://cs.uwaterloo.ca/journals/JIS/VOL28/Hercher3/hercher15.pdf), Journal of Integer Sequences 28 (2025), Article 25.8.5, published 12 December 2025; see also arXiv:2506.01099. Theorem 1 classifies every two-term Benelux pair $m<n<1.4\cdot10^{12}$. The paper links its archived CUDA source repository, whose current commit I checked as 54b80aca0fd9b7bc33b13f65cc00b50824e90082. The repository contains the program but no completion log or independently checkable certificate for the month-long search. I therefore use the $1.4\cdot10^{12}$ result only with label (b), and do not present it as my own computational verification.

2. Elementary reduction

Write

\operatorname{rad}(n)=\prod_{p\mid n}p

and suppose, without loss of generality, that $1\le x<y$. Put $d=y-x$, and for $i=0,1,2$ put

r_i=\operatorname{rad}(x+i)=\operatorname{rad}(y+i).

Define

R=\operatorname{lcm}(r_0,r_1,r_2) =\operatorname{rad}\bigl(y(y+1)(y+2)\bigr).

Divisibility lemma

(a) Every putative solution satisfies

R\mid d \quad\text{and hence}\quad R\le d=y-x<y. \tag{1}

Proof. If $p\mid y+i$, equality of prime supports gives $p\mid x+i$. Therefore $p\mid(y+i)-(x+i)=d$. Thus $r_i\mid d$ for each $i$, so their least common multiple $R$ divides $d$. Positivity gives $d<y$.

This yields a one-variable obstruction:

(a) If

\operatorname{rad}\bigl(n(n+1)(n+2)\bigr)\ge n \tag{2}

for every $n\le Y$, then #850 has no solution whose larger member is at most $Y$. This implication loses information, so a value violating (2) would only be a candidate, not a counterexample.

Two further consequences are useful:

(a) Each of $y,y+1,y+2$ must be non-squarefree. If $y+i$ were squarefree, then $r_i=y+i>d$, contradicting $r_i\mid d$.

(a) The gap has the exact form

y-x=tR\qquad(t\in\mathbb Z_{\ge1}). \tag{3}

Fixed-support formulation

Let $S_i$ be the prime support of $x+i$ (equivalently $y+i$).

(a) Apart from the prime $2$, the three sets $S_0,S_1,S_2$ are disjoint. The only possible overlap is $2\in S_0\cap S_2$, when $x,y$ are even. Both $x$ and $y$ obey

n\equiv0\pmod p\ (p\in S_0),\qquad n\equiv-1\pmod p\ (p\in S_1),\qquad n\equiv-2\pmod p\ (p\in S_2). \tag{4}

The generalized Chinese remainder theorem therefore puts both numbers in one residue class modulo $R$; equation (3) is the resulting gap.

(b, Størmer's theorem) For a fixed finite union $S=S_0\cup S_1\cup S_2$, there are only finitely many consecutive $S$-smooth pairs $n,n+1$, and they can be enumerated via finitely many Pell equations. See D. H. Lehmer, On a problem of Størmer, Illinois J. Math. 8 (1964), 57–79 (Project Euclid, DOI 10.1215/ijm/1256067456). Consequently each fixed support partition is decidable. The unresolved uniform step is that $S$, $R$, and the exponents are all unbounded.

3. Independent exact computation

The standalone checker is runs/erdos850_wave6n_reverify.py, SHA-256

23860a2cc711bed3458d14c9d29eea904444068cdfc790151f656e6be141cd84

It has no factoring/database dependency; NumPy is used only for exact fixed-width array operations.

Algorithm and correctness

(a) The radical sieve starts with r[n] = n. For every prime $p$ and every power $p^e\le Y+2$, $e\ge2$, it divides all multiples of $p^e$ by $p$. If $v_p(n)=a$, the entry is divided once for each $e=2,\ldots,a$, leaving exactly one factor $p$. Hence the resulting array is exactly $\operatorname{rad}(n)$.

For

a=\operatorname{rad}(n),\quad b=\operatorname{rad}(n+1),\quad c=\operatorname{rad}(n+2),

consecutive-number coprimality gives

\operatorname{rad}(n(n+1)(n+2)) =ab\,\frac{c}{\gcd(a,c)}. \tag{5}

(a) For $Y\le2^{32}-2$, $ab\le n(n+1)<2^{64}$, so the first product is exact in uint64. The final product is not formed in fixed width:

ab\,f<n\iff ab\le\left\lfloor\frac{n-1}{f}\right\rfloor,\qquad f=c/\gcd(a,c),

which makes the comparison overflow-free.

The code independently audits the fast sieve against:

a differently ordered prime-multiple radical sieve for every

$0\le n\le200000$; and

ordinary trial division at 64 deterministic checkpoints spread through

the full range.

It also trial-factors every candidate appearing in Hercher's classification; this arithmetic audit is separate from the billion-value necessary-condition scan.

Reproduction command

python3 runs/erdos850_wave6n_reverify.py \
  --limit 1000000000 --audit-limit 200000

The run made on this VM used NumPy 2.4.4. Its essential output was:

building exact radicals through 1,000,000,002 ...
radical sieve seconds: 76.006
independent radical-sieve audit: 0..200000 OK
full-range trial-factor checkpoints: 64 OK
necessary-condition scan: no y <= 1,000,000,000 has rad(y(y+1)(y+2)) < y
preliminary rad(y)*rad(y+1) < y cases: 845
global minimum R/y in the scanned range: y=2, R=6,
    reduced_ratio=3/1, decimal=3
total seconds: 94.100
RESULT no_necessary_condition_hits=True limit=1000000000

/usr/bin/time -v reported 94.49 seconds wall time, 55.14 seconds user time, 40.93 seconds system time, and peak RSS 8,004,124 KiB.

(d) For every $1\le n\le10^9$, the computation found the stronger finite-range inequality

\operatorname{rad}(n(n+1)(n+2))\ge3n,

and $n=2$ attains equality. The checker did not count all equality cases, so no uniqueness claim is made.

(a)+(d) Combining this exact scan with (1) proves that no #850 counterexample has larger member $y\le10^9$. The word “proves” here is finite/computational, not a uniform theorem.

4. The stronger literature corollary

Hercher's Theorem 1 says that every first-kind Benelux pair $m<n<1.4\cdot10^{12}$ is one of

\[ (75,1215) \]

m=2^k-2,\qquad n=2^k(2^k-2),\qquad 2\le k\le20. \tag{6}

Every #850 pair is in particular a first-kind Benelux pair, so only these listed candidates need their third terms checked.

(a) The exceptional candidate fails because

\operatorname{rad}(75+2)=\operatorname{rad}(77)=77,\qquad \operatorname{rad}(1215+2)=\operatorname{rad}(1217)=1217.

Trial division by the primes at most $\sqrt{1217}<35$ verifies that 1217 is prime.

(a) Every member of (6) fails uniformly:

m+2=2^k,\qquad n+2=2\bigl(2^{2k-1}-2^k+1\bigr).

The parenthesized factor is odd and at least $5$ for $k\ge2$. Hence $\operatorname{rad}(m+2)=2$, while $\operatorname{rad}(n+2)$ contains an odd prime.

The standalone checker independently emitted the full arithmetic table. Its endpoints and exceptional row are:

kind/$k$	$m$	$n$	$\operatorname{rad}(m+2)$	$\operatorname{rad}(n+2)$
exceptional	75	1,215	77	1,217
2	2	8	2	10
20	1,048,574	1,099,509,530,624	2	84,577,656,202

(b, Hercher Theorem 1) There is no #850 counterexample with

1\le x<y<1.4\cdot10^{12}. \tag{7}

This is the strongest concrete exclusion found in the literature search. Its classification premise is Hercher's published computation; my script verifies the deduction and all listed candidates but does not reproduce that month-long exhaustive search.

5. Why the argument does not become uniform

The elementary identity

y(y+2)+1=(y+1)^2 \tag{8}

has

\operatorname{rad}\bigl(y(y+1)(y+2)\bigr)=R<y

for a putative solution.

(b, ordinary $abc$ conjecture) Applying $abc$ to (8), with any $\varepsilon<1$, gives

(y+1)^2\le C_\varepsilon R^{1+\varepsilon} <C_\varepsilon y^{1+\varepsilon}.

Thus ordinary $abc$ leaves at most finitely many $y$, but its unspecified constant does not eliminate the finite exceptional set.

(b, Shorey–Tijdeman Theorem 9.1) Baker's stronger explicit $abc$ conjecture yields

y^2<R^{7/4}<y^{7/4},

an immediate contradiction. This is exactly why the conditional result closes the problem while ordinary $abc$ gives only finiteness.

(b, Stewart–Yu's unconditional $abc$-type bound) The available unconditional shape

(y+1)^2< \exp\!\left(CR^{1/3}(\log R)^3\right)

does not contradict $R<y$; the right side is much larger than $y^2$ for large $y$. Hence this standard machinery stalls at the precise missing power-law radical estimate.

An exact sufficient lemma would be

\operatorname{rad}(n(n+1)(n+2))\ge n \quad\text{for every positive }n. \tag{9}

(c) Lemma (9) is structurally plausible from the computation but is unproved here and must not be treated as a theorem. It is a special high-quality $abc$ assertion for (8); proving it uniformly, or exploiting the separate supports $S_0,S_1,S_2$ to bypass it, is the exact analytic wall.

Cost of extending only the finite scan

The $10^9$ run consumed about 96 CPU-seconds. A full unsegmented array to $1.4\cdot10^{12}$ would require about 11.2 TB, so scaling requires a segmented implementation.

(c, measured scaling estimate) Ideal linear scaling of the observed run to $1.4\cdot10^{12}$ is about 38 core-hours; allowing for segmentation and prime-loop overhead gives roughly 50–80 core-hours, or about 2–3 wall hours on 32 cores. At a realistic \$0.05–\$0.10 per core-hour, compute cost is roughly \$2.50–\$8, excluding engineering and storage. A scan to $10^{13}$ would be roughly 350–600 core-hours. I did not run either job here. Even such a scan would establish only a larger finite bound and could not close the unbounded problem without an analytic finiteness/uniformity step.

6. Verified state

(a) Any solution forces

$\operatorname{rad}(y(y+1)(y+2))\mid(y-x)<y$, puts both triples in one CRT class modulo that radical, and makes $y,y+1,y+2$ all non-squarefree.

(d) The necessary inequality fails for every $y\le10^9$; the exact

scan actually found $R(y)\ge3y$ throughout this range.

(b) Modulo Hercher's published Theorem 1, every

$y<1.4\cdot10^{12}$ is excluded after an elementary check of his complete two-term candidate list.

(c) No construction, counterexample, or unconditional uniform proof was

found. The missing step is a uniform radical lower bound such as (9), or a genuinely uniform use of the three separate prime-support sets.

PARTIAL: elementary reduction and an independent exact scan exclude y<=10^9; modulo Hercher's published exhaustive Theorem 1, all y<1.4e12 are excluded, but the unbounded problem remains open.

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