|
%I #22 Sep 08 2021 07:08:20
%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 R. 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.
%K nonn,nice,easy
%O 1,2
%A _Labos Elemer_
|
