A379258 a(n) is the number of iterations of the Euler phi function needed to reach 1 starting at the n-th 3-smooth number.

1, 2, 3, 3, 3, 4, 4, 4, 5, 4, 5, 5, 6, 5, 6, 5, 7, 6, 6, 7, 6, 8, 7, 6, 8, 7, 7, 9, 8, 7, 9, 8, 7, 10, 9, 8, 8, 10, 9, 8, 11, 10, 9, 8, 11, 10, 9, 12, 9, 11, 10, 9, 12, 11, 10, 13, 9, 12, 11, 10, 13, 10, 12, 11, 14, 10, 13, 12, 11, 14, 10, 13, 12, 15, 11, 14, 11

Offset: 1

Author

Amiram Eldar, Dec 19 2024

Keywords

• nonn
• easy

Examples

			a(6) = 4 because the 6th 3-smooth number is A003586(6) = 8, and 4 iterations of phi are needed to reach 1: 8 -> 4 -> 2 -> 1.
		

Links

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

Crossrefs

Cf. A000010, A003586, A049108, A086420, A022328, A022329, A022330, A022331, A202821.

Programs

Mathematica

f[n_] := Module[{e2 = IntegerExponent[n, 2], e3 = IntegerExponent[n, 3]}, e2 + e3 + 1 + Boole[e2 == 0]]; f[1] = 1; With[{max = 3*10^4}, f /@ Sort[Flatten[Table[2^i*3^j, {i, 0, Log2[max]}, {j, 0, Log[3, max/2^i]}]]]]

PARI

list(lim) = {my(e2, e3); print1(1, ", "); for(k = 2, lim, e2 = valuation(k, 2); e3 = valuation(k, 3); if(k == (1 << e2) * 3^e3, print1(e2 + e3 + 1 + (e2 == 0), ", ")));}

Formula

a(n) = A049108(A003586(n)).

a(n) = valuation(A003586(n), 2) + valuation(A003586(n), 3) + 1 + [valuation(A003586(n), 2) == 0] for n > 1, where [] is the Iverson bracket.

a(n) = A022328(n) + A022329(n) + 1 + [n is in A022330], for n > 1.

a(A022330(n)) = n + 2 for n >= 1.

a(A022331(n)) = n + 1 for n >= 0.

a(A202821(n)) = 2*n + 1, for n >= 0.