A364642 a(n) is the number of iterations of psi(phi(x)) starting at x = n and terminating when psi(phi(x)) = x (n is counted), -1 otherwise.

1, 2, 1, 2, 3, 2, 4, 3, 4, 3, 5, 3, 5, 4, 4, 4, 5, 4, 6, 4, 5, 5, 6, 4, 6, 5, 6, 5, 6, 4, 7, 5, 6, 5, 6, 5, 7, 6, 6, 5, 7, 5, 7, 6, 6, 6, 7, 5, 7, 6, 6, 6, 7, 6, 7, 6, 7, 6, 7, 5, 8, 7, 7, 6, 7, 6, 8, 6, 7, 6, 8, 6, 8, 7, 7, 7, 8, 6, 8, 6, 8, 7, 8, 6, 7, 7, 7, 7

Offset: 1

Author

Torlach Rush, Jul 30 2023

Keywords

• nonn

Comments

Here phi is Euler totient function and psi is the Dedekind psi function.

psi(phi(1)) = 1, and psi(phi(3)) = 3. Each term of the sequence is evaluated by calling psi(phi(x)) (beginning at x = n) repeatedly until psi(phi(x)) = x. a(n) is then the number of iterations.

If n = 3*2^k then a(n) = k+1. Hence for any x, should x = 3*2^k then the process terminates.

If n = 2^k for k >= 2 then a(n) = k.

See A364631 for additional comments.

Examples

			a(1) = 1 since psi(phi(1)) = 1.
a(2) = 2 since psi(phi(2)) = 1, and psi(phi(1)) = 1.
a(5) = 3 since psi(phi(5)) = 6, psi(phi(6)) = 3, and psi(phi(3)) = 3.
a(9) = 4 since psi(phi(9)) = 12, psi(phi(12)) = 4, psi(phi(4)) = 3, and psi(phi(3)) = 3.
		

Crossrefs

Cf. A000010, A001615, A003434, A364631.

Programs

Mathematica

psi[n_] := n*Times @@ (1 + 1/FactorInteger[n][[;; , 1]]); psi[1] = 1; a[n_] := -1 + Length@ FixedPointList[psi[EulerPhi[#]] &, n]; Array[a, 100] (* Amiram Eldar, Aug 04 2023 *)

PARI

dpsi(n) = n * sumdivmult(n, d, issquarefree(d)/d); \\ A001615
a(n) = my(k=0, m); while (1, m=dpsi(eulerphi(n)); k++; if (m ==n, return(k)); n=m); \\ Michel Marcus, Aug 14 2023

Python

from sympy.ntheory.factor_ import totient
from sympy import isprime, primefactors, prod
def psi(n):
    plist = primefactors(n)
    return n*prod(p+1 for p in plist)//prod(plist)
def a(n):
    i = 1
    r = n
    while (True):
        rc = psi(totient(r))
        if (rc == r):
            break;
        r = rc
        i += 1
    return i

Formula

a(2^k) = A003434(2^k) = k, k >= 2.