A032358 Number of iterations of phi(n) needed to reach 2.

0, 1, 1, 2, 1, 2, 2, 2, 2, 3, 2, 3, 2, 3, 3, 4, 2, 3, 3, 3, 3, 4, 3, 4, 3, 3, 3, 4, 3, 4, 4, 4, 4, 4, 3, 4, 3, 4, 4, 5, 3, 4, 4, 4, 4, 5, 4, 4, 4, 5, 4, 5, 3, 5, 4, 4, 4, 5, 4, 5, 4, 4, 5, 5, 4, 5, 5, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 5

Offset: 2

Author

Ursula Gagelmann (gagelmann(AT)altavista.net)

Keywords

• nice
• nonn
• easy

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.

Crossrefs

Cf. A000010, A003434.

Programs

Haskell

a032358 = length . takeWhile (/= 2) . (iterate a000010)
-- Reinhard Zumkeller, Oct 27 2011

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 *)

PARI

a(n)=my(t);while(n>2,n=eulerphi(n);t++);t \\ Charles R Greathouse IV, Oct 28 2011

Formula

a(n) = a(phi(n))+1, a(1) = -1. - Vladeta Jovovic, Apr 29 2003

a(n) = A003434(n) - 1 = A049108(n) - 2.

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)

Extensions

a(2) = 0 added and offset adjusted, suggested by David W. Wilson