← All problems

Erdős Problem #408 — Iterates of Euler's totient function

46 years old · traced to

For an integer n≥2n\ge 2, let ϕ(n)\phi(n) be the number of integers aa with 1≤a≤n1\le a\le n and gcd⁡(a,n)=1\gcd(a,n)=1. Define the iterates for integers k≥1k\ge 1 by

ϕ1(n)=ϕ(n),ϕk(n)=ϕ(ϕk−1(n))(k≥2),\phi_1(n)=\phi(n),\qquad \phi_k(n)=\phi\bigl(\phi_{k-1}(n)\bigr)\quad(k\ge 2),

and let

f(n)=min⁡{k≥1:ϕk(n)=1}.f(n)=\min\{k\ge 1:\phi_k(n)=1\}.

With nn sampled uniformly from the integers up to NN, does f(n)/log⁡nf(n)/\log n have a limiting distribution as N→∞N\to\infty? Is there a constant to which this ratio is almost always equal, in the sense that for every ε>0\varepsilon>0 the integers satisfying the ratio's distance from that constant less than ε\varepsilon have natural density 11? What can be said about the largest prime factor of ϕk(n)\phi_k(n) when, say, k=log⁡log⁡nk=\log\log n? Erdős Problem #408

Background

Pillai initiated the study of this iteration function in 1929 and obtained bounds placing f(n)f(n) between constant multiples of log⁡n\log n for all sufficiently large nn. Shapiro later established an essentially multiplicative structure. One useful formulation, given in the subsequent work of Erdős, Granville, Pomerance, and Spiro, is that the number of even terms in n,ϕ(n),ϕ2(n),…n,\phi(n),\phi_2(n),\ldots is a completely additive function; it equals f(n)f(n) for even nn and f(n)−1f(n)-1 for odd nn. This additive viewpoint makes it possible to bring distribution results for primes in arithmetic progressions to bear on the typical size of the iteration count. Pillai (1929); Shapiro (1950) Erdős, Granville, Pomerance, and Spiro (1990)

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.