← All problems

Erdős Problem #411 — Eventual doubling under iterated totient addition

46 years old · traced to

Let ϕ\phi be Euler’s totient function, define g(n)=n+ϕ(n)g(n)=n+\phi(n) for positive integers nn, and recursively define g1(n)=g(n)g_1(n)=g(n) and gk+1(n)=g(gk(n))g_{k+1}(n)=g(g_k(n)) for k≥1k\geq 1. Determine all positive integers nn and rr for which there is an integer K≥1K\geq 1 such that

gk+r(n)=2gk(n)g_{k+r}(n)=2g_k(n)

for every integer k≥Kk\geq K. Erdős Problems #411

Background

Erdős and Graham posed this iteration problem in their 1980 collection Old and New Problems and Results in Combinatorial Number Theory. It brings together the multiplicative arithmetic of the totient function and repeated addition through g(n)=n+ϕ(n)g(n)=n+\phi(n). The problem has also prompted the study of eventual identities with multipliers other than 22, which give context for the range of possible iteration patterns. Erdős and Graham (1980), p. 81; Erdős Problems #411 Steinerberger, On an iterated arithmetic function problem of Erdős and Graham (2025 preprint)

References

Progress summary

Never refreshed

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.