A003434 Number of iterations of phi(x) at n needed to reach 1.

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

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice
• look

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

Examples

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

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
• Hartosh Singh Bal, Gaurav Bhatnagar, Prime number conjectures from the Shapiro class structure, arXiv:1903.09619 [math.NT], 2019.
• C. Defant, On Arithmetic Functions Related to Iterates of the Schemmel Totient Functions, J. Int. Seq. 18 (2015) # 15.2.1.
• 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 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. [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)

Crossrefs

Cf. A000010, A007755.

Programs

Haskell

a003434 n = fst $ until ((== 1) . snd)
                        (\(i, x) -> (i + 1, a000010 x)) (0, n)
-- Reinhard Zumkeller, Feb 08 2013, Jul 03 2011

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

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

Python

from sympy import totient
def A003434(n):
    c, m = 0, n
    while m > 1:
        c += 1
        m = totient(m)
    return c # Chai Wah Wu, Nov 14 2021

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