Iteration of Euler's phi function

[huba]

Iterating Euler's totient function \varphi(n), it eventually arrives at 1. Let h(n) denote the least number of iterations to arrive at 1. For instance, h(18)=3, ie \varphi^{3}(18)=1. There is a conjecture (or is there a proof?) that the largest n for which h(n)=k is 2\times 3^{k-1}. The only reference I found on the internet was a short note in a comment to Sloane's A007755 (the smallest n for which h(n)=k), saying that the maximum value is of that form.
Although I haven't found a proof, I think that I have at least a simple result, using the 2\times 3^{k-1} form. Richard K. Guy (2004), in "Unsolved Problems in Number Theory", p.149 (haven't read it, found it in Google Book Search) describes perfect totient numbers as those n for which n = \varphi(n) + \varphi^{2}(n) + \varphi^{3}(n) + ... + 2 + 1, and says that all powers of 3 are perfect totient numbers. I haven't seen the proof for all powers of 3 being perfect totient numbers, but I would reason this way:

It is easy to prove by induction that
\sum^{k-1}_{j=0}2\times 3^{j}+1=3^{k}.

As for all x\geq j, \varphi^{j}(2\times 3^{x}) = 2\times 3^{x-j}, and \varphi^{x+1}(2\times 3^{x}) = \varphi(2) = 1,

\sum^{k+1}_{j=1}\varphi^{j}(2\times 3^{k})=3^{k}

 

[huba]

The set of the smallest numbers n for which \varphi^{k}(n) = 1 is possibly more interesting. Sloane's http://www.research.att.com/~njas/sequences/A007755" lists the first 34 such numbers, or 33 if starting with 2 (I left out 1) :
2, 3, 5, 11, 17, 41, 83, 137, 257, 641, ...
I will refer to the set of those integers as M.

It was conjectured (Shapiro, 1943) that all such numbers are prime, but then composite numbers were found.
According to Guy (2004), Catlin (1970) showed that if m is an odd element of M, then the factors of m are in M.
I propose the conjecture that all primes > 2 in M are either http://mathworld.wolfram.com/FermatPrime.html" or are of the form 2^{t}\times m + 1 with m \in M. In other words, if prime p \in M then either \varphi(p) = 2^{2^{s}} or \varphi(p) = 2^{t}\times m with m \in M, with t and s any positive integers.
Further, a finite number of phi-iterations on m will lead to a number with a factor which is a Fermat prime. For example, take m = 35209, a composite number with the prime factors 137 and 257 (257 is already a Fermat prime). \varphi(35209) = \varphi(137)\times \varphi(257) = 136 \times 256 = 2^{11}\times 17 = 34816 which again has a Fermat prime, 17, as a prime factor.
I would also conjecture that if m is composite, then at least one of its prime factors is a Fermat prime. For example, the largest term in A007755 is 4295098369, which is 65537^{2}.

I would appreciate any comments.

Just another example for the iteration leading to a Fermat prime:

\varphi(140417) = 140416 = 2^{7}\times1097
\varphi(140416) = 2^{6}\times 1096 = 2^{9}\times 137 = 70144
\varphi(70144) = 2^{8}\times 136 = 2^{11}\times 17 = 34816, and so

17, a Fermat prime, divides \varphi^{3}(140417).