A363612 Number of iterations of phi(x) at n needed to reach a square.

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

Offset: 1

Author

Darío Clavijo, Jun 11 2023

Keywords

• nonn

Crossrefs

Cf. A000010 (phi), A003434 (to reach 1).

Programs

Maple

a:= proc(n) option remember;
     `if`(issqr(n), 0, 1+a(numtheory[phi](n)))
    end:
seq(a(n), n=1..105);  # Alois P. Heinz, Jun 12 2023

Mathematica

a[n_] := -1 + Length @ NestWhileList[EulerPhi, n, ! IntegerQ[Sqrt[#]] &]; Array[a, 100] (* Amiram Eldar, Jun 11 2023 *)

PARI

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

Python

from sympy import totient
from sympy.ntheory.primetest import is_square
def a(n):
  x = n
  c = 0
  while not is_square(x):
    x = totient(x)
    c += 1
  return c