cp's OEIS Frontend

A049113 Number of powers of 2 in sequence obtained when phi (A000010) is repeatedly applied to n.

%I A049113 #22 Aug 27 2024 09:14:58
%S A049113 1,2,2,3,3,2,2,4,2,3,3,3,3,2,4,5,5,2,2,4,3,3,3,4,4,3,2,3,3,4,4,6,4,5,
%T A049113 4,3,3,2,4,5,5,3,3,4,4,3,3,5,3,4,6,4,4,2,5,4,3,3,3,5,5,4,3,7,5,4,4,6,
%U A049113 4,4,4,4,4,3,5,3,5,4,4,6,2,5,5,4,7,3,4,5,5,4,4,4,5,3,4,6,6,3,5,5,5,6,6,5,5
%N A049113 Number of powers of 2 in sequence obtained when phi (A000010) is repeatedly applied to n.
%H A049113 Amiram Eldar, <a href="/A049113/b049113.txt">Table of n, a(n) for n = 1..10000</a>
%F A049113 a(n) = A049108(n)-A049115(n). - _R. J. Mathar_, Sep 08 2021
%e A049113 If n = 164, the "iterated phi-sequence" for n is {164,80,32,16,8,4,2,1}. It includes 6 powers of 2 at the end, so a(164) = 6.
%p A049113 A049113 := proc(n)
%p A049113     local a, e;
%p A049113     e := n ;
%p A049113     a :=0 ;
%p A049113     while e > 1 do
%p A049113         if isA000079(e) then
%p A049113             a := a+1 ;
%p A049113         end if;
%p A049113         e := numtheory[phi](e) ;
%p A049113     end do:
%p A049113     1+a;
%p A049113 end proc:
%p A049113 seq(A049113(n),n=1..40) ; # _R. J. Mathar_, Jan 09 2017
%t A049113 pwrs2 = NestList[2#&, 1, 15];
%t A049113 Table[Length[Intersection[NestWhileList[EulerPhi[#]&, i, # > 1 &], pwrs2]], {i, 100}] (* _Harvey P. Dale_, Dec 12 2010 *)
%o A049113 (PARI) a(n)=while(n!=1<<valuation(n,2),n=eulerphi(n)); valuation(n,2)+1 \\ _Charles R Greathouse IV_, Feb 21 2013
%Y A049113 Cf. A000010, A049115, A049108.
%K A049113 nonn
%O A049113 1,2
%A A049113 _Labos Elemer_