A086420 -id:A086420 - cp's OEIS frontend

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

Amiram Eldar, Dec 19 2024

			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.

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

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

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]}]]]]

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), ", ")));}

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.

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

Original entry on oeis.org

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

Amiram Eldar, Dec 19 2024

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

			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.

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

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

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

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

a(A003586(n)) = 0.

cp's OEIS Frontend

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula