Are there infinitely many $n$ with $\phi(n)=\phi(n+1)$? (Erdős #1003)
Statement
Let $\phi$ denote Euler's totient function (the number of integers in $\{1,\ldots,n\}$ coprime to $n$). Are there infinitely many integers $n$ with $\phi(n)=\phi(n+1)$? More generally, Erdős conjectured that for every fixed $k\geq 1$ the system $$\phi(n)=\phi(n+1)=\cdots=\phi(n+k)$$ has infinitely many solutions $n$.
Acceptance. FULLY RESOLVES (OPEN, proof-shaped): a complete proof — machine-checkable (Lean/Coq) preferred, otherwise a full written proof — that $\phi(n)=\phi(n+1)$ holds for infinitely many $n$ (or the stronger $k$-term claim). A finite list of solutions can never suffice. ADVANCES: an improved upper bound on the counting function of such $n$ that strictly beats the EPS87 bound $x/\exp((\log x)^{1/3})$ stated above, with proof; OR any nontrivial lower bound / rigorous construction of an infinite family under a clearly stated hypothesis; OR extend the verified enumeration underlying OEIS A001274 to a new record range with reproducible code and report the empirical growth. Deliver the proof or formal artifact, the bound with its derivation, or the enumeration code together with the attained range.
Background
Posed by Erdős [Er85e]; listed as open on erdosproblems.com/1003 (fetched 2026-07-21, status 'open'). The strongest known result is a density bound of Erdős, Pomerance, and Sárközy [EPS87]: the number of $n\leq x$ with $\phi(n)=\phi(n+1)$ is at most $x/\exp((\log x)^{1/3})$ — this bounds how common such $n$ are but does not prove there are infinitely many. Solutions are catalogued in OEIS A001274 (the smallest are $n=1,3,15,\ldots$, e.g. $\phi(15)=\phi(16)=8$). The exact analogue for the divisor function, $d(n)=d(n+1)$ infinitely often, is Erdős #946 (erdosproblems.com/946), and #415 (erdosproblems.com/415) concerns inequality patterns among consecutive totient values. A formalised statement exists in the google-deepmind/formal-conjectures Lean repository. No cash prize. Attacker's tool: sieve $\phi$ over long ranges to extend A001274 and measure the empirical count against the EPS87 bound; the infinitude claim itself is proof-shaped, so a full (ideally Lean-checkable) proof is what closes it.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1003 (T. F. Bloom) | website |
| REF-02 | OEIS A001274 — numbers m with phi(m) = phi(m+1) | website |
| REF-03 | Lean formalisation (google-deepmind/formal-conjectures) of Erdős #1003 | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.