Skip to content

Erdős Problem #411

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, iterated functions.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

Let \(\phi(n)\) be Euler's totient function, the number of integers from \(1\) through \(n\) that share no factor with \(n\) other than \(1\). Define \(g(n)=n+\phi(n)\) and repeatedly apply it: \(g_1(n)=g(n)\) and \(g_k(n)=g(g_{k-1}(n))\). Erdős and Graham ask for which starting values \(n\) and positive shifts \(r\) the orbit eventually obeys

\[ g_{k+r}(n)=2g_k(n) \]

for every sufficiently large \(k\). “Eventually” matters: early terms may not fit the pattern, while later terms may repeat a fixed multiplicative rhythm. The question asks for all such \(n\) and \(r\), not merely for examples.

The maintained problem page gives the original reference as Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), p. 81. The exact wording and notation are also reproduced in Steinerberger's primary 2025 paper, §1. This article follows the live statement rather than silently replacing “for which \(n\) and \(r\)” by the narrower question of classifying points already on a cycle.

A small example

The classical example \(n=10\) can be checked with exact integer arithmetic. Since \(\phi(10)=4\), \(g(10)=14\); then \(\phi(14)=6\), \(g(14)=20\); next \(\phi(20)=8\), \(g(20)=28\); and \(\phi(28)=12\), \(g(28)=40\). Thus the beginning of the orbit is

\[ 10\longmapsto14\longmapsto20\longmapsto28\longmapsto40. \]

The three displayed comparisons are \(20=2\cdot10\), \(28=2\cdot14\), and \(40=2\cdot20\). A trial-division totient calculation reproduced this orbit and returned the exact checks (20,20), (28,28), and (40,40) for the two-step value and its doubled predecessor. This verifies a finite instance of the claimed pattern; it does not classify all starts, prove that the equality persists for every later index, or say anything about shifts \(r\ne2\).

The persistence mechanism is elementary once an even term satisfies the two-step equation. For even \(m\), \(\phi(2m)=2\phi(m)\), so \(g(2m)=2g(m)\). Steinerberger uses this to show that the \(r=2\) question reduces to the arithmetic equation

\[ \phi(m)+\phi(m+\phi(m))=m. \]

This reduction is a useful normalization, not a solution of the original problem for all values of \(r\).

What is known

Steinerberger's arXiv:2504.08023v1 (submitted 10 April 2025) proves the \(r=2\) reduction and gives six explicit infinite families for the auxiliary equation: \(m=2^\ell u\) with \(u\) in \(\{1,3,5,7,35,47\}\), subject to the lower exponent needed for the cycle. The paper's Theorem on p. 1, the equivalence argument in §§2.1–2.2, and the 2-adic analysis in §2 are the relevant primary locations. It further reduces any additional branch to a prime \(p=8m+7\ge10^{10}\) together with \(\phi(6m+5)=4m+4\), equivalently to the related equation \(\phi(t)=\frac23(t+1)\) with an additional primality condition. The paper presents completeness of the six families as conditional or possible, not as a finished theorem.

Hercher's arXiv:2504.19915v1 (submitted 28 April 2025) studies that related totient equation. Its abstract and Theorem 1 state that every solution is square-free; Corollary 2 gives a prime-factor nondivisibility condition; later results bound any additional solution below neither \(10^{14}\) nor six prime factors. These are results about the auxiliary equation, not a complete answer to Erdős Problem 411. The live page's discussion also contains a typographical report of \(1195\) where the factored value is \(1295\); the paper's displayed factorization and later discussion use \(1295\). That discrepancy is retained as source hygiene rather than repaired into a new theorem.

The live page records examples with other multipliers, including \(g_{k+4}(738)=3g_k(738)\) and the reported \(3114\) example with multiplier \(729\). They illustrate richer dynamics but do not answer the requested multiplier \(2\) classification.

GCL's current state

The pinned catalogue packet is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, Git blob 4e60263a80af6207aca494d2e1388e44fa372889 (catalogue-file SHA-256 be65b0db56fe13becec3178f2937685ee7e6a2f5df9325712474722c279c4182). Entry 411 records open, unformalized, and statement-formalized no, last updated 2025-08-31, with the note “partial r=2 result.” The protected GCL registry places it in STATEMENT_CAPTURE_REQUIRED.

The maintained live entry, accessed 2026-10-13, is still open, was last edited 28 October 2025, and says “Formalised statement? No.” It now displays six user comments and one proof claim. The claim, submitted 8 September 2026, asserts only the first \(r=2\) branch and explicitly leaves the second branch open; the page warns that proof claims are not checked. It is therefore an unverified external report, not accepted coverage, a GCL result, or a certification.

The exact FormalConjectures snapshot named by the packet is upstream commit 85f863718beeec7b58a3a1926ee92e3472bc2020; its tree contains FormalConjectures/ErdosProblems/410.lean but no 411.lean. The admitted MATHFORGE provider snapshot is metadata-only at commit 638190868060e60e109197af602fda4fb80fd02b, with provider artifact blobs 5e74d0ceec81d313e9c858ec5bd4014fa543314f and bc0a92eeefc69e92a2e08c99f903b93f966257d8. Thus there is no pinned Lean theorem for this problem to replay, with or without sorry.

What remains

The main mathematical gap is global: classify all transient starts and all shifts \(r\), while deciding whether the exceptional prime/totient branch contains anything beyond the displayed families. Even for \(r=2\), a cycle classification is not automatically a basin classification, because a starting value may enter a known cycle later. The live discussion's proposed square-free recurrence is explicitly challenged in a later comment: a forward extension rule does not prove that every solution can be reduced by deleting its largest prime factor.

A genuinely bounded next task is to capture a source-normalized theorem interface. Its input should be a Lean-free statement record defining \(\phi\), \(g_0(n)=n\), and \(g_{j+1}(n)=g(g_j(n))\), with the live quantifiers and the auxiliary \(r=2\) equation recorded separately. Its target should be the exact lemma: if \(m\ge3\) satisfies \(\phi(m)+\phi(m+\phi(m))=m\), then \(g_2(m)=2m\) and \(g_{j+2}(m)=2g_j(m)\) for every \(j\ge0\). Acceptance is a checked proof or a line-by-line mathematical proof of that lemma plus exact checks for the six listed base families; falsification is a counterexample satisfying the hypothesis but not the conclusion, or a detected indexing mismatch. Stop after that interface and its finite checks; do not attempt a full classification or a large unbounded search.

Sources and claim boundaries

Primary sources are Erdős–Graham (1980), p. 81, Steinerberger, arXiv:2504.08023v1, especially Theorem/§§1–2, and Hercher, arXiv:2504.19915v1, especially the abstract and Theorem 1. The source packet and assignment are original GitHub issue #1681; the original SOURCE RESULT/1 citation is authenticated original RESULT/1.

The finite orbit above is an independently reproduced arithmetic check. The six-family and exceptional-branch statements are attributed to Steinerberger and are not upgraded here. Hercher's auxiliary results and the maintained-page comments are external source reports, with the latter explicitly unverified. No Lean replay, mathematical certification, acceptance decision, publication decision, or claim that V2 coverage has changed is supplied by this article.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1681 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_REQUIRED.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction