← All problems

Erdős Problem #409 — Iterations of the totient-plus-one map

45 years old · documented by

Let ϕ\phi be Euler’s totient function on the positive integers. For each n≥1n\ge 1, define the iterates by

x0=n,xj+1=ϕ(xj)+1(j≥0),x_0=n,\qquad x_{j+1}=\phi(x_j)+1\quad(j\ge 0),

and let τ(n)=min⁡{j≥0:xj is prime}\tau(n)=\min\{j\ge 0:x_j\text{ is prime}\}, with τ(n)=0\tau(n)=0 when nn is already prime. This minimum exists: if mm is composite, then m≥4m\ge4, ϕ(m)≤m/2\phi(m)\le m/2, and hence ϕ(m)+1<m\phi(m)+1<m; primes are fixed by the map. The quantitative question is to find useful upper bounds for τ(n)\tau(n) as a function of nn. Erdős Problems #409

For a fixed prime pp, define its set of inputs that eventually reach it by

Bp={n≥1:xj=p for some j≥0}.B_p=\{n\ge1: x_j=p\text{ for some }j\ge0\}.

Is BpB_p infinite? What is its natural density: does the limit

lim⁡X→∞1X#{n≤X:n∈Bp}\lim_{X\to\infty}\frac{1}{X}\#\{n\le X:n\in B_p\}

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

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.