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

Comments

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

Links

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

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)

Example

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.

Mathematica

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

Prog

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

Crossrefs

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

Cf. also A064097, A064415, A329697.

Sequence in context: A039701 A025822 A051585 * A294204 A329697 A029367

Adjacent sequences: A049112 A049113 A049114 * A049116 A049117 A049118

Keyword

nonn

Author

Labos Elemer

Extensions

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

Status

approved