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

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)).

Links

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

Formula

a(A003586(n)) = 0.

Example

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.

Mathematica

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

Prog

(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; }

Crossrefs

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

Sequence in context: A322452 A076754 A346482 * A364043 A339933 A101659

Adjacent sequences: A379256 A379257 A379258 * A379260 A379261 A379262

Keyword

nonn,easy

Author

Amiram Eldar, Dec 19 2024

Status

approved