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

 

Logo


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: A176835 A237110 A078704 * 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 25 08:12 EST 2018. Contains 299646 sequences. (Running on oeis4.)