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

Links

Table of n, a(n) for n=1..105.

Formula

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

Example

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.

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 *)

Prog

(PARI) a(n)=while(n!=1<<valuation(n, 2), n=eulerphi(n)); valuation(n, 2)+1 \\ Charles R Greathouse IV, Feb 21 2013

Crossrefs

Cf. A000010, A049115, A049108.

Sequence in context: A332383 A340327 A332249 * A055093 A196058 A081844

Adjacent sequences: A049110 A049111 A049112 * A049114 A049115 A049116

Keyword

nonn

Author

Labos Elemer

Status

approved