Skip to content

Erdős Problem #409

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

Erdős Problem 409 studies what happens when we repeatedly apply the function

\[ T(n)=\varphi(n)+1, \]

where \(\varphi(n)\) is Euler's totient function, the number of integers from 1 through \(n\) that are coprime to \(n\). Starting from a positive integer \(n\), keep applying \(T\). If a prime is reached after \(k\) applications, write \(c(n)=k\). Thus a prime has count zero, while a composite starting value may have a positive count. The central question is how large \(c(n)\) can be and what a useful general upper bound should look like.

The source also asks two distribution questions. For a fixed prime \(p\), can infinitely many starting integers eventually land on \(p\)? If so, what is the density of those starting integers? A related variant replaces \(T\) by

\[ S(n)=\sigma(n)-1, \]

where \(\sigma(n)\) is the sum of the positive divisors of \(n\): do these iterations always reach a prime, and how quickly? These are related dynamical questions, but they are not one theorem with one conclusion.

A small example

Take \(n=45\). Exact factorisation gives

\[ \varphi(45)=45\left(1-\frac13\right)\left(1-\frac15\right)=24, \]

so the orbit is

\[ 45\longmapsto25\longmapsto21\longmapsto13. \]

The intermediate values are composite and 13 is prime, so direct arithmetic verifies \(c(45)=3\). This illustrates the definition, including the fact that the first prime is what matters. For comparison, \(\sigma(15)=1+3+5+15=24\), so the sigma-minus-one orbit reaches the prime 23 in one step:

\[ 15\longmapsto23. \]

A bounded exact enumeration using divisor sums, totients, and trial-division primality checks found a largest totient count of 7 among \(1\le n\le1000\), attained at \(n=949\). This is a finite check, not an upper bound for all integers, and it says nothing by itself about densities or asymptotic growth.

What is known

The maintained problem page identifies the question as a problem of Finucane and cites Erdős and Graham's Old and New Problems and Results in Combinatorial Number Theory (1980), printed page 81. That primary document states the questions but does not provide a solution to them. The maintained page also records the later interpretation that, if \(F(n)\) denotes the number of totient-plus-one iterations, the elementary facts \(F(n)=o(n)\) and \(F(n)=1\) for infinitely many \(n\) are not the intended endpoint; the likely goal is a good upper bound. It points to Problem B41 in Guy's 2004 collection for related discussion. These are source reports, not a new theorem proved by this article.

There is one elementary termination fact for the totient map. At \(n=1\) the next value is 2. If \(n>1\) is composite, then \(\varphi(n)+1<n\); therefore a non-prime orbit descends until it reaches a prime. This establishes existence of \(c(n)\) for positive \(n\), but it does not determine its maximum order, the size of a fixed-prime basin, or its density. The sigma map is different: it is not governed by the same decreasing argument, so its termination question requires separate evidence.

GCL's current state

The source-audit assignment is original issue #1679, assignment ERDOS-CATALOGUE-0409-S01. Its protected packet pins the catalogue snapshot teorth/erdosproblems at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, with entry blob 4e60263a80af6207aca494d2e1388e44fa372889. That snapshot says the informal status is open, dated 2025-08-31, and the formal status is unformalized, while statement-formalized metadata is yes.

The live Problem 409 page was edited on 20 December 2025. It still presents the problem as open, but makes the ambiguity and the upper-bound interpretation more explicit; this is documented drift in exposition, not evidence of a changed solution status. The pinned FormalConjectures source is 409.lean at commit 85f863718beeec7b58a3a1926ee92e3472bc2020, blob 4f163009ffc1c43b9cfe71f76ead00a403e409be. It contains the totient termination theorem with a proof, but the research answers use answer(sorry). Presence of a formal statement or a completed variant is not mathematical certification of the open claims.

The formal quantifiers matter. The minimum-count theorem is stated for every positive \(n\); the fixed-prime question is encoded as an existential choice of one prime whose basin is infinite; and the density statement assumes that the relevant density already exists before asking for its value. The sigma family uses the hypothesis \(n>1\). These choices are useful interfaces for several subquestions, but they should not be read as a single formalization of every possible meaning of “how soon” or “density”.

What remains

The meaningful unresolved work is to choose one precisely normalized target: for example, a sharp bound for \(c(n)\), the infinitude of the preimage of a fixed prime, or the density of that preimage. A bounded successor should first reproduce the primary wording, define whether iteration count starts at zero, and separate the totient and sigma maps. It can then compute a finite table or prove a local lemma with an explicit range and stopping rule. Such evidence may expose a useful pattern, but it cannot establish an asymptotic, an infinite-family statement, or sigma termination without a proof covering all inputs.

Sources and claim boundaries

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1679 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: PROTECTED_READY_BACKLOG.
  • Formal-statement coverage: A provider statement was included in the pinned 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