OFFSET
2,4
COMMENTS
This sequence is additive (but not completely additive). [Charles R Greathouse IV, Oct 28 2011]
Shapiro asks for a proof that for every n > 1 there is a prime p such that a(p) = n. [Charles R Greathouse IV, Oct 28 2011]
This is A003434(n)-1 for n>1. - N. J. A. Sloane, Sep 02 2017
LINKS
Reinhard Zumkeller, Table of n, a(n) for n = 2..10000
P. A. Catlin, Concerning the iterated phi-function, Amer Math. Monthly 77 (1970), pp. 60-61.
Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.
Paul Erdos, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]
T. D. Noe, Primes in classes of the iterated totient function, JIS 11 (2008) 08.1.2, sequence C(x).
Harold Shapiro, An arithmetic function arising from the phi function, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.
FORMULA
a(n) = a(phi(n))+1, a(1) = -1. - Vladeta Jovovic, Apr 29 2003
From Charles R Greathouse IV, Oct 28 2011: (Start)
Shapiro proves that log_3(n/2) <= a(n) < log_2(n) and also
a(mn) = a(m) + a(n) if either m or n is odd and a(mn) = a(m) + a(n) + 1 if m and n are even.
(End)
MAPLE
A032358 := proc(n)
local a, phin ;
if n <=2 then
0;
else
phin := n ;
a := 0 ;
for a from 1 do
phin := numtheory[phi](phin) ;
if phin = 2 then
return a;
end if;
end do:
end if;
end proc:
seq(A032358(n), n=1..30) ; # R. J. Mathar, Aug 28 2015
MATHEMATICA
Table[Length[NestWhileList[EulerPhi[#]&, n, #>2&]]-1, {n, 3, 80}] (* Harvey P. Dale, May 01 2011 *)
PROG
(Haskell)
a032358 = length . takeWhile (/= 2) . (iterate a000010)
-- Reinhard Zumkeller, Oct 27 2011
(PARI) a(n)=my(t); while(n>2, n=eulerphi(n); t++); t \\ Charles R Greathouse IV, Oct 28 2011
CROSSREFS
KEYWORD
nice,nonn,easy
AUTHOR
Ursula Gagelmann (gagelmann(AT)altavista.net)
EXTENSIONS
a(2) = 0 added and offset adjusted, suggested by David W. Wilson
STATUS
approved