Erdős Problem #409 — Iterations of the totient-plus-one map
Let be Euler’s totient function on the positive integers. For each , define the iterates by
and let , with when is already prime. This minimum exists: if is composite, then , , and hence ; primes are fixed by the map. The quantitative question is to find useful upper bounds for as a function of . Erdős Problems #409
For a fixed prime , define its set of inputs that eventually reach it by
Is infinite? What is its natural density: does the limit
exist, and, if so, what is its value? Erdős Problems #409
Background
The problem is attributed to Finucane and cited as [ErGr80, p. 81]. Its wording leaves the quantitative goal open-ended; the problem discussion interprets it as seeking good upper bounds for the number of iterations. The topic is also discussed as problem B41 in Richard K. Guy’s 2004 collection Unsolved Problems in Number Theory. Erdős Problems #409 Guy, Unsolved Problems in Number Theory (2004)
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.