login
A049113
Number of powers of 2 in sequence obtained when phi (A000010) is repeatedly applied to n.
6
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
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
KEYWORD
nonn
AUTHOR
STATUS
approved