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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003434 Number of iterations of phi(x) at n needed to reach 1.
(Formerly M0244)
28
0, 1, 2, 2, 3, 2, 3, 3, 3, 3, 4, 3, 4, 3, 4, 4, 5, 3, 4, 4, 4, 4, 5, 4, 5, 4, 4, 4, 5, 4, 5, 5, 5, 5, 5, 4, 5, 4, 5, 5, 6, 4, 5, 5, 5, 5, 6, 5, 5, 5, 6, 5, 6, 4, 6, 5, 5, 5, 6, 5, 6, 5, 5, 6, 6, 5, 6, 6, 6, 5, 6, 5, 6, 5, 6, 5, 6, 5, 6, 6, 5, 6, 7, 5, 7, 5, 6, 6, 7, 5, 6, 6, 6, 6, 6, 6, 7, 5, 6, 6, 7, 6, 7, 6, 6 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

Each number n>1 occurs for the first time at the position A007755(n+1) and for the last time at 2*3^(n-1). - Ivan Neretin, Mar 24 2015

REFERENCES

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

M. V. Subbarao, On a function connected with phi(n), J. Madras Univ. B. 27 (1957), pp. 327-333.

LINKS

T. D. Noe, Table of n, a(n) for n = 1..10000

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]

I. Niven, The iteration of certain arithmetic functions, Canad. J. Math. 2 (1950), pp. 406-408.

H. N. Shapiro, On the iterates of a certain class of arithmetic functions, Comm. Pure Appl. Math. 3 (1950), pp. 259-272.

S. Sivasankaranarayana Pillai, On a function connected with phi(n), Bull. Amer. Math. Soc., 35:6 (1929), pp. 837-841.

S. Sivasankaranarayana Pillai, On a function connected with phi(n), Bull. Amer. Math. Soc., 35.6 (1929), 837-841. (Annotated scanned copy)

FORMULA

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

By the definition of a(n) we have for n >= 2 the recursion a(n) = a(phi(n)) + 1. - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 20 2001

Pillai proved that log(n/2)/log(3) + 1 <= a(n) <= log(n)/log(2) + 1. - Charles R Greathouse IV, Mar 22, 2012

EXAMPLE

If n=164 the trajectory is {164,80,32,16,8,4,2,1}. Its length is 8, thus a(164)=7.

MAPLE

A003434 := proc(n)

    local a, e;

    e := n ;

    a :=0 ;

    while e > 1 do

        a := a+1 ;

        e := numtheory[phi](e) ;

    end do:

    a;

end proc:

seq(A003434(n), n=1..40) ; # R. J. Mathar, Jan 09 2017

MATHEMATICA

f[n_] := Length@ NestWhileList[ EulerPhi, n, # != 1 &] - 1; Array[f, 105] (* Robert G. Wilson v, Feb 07 2012 *)

PROG

(PARI) A003434(n)=for(k=0, n, n>1 || return(k); n=eulerphi(n)) /* Works because the loop limits are evaluated only once. Using while(...) takes 50% more time. */ \\ M. F. Hasler, Jul 01 2009

(Haskell)

a003434 n = fst $ until ((== 1) . snd)

                        (\(i, x) -> (i + 1, a000010 x)) (0, n)

-- Reinhard Zumkeller, Feb 08 2013, Jul 03 2011

CROSSREFS

Cf. A000010, A007755.

Sequence in context: A202472 A235613 A019569 * A097849 A100678 A026834

Adjacent sequences:  A003431 A003432 A003433 * A003435 A003436 A003437

KEYWORD

nonn,easy,nice,look

AUTHOR

N. J. A. Sloane

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 19 05:12 EST 2018. Contains 299330 sequences. (Running on oeis4.)