Erdős Problem #408 — Iterates of Euler's totient function
For an integer , let be the number of integers with and . Define the iterates for integers by
and let
With sampled uniformly from the integers up to , does have a limiting distribution as ? Is there a constant to which this ratio is almost always equal, in the sense that for every the integers satisfying the ratio's distance from that constant less than have natural density ? What can be said about the largest prime factor of when, say, ? Erdős Problem #408
Background
Pillai initiated the study of this iteration function in 1929 and obtained bounds placing between constant multiples of for all sufficiently large . 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 is a completely additive function; it equals for even and for odd . 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
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.