A003434 -id:A003434 - cp's OEIS frontend

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

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.

A060605 a(n) = sum of lengths of the iteration sequences of Euler totient function from 1 to n.

Original entry on oeis.org

1, 3, 6, 9, 13, 16, 20, 24, 28, 32, 37, 41, 46, 50, 55, 60, 66, 70, 75, 80, 85, 90, 96, 101, 107, 112, 117, 122, 128, 133, 139, 145, 151, 157, 163, 168, 174, 179, 185, 191, 198, 203, 209, 215, 221, 227, 234, 240, 246, 252, 259, 265, 272, 277, 284, 290, 296, 302

Offset: 1

Labos Elemer, Apr 13 2001

nonn

Partial sums of A049108. - Joerg Arndt, Jan 06 2015

			Iteration sequences of Phi applied to 1, 2, 3, 4, 5, 6 give lengths 1, 2, 3, 3, 4, 3 with partial sums as follows:1, 3, 5, 9, 13, 16 resulting in first...6th terms here.

Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.
Paul Erdos, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]
Harold Shapiro, An arithmetic function arising from the phi function, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.

Cf. A049108, A003434.

Accumulate[Table[Length[NestWhileList[EulerPhi,n,#!=1&]],{n,60}]] (* Harvey P. Dale, Mar 23 2024 *)

a049108(n)=my(t=1); while(n>1, t++; n=eulerphi(n)); t;
vector(80, n, sum(j=1, n, a049108(j))) \\ Michel Marcus, Jan 06 2015

a(n) = sum( j=1..n, A049108(j) ).

A309672 Composite terms of A007755.

Original entry on oeis.org

2329, 4369, 10537, 35209, 281929, 1114129, 8978569, 16843009, 143163649, 286331153, 1086374209, 4295098369, 9198250129, 18325194049, 36507844609, 73016672273, 139055899009, 277033877569, 586397253889, 1103840280833, 4673067091009, 9382516064513, 17868687216769

Offset: 1

Jeppe Stig Nielsen, Oct 05 2019

nonn

10537 is a term because it is composite (= 41*257) and the totient (A000010) iterating "trajectory" starting from 10537 and ending in 1 is longer (length 15) than any similar trajectory starting from a (prime or nonprime) N < 10537.

Cf. A000010, A003434, A049108, A007755, A098196.

A363680 Number of iterations of phi(x) at n needed to reach a cube.

Original entry on oeis.org

0, 1, 2, 2, 3, 2, 3, 0, 3, 3, 4, 3, 4, 3, 1, 1, 2, 3, 4, 1, 4, 4, 5, 1, 2, 4, 0, 4, 5, 1, 2, 2, 2, 2, 2, 4, 5, 4, 2, 2, 3, 4, 5, 2, 2, 5, 6, 2, 5, 2, 3, 2, 3, 4, 3, 2, 5, 5, 6, 2, 3, 2, 5, 0, 3, 2, 3, 3, 3, 2, 3, 2, 3, 5, 3, 5, 3, 2, 3, 3, 5, 3, 4, 2, 1, 5, 3

Offset: 1

Darío Clavijo, Jun 14 2023

nonn

Cf. A000010, A363612, A003434.

a[n_] := a[n] = If[IntegerQ[Surd[n, 3]], 0, a[EulerPhi[n]] + 1]; Array[a, 100] (* Amiram Eldar, Jun 14 2023 *)

a(n) = my(nb=0); while(!ispower(n, 3), n=eulerphi(n); nb++); nb; \\ Michel Marcus, Jun 15 2023

from sympy import totient, integer_nthroot
def a(n):
  x = n
  c = 0
  while not integer_nthroot(x,3)[1]:
    x = totient(x)
    c += 1
  return c

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A060605 a(n) = sum of lengths of the iteration sequences of Euler totient function from 1 to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A309672 Composite terms of A007755.

Views

Author

Keywords

Comments

Crossrefs

A363680 Number of iterations of phi(x) at n needed to reach a cube.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

Python