login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A032358 Number of iterations of phi(n) needed to reach 2. 5
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 (list; graph; refs; listen; history; text; internal format)
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

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)

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

Cf. A000010, A003434.

Sequence in context: A237110 A078704 A306468 * A011960 A187035 A008615

Adjacent sequences:  A032355 A032356 A032357 * A032359 A032360 A032361

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 11 12:33 EST 2019. Contains 329916 sequences. (Running on oeis4.)