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

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, 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, 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

Offset: 1

Author

Labos Elemer

Keywords

• nonn

Examples

			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.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000010, A049115, A049108.

Programs

Maple

A049113 := proc(n)
    local a, e;
    e := n ;
    a :=0 ;
    while e > 1 do
        if isA000079(e) then
            a := a+1 ;
        end if;
        e := numtheory[phi](e) ;
    end do:
    1+a;
end proc:
seq(A049113(n),n=1..40) ; # R. J. Mathar, Jan 09 2017

Mathematica

pwrs2 = NestList[2#&, 1, 15];
Table[Length[Intersection[NestWhileList[EulerPhi[#]&, i, # > 1 &], pwrs2]], {i, 100}] (* Harvey P. Dale, Dec 12 2010 *)

PARI

a(n)=while(n!=1<Charles R Greathouse IV, Feb 21 2013

Formula

a(n) = A049108(n)-A049115(n). - R. J. Mathar, Sep 08 2021