A379259 a(n) is the number of iterations that n requires to reach a 3-smooth number under the map x -> phi(x).

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

Offset: 1

Author

Amiram Eldar, Dec 19 2024

Keywords

• nonn
• easy

Comments

If k is a 3-smooth number then phi(k) is also a 3-smooth number. Therefore, a(n) counts the numbers that are not 3-smooth numbers in the trajectory from n to a 3-smooth number (including n if it is not a 3-smooth number).

The indices of records, 1, 5, 11, 23, 47, ..., seem to be A246491 except for the first term (checked up to A246491(15)).

Examples

			a(1) = a(2) = a(3) = a(4) = 0 because 1, 2, 3 and 4 are already 3-smooth numbers.
a(5) = 1 because after one iteration 5 -> phi(5) = 4, a 3-smooth number, 4, is reached.
a(23) = 3 because after 3 iterations 23 -> 22 -> 10 -> 4, a 3-smooth number, 4, is reached.
		

Links

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

Crossrefs

Cf. A000010, A003434, A003586, A086420, A122254, A246491.

Programs

Mathematica

smQ[n_] := n == Times @@ ({2, 3}^IntegerExponent[n, {2, 3}]); a[n_] := -1 + Length@ NestWhileList[EulerPhi, n, ! smQ[#] &]; Array[a, 100]

PARI

issm(n) = my(m = n >> valuation(n, 2)); m == 3^valuation(m, 3);
a(n) = {my(c = 0); while(!issm(n), c++; n = eulerphi(n)); c;}

Formula

a(A003586(n)) = 0.