A049108 - OEIS

%I #27 Aug 18 2024 20:19:43

%S 1,2,3,3,4,3,4,4,4,4,5,4,5,4,5,5,6,4,5,5,5,5,6,5,6,5,5,5,6,5,6,6,6,6,

%T 6,5,6,5,6,6,7,5,6,6,6,6,7,6,6,6,7,6,7,5,7,6,6,6,7,6,7,6,6,7,7,6,7,7,

%U 7,6,7,6,7,6,7,6,7,6,7,7,6,7,8,6,8,6,7,7,8,6,7,7,7,7,7,7,8,6,7,7,8,7,8,7,7

%N a(n) is the number of iterations of Euler phi function needed to reach 1 starting at n (n is counted).

%H Reinhard Zumkeller, <a href="/A049108/b049108.txt">Table of n, a(n) for n = 1..10000</a>

%F 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

%F log_3 n << a(n) << log_2 n. - _Charles R Greathouse IV_, Feb 07 2012

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

%p A049108 := proc(n)

%p     local a, e;

%p     e := n ;

%p     a :=0 ;

%p     while e > 1 do

%p         a := a+1 ;

%p         e := numtheory[phi](e) ;

%p     end do:

%p     1+a;

%p end proc:

%p seq(A049108(n),n=1..60) ; # _R. J. Mathar_, Sep 08 2021

%t f[n_] := Length[NestWhileList[ EulerPhi, n, # != 1 &]]; Array[f, 105] (* _Robert G. Wilson v_, Feb 07 2012 *)

%o (PARI) a(n)=my(t=1);while(n>1,t++;n=eulerphi(n));t \\ _Charles R Greathouse IV_, Feb 07 2012

%Y Cf. A000010, A007755. Equals A003434 + 1. Row lengths of A375478.

%K nonn,nice,easy

%O 1,2

%A _Labos Elemer_