A049115 a(n) is the number of iterations of the Euler phi function needed to reach a power of 2, when starting from n.

0, 0, 1, 0, 1, 1, 2, 0, 2, 1, 2, 1, 2, 2, 1, 0, 1, 2, 3, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 1, 2, 0, 2, 1, 2, 2, 3, 3, 2, 1, 2, 2, 3, 2, 2, 3, 4, 1, 3, 2, 1, 2, 3, 3, 2, 2, 3, 3, 4, 1, 2, 2, 3, 0, 2, 2, 3, 1, 3, 2, 3, 2, 3, 3, 2, 3, 2, 2, 3, 1, 4, 2, 3, 2, 1, 3, 3, 2, 3, 2, 3, 3, 2, 4, 3, 1, 2, 3, 2, 2, 3, 1, 2, 2, 2

Offset: 1

Author

Labos Elemer

Keywords

• nonn

Comments

a(n) = A227944(n) if n is not a power of 2. - Eric M. Schmidt, Oct 13 2013

Examples

			If n is a power of 2, then a(n)=0 by definition. If n = 59049, then by iterating with phi, we get 59049 -> 39366 -> 13122 -> 4374 -> 1458 -> 486 -> 162 -> 54 -> 18 -> 6 -> 2 -> 1. It took ten steps to reach the first power of 2 (2 in this case), so a(59049) = 10.
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000010, A003434, A049113, A057716, A209229, A227944.

Cf. also A064097, A064415, A329697.

Programs

Mathematica

Table[If[IntegerQ@ Log2@ n, 0, -1 + Length@ NestWhileList[EulerPhi, n, ! IntegerQ@ Log2@ # &]], {n, 105}] (* Michael De Vlieger, Aug 01 2017 *)

PARI

A049115(n) = if(!bitand(n,n-1),0,1+A049115(eulerphi(n))); \\ Antti Karttunen, Aug 28 2021

Formula

The smallest x so that Nest[ EulerPhi, n, x ] = 2^w is just achieved.

From Antti Karttunen, Aug 28 2021: (Start)

If A209229(n) = 1, then a(n) = 0, otherwise a(n) = 1 + a(A000010(n)).

a(n) <= A003434(n) and a(n) <= A329697(n) for all n.

(End)

Extensions

Definition corrected and simplified, example corrected by Antti Karttunen, Aug 28 2021