Erdős problem 1003 — wave7z report
Date: 2026-07-28 UTC
Claim labels used throughout:
- (a) elementary-rigorous: proved here from elementary facts.
- (b) rigorous-modulo-named-theorem: depends on the cited theorem, paper, or deterministic primality theorem.
- (c) plausible/structural-unverified: heuristic, a forum claim not checked in full, or a proposed direction.
- (d) computational-only: an exhaustive result only in the explicitly stated finite range.
0. Mandatory live-page check
I accessed the fully rendered live problem page and its discussion thread through the Bright Data browser on 2026-07-28. Direct text extraction was repeated after a 15-second render wait. (b)
The verbatim current statement is:
> Are there infinitely many solutions to \(\phi(n)=\phi(n+1)\), where \(\phi\) is the Euler totient function?
The live status is OPEN. The page says “0 claimed proofs for this problem” and “Currently working on this problem: None,” so no stop condition applies. It was last edited 19 April 2026. It lists five comments. The other markers are: likes — graszssss, Alfaiz, RomanLeLan, Steve_Fan; interested in collaborating — None; looks difficult — None; looks tractable — None; results could be formalisable — None; working on formalising the results — None. It also links OEIS A001274 and says a formalised statement exists. (b)
The known results printed on the live page are:
- Erdős says that, presumably, for every \(k\geq1\),
\[ \phi(n)=\phi(n+1)=\cdots=\phi(n+k) \]
has infinitely many solutions. (b)
- Erdős, Pomerance, and Sárközy proved that
\[ S(x):=\#\{n\leq x:\phi(n)=\phi(n+1)\} \leq \frac{x}{\exp((\log x)^{1/3})} \]
for sufficiently large \(x\). (b)
- It points to problems 946 (the divisor-function analogue) and 415 (inequality patterns among consecutive totients). (b)
All five comments were read:
1. Steve Fan (23 February 2026) proposes a stronger upper bound
\[ x\exp\!\left(-c_0\bigl(\log x\,\log\log x\,\log\log\log x\bigr)^{1/3}\right) \]
by changing two parameters in the 1987 proof and invoking Theorem 1.1 of Banks–Friedlander–Pomerance–Shparlinski. This is a forum derivation, not a posted proof, so I record it only as (c). The cited paper and its theorem do exist.
2. Alfaiz (22 February 2026) points to the literature on fixed shifts, especially Kevin Ford’s paper. The paper and arXiv identifier 2002.12155 were verified. (b)
3. Terence Tao (30 October 2025) gives the standard \(k=2\) construction from primes \(p,2p-1\), and explains why the unit shift cannot persist with a fixed small number of prime factors. The latter assertion is proved independently below as Theorem 4. (a)
4. Steve Fan (30 October 2025) identifies the upper-bound source as Theorem 2 of On locally repeated values of certain arithmetic functions, II, Acta Math. Hungar. 49 (1987), 251–259. The primary PDF confirms this. (b)
5. Stijn Cambie (30 October 2025) notes that the 1987 authors explicitly say they cannot prove infinitude. The primary PDF confirms the substance of this comment. (b)
There is a bibliographic inconsistency worth flagging. The live page’s LaTeX reference panel currently expands EPS87 as paper “III” in Proc. AMS, while the theorem is actually in paper “II” in Acta Math. Hungar., as the live comments and primary PDF state. (b)
1. Primary-source literature audit
I searched the exact equation, its title variants, and the cited papers. The following primary sources were opened and checked; I did not find a later primary source claiming to settle the unit-shift problem.
1. P. Erdős, Some problems and results in number theory, in Number Theory and Combinatorics, Japan 1984 (1985), 65–87. Page 67 states the consecutive-totient conjecture and says even \(k=1\) seems unattackable. (b)
2. P. Erdős, C. Pomerance, A. Sárközy, On locally repeated values of certain arithmetic functions, II, Acta Math. Hungar. 49 (1987), 251–259. Theorem 2 gives the displayed \(x/\exp((\log x)^{1/3})\) upper bound, and the authors conjecture \(S(x)\geq x^{1-\varepsilon}\) eventually while saying infinitude itself is unknown. (b)
3. T. Yamada, On equations \(\sigma(n)=\sigma(n+k)\) and \(\phi(n)=\phi(n+k)\), arXiv:1001.2511v2; J. Combin. Number Theory 9 (2017), 15–21. Corollary 1.3 gives, for odd fixed \(k\),
\[ \#\{n\leq x:\phi(n)=\phi(n+k)\} \ll x\exp\!\left(-(2^{-1/2}+o(1)) \sqrt{\log x\,\log\log\log x}\right). \]
Thus the live page does not display the strongest verified published asymptotic upper bound I found. (b)
4. P. Kinlaw, M. Kobayashi, C. Pomerance, On the equation \(\phi(n)=\phi(n+1)\), Acta Arith. 196 (2020), 69–92. It still calls infinitude unknown, uses an exhaustive list of 10,755 solutions through \(10^{13}\), and proves
\[ \sum_{\phi(n)=\phi(n+1)}\frac1n<7.8358. \]
(b)
5. K. Ford, Solutions of \(\phi(n)=\phi(n+k)\) and \(\sigma(n)=\sigma(n+k)\), arXiv:2002.12155v5; IMRN 2022, 3561–3570. Ford proves infinitude for some even \(k\leq3570\) and for every multiple of \(442720643463713815200\). His Lemma 1 construction starts with \(j,j+k\) having the same prime support, and the paper explicitly notes that no such \(j\) exists when \(k\) is odd. It therefore does not reach \(k=1\). (b)
6. W. D. Banks, J. B. Friedlander, C. Pomerance, I. E. Shparlinski, Counting integers with a smooth totient, arXiv:1809.01214. Theorem 1.1 is the smooth-totient estimate invoked in the newest live-page comment. (b)
The searches also recovered earlier computational papers and OEIS data, but I did not use secondary tables as proof of any finite result below. (a)
2. Exact radical-kernel reduction
Write \(\operatorname{rad}(m)\) for the product of the distinct primes dividing \(m\), with \(\operatorname{rad}(1)=1\).
Theorem 1 (exact bijection)
Let
\[ R=\operatorname{rad}(n),\qquad S=\operatorname{rad}(n+1), \]and put
\[ g=(\phi(R),\phi(S)),\qquad u=\frac{\phi(R)}g,\qquad v=\frac{\phi(S)}g. \]Then \(\phi(n)=\phi(n+1)\) if and only if
\[ n=Rv,\qquad n+1=Su,\qquad Su-Rv=1, \tag{2.1} \]and every prime factor of \(v\) divides \(R\), while every prime factor of \(u\) divides \(S\). Equivalently, solutions are in bijection with coprime squarefree \(R,S\) satisfying those cross-support conditions and the last equation in (2.1). (a)
Proof
Write \(n=Ra\) and \(n+1=Sb\). Since \(R,S\) are the respective radicals,
\[ \phi(n)=a\phi(R),\qquad \phi(n+1)=b\phi(S). \]Equality gives \(au=bv\). As \((u,v)=1\), there is an integer \(c\geq1\) with
\[ a=cv,\qquad b=cu. \]But consecutiveness now gives
\[ 1=Sb-Ra=c(Su-Rv). \]Both factors on the right are integers, so \(c=1\) and (2.1) follows. The support conditions follow from the definitions of \(a,b\).
Conversely, suppose squarefree coprime \(R,S\) obey the stated conditions. The support conditions make
\[ \operatorname{rad}(Rv)=R,\quad \operatorname{rad}(Su)=S,\quad \phi(Rv)=v\phi(R)=guv=u\phi(S)=\phi(Su). \]The Bézout equation says \(Su=Rv+1\), completing the converse. \(\square\)
This reduction is exact, not heuristic. It shows that the exponents in a solution are forced by the two radicals; there is no remaining free scaling parameter. (a)
For example, \(n=104\) has
\[ (R,S,g,u,v)=(26,105,12,1,4), \]so \(104=26\cdot4\), \(105=105\cdot1\), and \(105-104=1\). (a)
3. A sharp elementary classification at odd complexity three
Let \(O\) be the odd member and \(E\) the even member of \(\{n,n+1\}\). Since \(2\mid E\),
\[ \frac{\phi(E)}E\leq\frac12. \]If \(E=O-1\), equality of the two totients gives
\[ \frac{\phi(O)}O<\frac12. \]If \(E=O+1\), it gives
\[ \frac{\phi(O)}O\leq\frac12\left(1+\frac1O\right). \]Thus, with \(T=\operatorname{rad}(O)\),
\[ 2\phi(T)\leq T+1. \tag{3.1} \]Indeed \(\phi(O)/O=\phi(T)/T\) and \(O\geq T\). (a)
Theorem 2 (all possible odd radicals for \(\omega(O)\leq3\))
If \(\phi(n)=\phi(n+1)\) and the odd member \(O\) has at most three distinct prime factors, then either
\[ (n,O)=(1,1),(3,3),(15,15), \]or \(\omega(O)=3\) and
\[ \operatorname{rad}(O)\in\{105,165,195,255\} =\{3\cdot5\cdot7,\;3\cdot5\cdot11,\;3\cdot5\cdot13,\;3\cdot5\cdot17\}. \tag{3.2} \](a)
Proof
For one odd prime \(p\), (3.1) says \(2(p-1)\leq p+1\), hence \(p=3\). Applying the sharper inequality with \(O\) gives \(O\leq3\), hence \(O=3\). For two odd primes,
\[ \frac{\phi(T)}T\geq\frac23\frac45=\frac8{15}. \]Together with (3.1), this forces \(T\leq15\), hence \(T=15\), and the inequality with \(O\) forces \(O=15\). The radical \(1\) gives \(O=1\). Direct substitution gives \(n=1,3,15\).
Now take \(T=pqr\) with odd primes \(p which contradicts (3.1). Therefore \(p=3\). Expanding (3.1) gives or If \(q\geq7\), the left side is at least \(3\cdot7=21\). Hence \(q=5\), and then \(r\leq17\). The four primes \(r=7,11,13,17\) give exactly (3.2). \(\square\) The radical list (3.2) is unconditional and finite. For each listed radical, every possible odd member is which makes exhaustive bounded checking straightforward. (a) The standalone checker is erdos1003_wave7z_reverify.py. It uses only the Python standard library. For every \(O\leq2^{64}-1\) with one of the four radicals in (3.2), it generates the exponent triples without omission, computes factors \(O-1\) and \(O+1\), and tests their totients. Factorisation is Pollard–Brent rho; terminal primality tests use the seven deterministic Miller–Rabin witnesses proven sufficient below \(2^{64}\). (b) for deterministic primality, (d) for the exhaustive output. The candidate counts are: | \(\operatorname{rad}(O)\) | candidates \(O\leq2^{64}-1\) | |---:|---:| | 105 | 3,595 | | 165 | 2,867 | | 195 | 2,663 | | 255 | 2,389 | | total | 11,514 | (d) Exactly twelve candidates work. Combining them with the elementary \(\omega(O)\leq2\) cases gives the following complete result in the stated regime: > For \(O\leq2^{64}-1\), all solutions whose odd member has at most three distinct prime factors are > \[
> \boxed{1,3,15,104,164,194,255,495,584,975,2204,2625,2834,13365,73124.}
> \] (d) (complete only for the displayed bound; Theorem 2 makes the candidate space rigorous). Here is the full arithmetic table: | \(n\) | odd \(O\) | factorisation of \(O\) | even \(E\) | factorisation of \(E\) | common \(\phi\) | |---:|---:|:---|---:|:---|---:| | 1 | 1 | \(1\) | 2 | \(2\) | 1 | | 3 | 3 | \(3\) | 4 | \(2^2\) | 2 | | 15 | 15 | \(3\cdot5\) | 16 | \(2^4\) | 8 | | 104 | 105 | \(3\cdot5\cdot7\) | 104 | \(2^3\cdot13\) | 48 | | 164 | 165 | \(3\cdot5\cdot11\) | 164 | \(2^2\cdot41\) | 80 | | 194 | 195 | \(3\cdot5\cdot13\) | 194 | \(2\cdot97\) | 96 | | 255 | 255 | \(3\cdot5\cdot17\) | 256 | \(2^8\) | 128 | | 495 | 495 | \(3^2\cdot5\cdot11\) | 496 | \(2^4\cdot31\) | 240 | | 584 | 585 | \(3^2\cdot5\cdot13\) | 584 | \(2^3\cdot73\) | 288 | | 975 | 975 | \(3\cdot5^2\cdot13\) | 976 | \(2^4\cdot61\) | 480 | | 2204 | 2205 | \(3^2\cdot5\cdot7^2\) | 2204 | \(2^2\cdot19\cdot29\) | 1008 | | 2625 | 2625 | \(3\cdot5^3\cdot7\) | 2626 | \(2\cdot13\cdot101\) | 1200 | | 2834 | 2835 | \(3^4\cdot5\cdot7\) | 2834 | \(2\cdot13\cdot109\) | 1296 | | 13365 | 13365 | \(3^5\cdot5\cdot11\) | 13366 | \(2\cdot41\cdot163\) | 6480 | | 73124 | 73125 | \(3^2\cdot5^4\cdot13\) | 73124 | \(2^2\cdot101\cdot181\) | 36000 | (d) Every row is also checked against the independent radical-kernel certificate (2.1). The full run printed: Peak resident memory was 63,272 KiB; measured wall time was 12.35 seconds on this VM. (d) As an independent implementation check, I separately enumerated the same 11,514 candidates using SymPy 1.14.0’s Reproduction: No downloaded table or precomputed factorisation is read by the checker. The solutions for which the upper member is a power of two, \(n+1=2^k\), are exactly There is no solution with the lower member \(n\) a positive power of two. (b) (the structural proof is elementary; the finite Fermat primality facts are directly checkable). If \(n=2^k-1\), then equality requires An odd integer with power-of-two totient is a squarefree product of Fermat primes Indeed, a repeated odd prime would divide the totient, and an odd prime \(p\) with \(p-1\) a power of two must be a Fermat prime. For a finite index set \(A\), All displayed binary exponents are distinct. Equality with therefore forces \(A=\{0,1,\ldots,r-1\}\) and \(k=2^r\). Now are prime, while is composite. Hence \(0\leq r\leq5\), which gives (5.1); the standard identity4. Exhaustive unsigned-64-bit computation in that regime
odd-member limit: 18446744073709551615
candidate counts: 105:3595 165:2867 195:2663 255:2389
total candidates: 11514
three-prime solutions (12):
n=104 odd=105 rad(odd)=105 phi(n)=phi(n+1)=48
n=164 odd=165 rad(odd)=165 phi(n)=phi(n+1)=80
n=194 odd=195 rad(odd)=195 phi(n)=phi(n+1)=96
n=255 odd=255 rad(odd)=255 phi(n)=phi(n+1)=128
n=495 odd=495 rad(odd)=165 phi(n)=phi(n+1)=240
n=584 odd=585 rad(odd)=195 phi(n)=phi(n+1)=288
n=975 odd=975 rad(odd)=195 phi(n)=phi(n+1)=480
n=2204 odd=2205 rad(odd)=105 phi(n)=phi(n+1)=1008
n=2625 odd=2625 rad(odd)=105 phi(n)=phi(n+1)=1200
n=2834 odd=2835 rad(odd)=105 phi(n)=phi(n+1)=1296
n=13365 odd=13365 rad(odd)=165 phi(n)=phi(n+1)=6480
n=73124 odd=73125 rad(odd)=195 phi(n)=phi(n+1)=36000
omega(odd)<=3 solutions (15): (1, 3, 15, 104, 164, 194, 255, 495,
584, 975, 2204, 2625, 2834, 13365, 73124)
independent phi sieve through 1000000: 68 total solutions
omega(odd)<=3 subset: (1, 3, 15, 104, 164, 194, 255, 495, 584,
975, 2204, 2625, 2834, 13365, 73124)
PASS (12.301 seconds)
factorint; it returned the same twelve three-prime solutions. The checker’s unrelated full totient sieve through \(10^6\) found 68 solutions in total and exactly the same 15-element low-complexity subset. (d)cd /home/exedev/MathDyad
python runs/erdos1003_wave7z_reverify.py
5. Complete power-of-two-neighbour classification
Theorem 3
Proof
If instead \(n=2^k\), then the same power-of-two-totient characterization makes \(n+1\) a product of distinct Fermat primes. Its binary expansion has \(2^{|A|}\) nonzero terms, whereas \(2^k+1\) has two. Thus \(|A|=1\), so \(n+1=F_j\) and \(k=2^j\). But then \(\phi(n+1)=2^k\neq2^{k-1}=\phi(n)\). \(\square\)
The checker recomputes all six equalities in (5.1), verifies \(F_0,\ldots,F_4\) with deterministic primality tests, and checks the displayed factorisation of \(F_5\). (b)
6. Why fixed-factor ansätze cannot prove infinitude
Theorem 4
For every fixed \(K\), there are only finitely many solutions \(n\) with
\[ \max(\omega(n),\omega(n+1))\leq K. \tag{6.1} \]Consequently, along any hypothetical infinite sequence of solutions, the number of distinct prime factors of at least one member tends beyond every fixed bound. (a)
Proof
First, the map from finite prime sets
\[ A\longmapsto\prod_{p\in A}\left(1-\frac1p\right) \tag{6.2} \]is injective. If two different sets gave the same value, cancel their intersection and let \(r\) be the largest remaining prime, say on the left. After cross multiplication the right side is divisible by \(r\), while every factor on the left is a positive integer smaller than \(r\), a contradiction.
Assume infinitely many solutions satisfy (6.1), and take a subsequence on which the same member is even. Order each member’s prime factors and pad the lists with \(\infty\). A diagonal subsequence makes each of the finitely many coordinates either eventually constant or tend to infinity. In (6.2), primes tending to infinity contribute factors tending to \(1\), so each side has a limiting product over its eventually constant primes.
For a solution with common totient \(t\),
\[ \left|\frac{\phi(n)}n-\frac{\phi(n+1)}{n+1}\right| =\frac{t}{n(n+1)}\longrightarrow0. \]The two limiting products are therefore equal. Their finite prime sets are disjoint because \((n,n+1)=1\), while one contains \(2\); this contradicts injectivity. \(\square\)
This proves the substance of the live-page comment about increasing factor complexity, but it is qualitative and ineffective: it gives no usable bound for a specified \(K\). (a)
7. Exact remaining wall
Theorems 1–4 do not prove infinitude. The exact remaining construction problem is:
> Produce infinitely many coprime squarefree pairs \(R,S\) such that, for
> \[ > g=(\phi(R),\phi(S)),\quad u=\phi(R)/g,\quad v=\phi(S)/g, > \]
> every prime of \(v\) lies in \(R\), every prime of \(u\) lies in \(S\), and
> \[ > Su-Rv=1. > \tag{7.1} > \]
By Theorem 1, this is not merely sufficient; it is equivalent to the original problem. (a)
The missing lemma is an infinitude theorem for these cross-supported radical pairs. Standard fixed-pattern prime-tuples machinery does not supply it: Ford’s same-prime-support construction requires an even shift and explicitly has no seed \(j\) for odd \(k\). (b) Equation (7.1) also forces the exponent vector rather than leaving a scalable parameter, while Theorem 4 says no bounded-prime-factor template can work indefinitely. (a)
More finite sieving cannot bridge this uniformity gap. A naive unsegmented totient array through \(2^{64}\) would require about \(2^{67}\) bytes (roughly 148 exabytes) for 64-bit entries and on the order of \(10^{19}\) elementary updates; even an idealized \(10^8\) updates/second is thousands of core-years. (d) Segmentation removes the memory obstruction but not the work or, more importantly, the missing infinitude step. (a)
The verified advance here is therefore a clean exact reduction, a sharp elementary classification of the first nontrivial odd-factor regime, a complete \(2^{64}\)-scale computation in that regime, and a proof that any infinite construction must have unbounded factor complexity. It does not close Erdős problem 1003. (a)/(d)
PARTIAL: Exact radical-kernel bijection proved; all solutions with odd member <= 2^64-1 and omega(odd) <= 3 are exhaustively classified (15 total), but infinitude remains equivalent to constructing infinitely many cross-supported radical pairs satisfying Su-Rv=1.