cp's OEIS Frontend

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

%I A049108 #27 Aug 18 2024 20:19:43
%S A049108 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 A049108 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 A049108 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 A049108 a(n) is the number of iterations of Euler phi function needed to reach 1 starting at n (n is counted).
%H A049108 Reinhard Zumkeller, <a href="/A049108/b049108.txt">Table of n, a(n) for n = 1..10000</a>
%F A049108 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 A049108 log_3 n << a(n) << log_2 n. - _Charles R Greathouse IV_, Feb 07 2012
%e A049108 If n=164 the trajectory is {164,80,32,16,8,4,2,1}. Its length is 8, thus a(164)=8.
%p A049108 A049108 := proc(n)
%p A049108     local a, e;
%p A049108     e := n ;
%p A049108     a :=0 ;
%p A049108     while e > 1 do
%p A049108         a := a+1 ;
%p A049108         e := numtheory[phi](e) ;
%p A049108     end do:
%p A049108     1+a;
%p A049108 end proc:
%p A049108 seq(A049108(n),n=1..60) ; # _R. J. Mathar_, Sep 08 2021
%t A049108 f[n_] := Length[NestWhileList[ EulerPhi, n, # != 1 &]]; Array[f, 105] (* _Robert G. Wilson v_, Feb 07 2012 *)
%o A049108 (PARI) a(n)=my(t=1);while(n>1,t++;n=eulerphi(n));t \\ _Charles R Greathouse IV_, Feb 07 2012
%Y A049108 Cf. A000010, A007755. Equals A003434 + 1. Row lengths of A375478.
%K A049108 nonn,nice,easy
%O A049108 1,2
%A A049108 _Labos Elemer_