Erdős Problem #850

Erdős Problem 850 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/850.tex.

REUSED SOURCE 1

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? This is sometimes known as the Erdős-Woods conjecture. For just $x,y$ and $x+1,y+1$ one can take\[x=2(2^r-1)\]and\[y = x(x+2).\]Erdős also asked whether there are any other examples. Makowski [Ma68] observed that $x=75$ and $y=1215$ is another example, since\[75 = 3\cdot 5^2 \textrm{ and }1215 = 3^5\cdot 5\]while\[76 = 2^2\cdot 19\textrm{ and }1216 = 2^6\cdot 19.\](This example was also found independently by Matthew Bolan, and by Dubickas, who posed it as part of the 2024 team selection test in Lithuania.) No other examples are known. This sequence is listed as A343101 at the OEIS. Shorey and Tijdeman [ShTi16] have shown that, assuming a strong form of the ABC conjecture due to Baker, then the answer to the original problem is no. See also [677] . The case of $x,y$ and $x+1,y+1$ appeared as Problem 1 in the Third Benelux Mathematical Olympiad 2011. This problem is discussed in problem B19 of Guy's collection [Gu04]. References [Gu04] Guy, Richard K., Unsolved problems in number theory . $2004$, xviii+437. [Ma68] Makowski, Andrzej, On a problem of {E}rdős . Enseign. Math. $2$ $1968$, 193. [ShTi16] Shorey, Tarlok N. and Tijdeman, Rob, Arithmetic properties of blocks of consecutive integers . $2016$, 455--471.

1) “FORMAL RESTATEMENT”

Ambiguity note: The phrase “prime factors” is standard for positive integers. For negative integers one typically means prime factors of $|n|$, and for $0$ the notion is undefined. The minimal corrected reading consistent with standard conventions is: $x,y\in\mathbb{N}$ are distinct positive integers.

Define $\operatorname{rad}(n):=\prod_{p\mid n} p$ for $n\in\mathbb{N}$ (product of distinct primes dividing $n$). The condition “$u$ and $v$ have the same prime factors” is $\operatorname{rad}(u)=\operatorname{rad}(v)$.

Question: Do there exist distinct $x,y\in\mathbb{N}$ such that \[ \operatorname{rad}(x)=\operatorname{rad}(y),\quad \operatorname{rad}(x+1)=\operatorname{rad}(y+1),\quad \operatorname{rad}(x+2)=\operatorname{rad}(y+2)? \]

2) “QUICK LITERATURE/CONTEXT CHECK”

The problem statement itself provides: - An infinite family of examples satisfying the first two equalities (for $x,y$ and $x+1,y+1$) with $x=2(2^r-1)$ and $y=x(x+2)$. - Another example for the first two equalities: $(x,y)=(75,1215)$. - Conditional on a strong ABC conjecture (Baker form), Shorey--Tijdeman show nonexistence for the full three-shift condition.

In this write-up I do not invoke external literature beyond what is explicitly stated in the problem text.

3) “ATTACK PLAN”

Proof-track ideas (to prove nonexistence): - Use congruence/valuation constraints across the three consecutive integers and compare prime supports. - Try to force strong algebraic relations from $\operatorname{rad}(x+i)=\operatorname{rad}(y+i)$ for $i=0,1,2$.

Disproof/construction ideas (to build an example): - Extend the known “square trick” $y+1=(x+1)^2$ from the two-shift construction and try to simultaneously enforce $\operatorname{rad}(x+2)=\operatorname{rad}(y+2)$.

Best current path in this write-up: verify the given two-shift construction, record necessary structural constraints for any hypothetical three-shift solution, and run a computational search for small solutions.

4) “WORK”

FAST REALITY CHECK (computation): I computed $\operatorname{rad}(n)$ for all $n\le 1{,}000{,}002$ by a sieve and checked whether any two distinct $x<y\le 1{,}000{,}000$ share the same triple \[ (\operatorname{rad}(x),\operatorname{rad}(x+1),\operatorname{rad}(x+2)). \] No collisions were found in this range; hence there are no solutions with $1\le x<y\le 10^6$.

Lemma 850.1 (Verification of the Erdős two-shift construction). Fix an integer $r\ge 1$ and set \[ x=2(2^r-1),\qquad y=x(x+2). \] Then $\operatorname{rad}(x)=\operatorname{rad}(y)$ and $\operatorname{rad}(x+1)=\operatorname{rad}(y+1)$.

Proof. First compute $x+2=2(2^r-1)+2=2^{r+1}$. Hence \[ y=x(x+2)=x\cdot 2^{r+1}. \] Multiplying an integer by a power of $2$ does not introduce any new odd prime factors. Since $x$ is even, $2$ already divides $x$, so the set of primes dividing $y$ is exactly the set of primes dividing $x$. Therefore $\operatorname{rad}(y)=\operatorname{rad}(x)$.

Next, \[ y+1=x(x+2)+1 = x^2+2x+1=(x+1)^2. \] Thus $x+1$ and $y+1$ have exactly the same prime divisors (squaring does not change the set of prime divisors), so $\operatorname{rad}(y+1)=\operatorname{rad}(x+1)$. $\square$

Lemma 850.2 (Prime-support disjointness across consecutive integers). For any integer $n\ge 1$: - $\gcd(n,n+1)=\gcd(n+1,n+2)=1$. - $\gcd(n,n+2)\mid 2$. Consequently, the sets of prime divisors of $n$ and $n+1$ are disjoint, as are those of $n+1$ and $n+2$. The sets of prime divisors of $n$ and $n+2$ intersect only possibly in the prime $2$.

Proof. Consecutive integers are coprime: if a prime $p$ divides both $n$ and $n+1$, then $p$ divides their difference $1$, impossible; hence $\gcd(n,n+1)=1$. Similarly $\gcd(n+1,n+2)=1$.

Also $\gcd(n,n+2)$ divides the difference $(n+2)-n=2$, so $\gcd(n,n+2)\mid 2$. The prime-support statements follow immediately from these gcd facts. $\square$

Lemma 850.3 (The Makowski example satisfies two shifts but fails the third). Let $x=75$ and $y=1215$. Then $\operatorname{rad}(x)=\operatorname{rad}(y)$ and $\operatorname{rad}(x+1)=\operatorname{rad}(y+1)$, but $\operatorname{rad}(x+2)\ne \operatorname{rad}(y+2)$.

Proof. Factorizations: \[ 75=3\cdot 5^2\ \Rightarrow\ \operatorname{rad}(75)=3\cdot 5, \] \[ 1215=3^5\cdot 5\ \Rightarrow\ \operatorname{rad}(1215)=3\cdot 5. \] So $\operatorname{rad}(x)=\operatorname{rad}(y)$.

Also \[ 76=2^2\cdot 19\ \Rightarrow\ \operatorname{rad}(76)=2\cdot 19, \] \[ 1216=2^6\cdot 19\ \Rightarrow\ \operatorname{rad}(1216)=2\cdot 19. \] So $\operatorname{rad}(x+1)=\operatorname{rad}(y+1)$.

Finally $x+2=77=7\cdot 11$, so $\operatorname{rad}(x+2)=7\cdot 11=77$. Meanwhile $y+2=1217$; a direct check shows $1217$ is not divisible by $2,3,5,7,11,13,17,19,23,29,31$ (all primes up to $\sqrt{1217}<35$), hence $1217$ is prime and $\operatorname{rad}(y+2)=1217\ne 77$. $\square$

5) “VERIFICATION”

- Lemma 850.1: the key identity $y+1=(x+1)^2$ is exact, and the prime-support conclusions use only basic facts about prime divisors under multiplication by powers and squaring. - Lemma 850.2: gcd arguments are standard and fully justified. - The computational search was exhaustive for all $1\le x\le 10^6$ by hashing the radical triples; any solution with both $x,y\le 10^6$ would have been found as a collision.

6) FINAL

UNRESOLVED (i) Strongest fully proved partial result: The Erdős construction $x=2(2^r-1),y=x(x+2)$ yields infinitely many examples satisfying the first two radical equalities (Lemma 850.1). Any hypothetical three-shift solution must respect strong prime-support disjointness across $x,x+1,x+2$ (Lemma 850.2). A brute-force search finds no solutions with $1\le x<y\le 10^6$. (ii) First gap (crisp): Either produce explicit distinct $x,y$ with $\operatorname{rad}(x+i)=\operatorname{rad}(y+i)$ for $i=0,1,2$, or prove that no such pair exists unconditionally. (iii) Top 3 next moves: 1. Strengthen Lemma 850.2 with valuation constraints: analyze $v_p(x+i)$ versus $v_p(y+i)$ for each prime $p$ dividing the common radicals, aiming to force algebraic relations that contradict $x\ne y$. 2. Extend computation beyond $10^6$ using the same collision-hash method (it scales linearly) and also search in constrained families inspired by Lemma 850.1 (e.g. enforce $y+1=(x+1)^2$ and test $x+2,y+2$). 3. Try to show that simultaneously matching radicals for three consecutive integers forces $x$ and $y$ to be extremely close or to satisfy a rigid multiplicative dependence, then contradict with size/prime-support arguments. (iv) Minimal counterexample structure (if it exists): A pair $x<y$ where the three consecutive integers $x,x+1,x+2$ and $y,y+1,y+2$ have exactly the same prime supports term-by-term, with exponents rearranged. Lemma 850.2 shows the prime supports for the three terms are almost disjoint (except possibly $2$ between the even terms), so any counterexample must carefully balance three disjoint prime sets across the two triples.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

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? This is sometimes known as the Erdős-Woods conjecture. For just $x,y$ and $x+1,y+1$ one can take\[x=2(2^r-1)\]and\[y = x(x+2).\]Erdős also asked whether there are any other examples. Makowski [Ma68] observed that $x=75$ and $y=1215$ is another example, since\[75 = 3\cdot 5^2 \textrm{ and }1215 = 3^5\cdot 5\]while\[76 = 2^2\cdot 19\textrm{ and }1216 = 2^6\cdot 19.\](This example was also found independently by Matthew Bolan, and by Dubickas, who posed it as part of the 2024 team selection test in Lithuania.) No other examples are known. This sequence is listed as A343101 at the OEIS. Shorey and Tijdeman [ShTi16] have shown that, assuming a strong form of the ABC conjecture due to Baker, then the answer to the original problem is no. See also [677] . The case of $x,y$ and $x+1,y+1$ appeared as Problem 1 in the Third Benelux Mathematical Olympiad 2011. This problem is discussed in problem B19 of Guy's collection [Gu04]. References [Gu04] Guy, Richard K., Unsolved problems in number theory . $2004$, xviii+437. [Ma68] Makowski, Andrzej, On a problem of {E}rdős . Enseign. Math. $2$ $1968$, 193. [ShTi16] Shorey, Tarlok N. and Tijdeman, Rob, Arithmetic properties of blocks of consecutive integers . $2016$, 455--471.

1) “FORMAL RESTATEMENT”

Ambiguity note: The phrase “prime factors” is standard for positive integers. For negative integers one typically means prime factors of $|n|$, and for $0$ the notion is undefined. The minimal corrected reading consistent with standard conventions is: $x,y\in\mathbb{N}$ are distinct positive integers.

Define $\operatorname{rad}(n):=\prod_{p\mid n} p$ for $n\in\mathbb{N}$ (product of distinct primes dividing $n$). The condition “$u$ and $v$ have the same prime factors” is $\operatorname{rad}(u)=\operatorname{rad}(v)$.

Question: Do there exist distinct $x,y\in\mathbb{N}$ such that \[ \operatorname{rad}(x)=\operatorname{rad}(y),\quad \operatorname{rad}(x+1)=\operatorname{rad}(y+1),\quad \operatorname{rad}(x+2)=\operatorname{rad}(y+2)? \]

2) “QUICK LITERATURE/CONTEXT CHECK”

The problem statement itself provides: - An infinite family of examples satisfying the first two equalities (for $x,y$ and $x+1,y+1$) with $x=2(2^r-1)$ and $y=x(x+2)$. - Another example for the first two equalities: $(x,y)=(75,1215)$. - Conditional on a strong ABC conjecture (Baker form), Shorey--Tijdeman show nonexistence for the full three-shift condition.

In this write-up I do not invoke external literature beyond what is explicitly stated in the problem text.

3) “ATTACK PLAN”

Proof-track ideas (to prove nonexistence): - Use congruence/valuation constraints across the three consecutive integers and compare prime supports. - Try to force strong algebraic relations from $\operatorname{rad}(x+i)=\operatorname{rad}(y+i)$ for $i=0,1,2$.

Disproof/construction ideas (to build an example): - Extend the known “square trick” $y+1=(x+1)^2$ from the two-shift construction and try to simultaneously enforce $\operatorname{rad}(x+2)=\operatorname{rad}(y+2)$.

Best current path in this write-up: verify the given two-shift construction, record necessary structural constraints for any hypothetical three-shift solution, and run a computational search for small solutions.

4) “WORK”

FAST REALITY CHECK (computation): I computed $\operatorname{rad}(n)$ for all $n\le 1{,}000{,}002$ by a sieve and checked whether any two distinct $x<y\le 1{,}000{,}000$ share the same triple \[ (\operatorname{rad}(x),\operatorname{rad}(x+1),\operatorname{rad}(x+2)). \] No collisions were found in this range; hence there are no solutions with $1\le x<y\le 10^6$.

Lemma 850.1 (Verification of the Erdős two-shift construction). Fix an integer $r\ge 1$ and set \[ x=2(2^r-1),\qquad y=x(x+2). \] Then $\operatorname{rad}(x)=\operatorname{rad}(y)$ and $\operatorname{rad}(x+1)=\operatorname{rad}(y+1)$.

Proof. First compute $x+2=2(2^r-1)+2=2^{r+1}$. Hence \[ y=x(x+2)=x\cdot 2^{r+1}. \] Multiplying an integer by a power of $2$ does not introduce any new odd prime factors. Since $x$ is even, $2$ already divides $x$, so the set of primes dividing $y$ is exactly the set of primes dividing $x$. Therefore $\operatorname{rad}(y)=\operatorname{rad}(x)$.

Next, \[ y+1=x(x+2)+1 = x^2+2x+1=(x+1)^2. \] Thus $x+1$ and $y+1$ have exactly the same prime divisors (squaring does not change the set of prime divisors), so $\operatorname{rad}(y+1)=\operatorname{rad}(x+1)$. $\square$

Lemma 850.2 (Prime-support disjointness across consecutive integers). For any integer $n\ge 1$: - $\gcd(n,n+1)=\gcd(n+1,n+2)=1$. - $\gcd(n,n+2)\mid 2$. Consequently, the sets of prime divisors of $n$ and $n+1$ are disjoint, as are those of $n+1$ and $n+2$. The sets of prime divisors of $n$ and $n+2$ intersect only possibly in the prime $2$.

Proof. Consecutive integers are coprime: if a prime $p$ divides both $n$ and $n+1$, then $p$ divides their difference $1$, impossible; hence $\gcd(n,n+1)=1$. Similarly $\gcd(n+1,n+2)=1$.

Also $\gcd(n,n+2)$ divides the difference $(n+2)-n=2$, so $\gcd(n,n+2)\mid 2$. The prime-support statements follow immediately from these gcd facts. $\square$

Lemma 850.3 (The Makowski example satisfies two shifts but fails the third). Let $x=75$ and $y=1215$. Then $\operatorname{rad}(x)=\operatorname{rad}(y)$ and $\operatorname{rad}(x+1)=\operatorname{rad}(y+1)$, but $\operatorname{rad}(x+2)\ne \operatorname{rad}(y+2)$.

Proof. Factorizations: \[ 75=3\cdot 5^2\ \Rightarrow\ \operatorname{rad}(75)=3\cdot 5, \] \[ 1215=3^5\cdot 5\ \Rightarrow\ \operatorname{rad}(1215)=3\cdot 5. \] So $\operatorname{rad}(x)=\operatorname{rad}(y)$.

Also \[ 76=2^2\cdot 19\ \Rightarrow\ \operatorname{rad}(76)=2\cdot 19, \] \[ 1216=2^6\cdot 19\ \Rightarrow\ \operatorname{rad}(1216)=2\cdot 19. \] So $\operatorname{rad}(x+1)=\operatorname{rad}(y+1)$.

Finally $x+2=77=7\cdot 11$, so $\operatorname{rad}(x+2)=7\cdot 11=77$. Meanwhile $y+2=1217$; a direct check shows $1217$ is not divisible by $2,3,5,7,11,13,17,19,23,29,31$ (all primes up to $\sqrt{1217}<35$), hence $1217$ is prime and $\operatorname{rad}(y+2)=1217\ne 77$. $\square$

5) “VERIFICATION”

- Lemma 850.1: the key identity $y+1=(x+1)^2$ is exact, and the prime-support conclusions use only basic facts about prime divisors under multiplication by powers and squaring. - Lemma 850.2: gcd arguments are standard and fully justified. - The computational search was exhaustive for all $1\le x\le 10^6$ by hashing the radical triples; any solution with both $x,y\le 10^6$ would have been found as a collision.

6) FINAL

UNRESOLVED (i) Strongest fully proved partial result: The Erdős construction $x=2(2^r-1),y=x(x+2)$ yields infinitely many examples satisfying the first two radical equalities (Lemma 850.1). Any hypothetical three-shift solution must respect strong prime-support disjointness across $x,x+1,x+2$ (Lemma 850.2). A brute-force search finds no solutions with $1\le x<y\le 10^6$. (ii) First gap (crisp): Either produce explicit distinct $x,y$ with $\operatorname{rad}(x+i)=\operatorname{rad}(y+i)$ for $i=0,1,2$, or prove that no such pair exists unconditionally. (iii) Top 3 next moves: 1. Strengthen Lemma 850.2 with valuation constraints: analyze $v_p(x+i)$ versus $v_p(y+i)$ for each prime $p$ dividing the common radicals, aiming to force algebraic relations that contradict $x\ne y$. 2. Extend computation beyond $10^6$ using the same collision-hash method (it scales linearly) and also search in constrained families inspired by Lemma 850.1 (e.g. enforce $y+1=(x+1)^2$ and test $x+2,y+2$). 3. Try to show that simultaneously matching radicals for three consecutive integers forces $x$ and $y$ to be extremely close or to satisfy a rigid multiplicative dependence, then contradict with size/prime-support arguments. (iv) Minimal counterexample structure (if it exists): A pair $x<y$ where the three consecutive integers $x,x+1,x+2$ and $y,y+1,y+2$ have exactly the same prime supports term-by-term, with exponents rearranged. Lemma 850.2 shows the prime supports for the three terms are almost disjoint (except possibly $2$ between the even terms), so any counterexample must carefully balance three disjoint prime sets across the two triples.