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

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

Offset: 1

Author

Torlach Rush, Jul 30 2023

Keywords

• nonn

Comments

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

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

Values of psi(x) are always greater that x, while values of phi(x) are always less than x. It appears the tendency for phi(x) to converge is greater than that of psi(x) to diverge.

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

The process will fail to terminate only if the number of iterations where phi(psi(x)) > x continues to be greater than the number of iterations where phi(psi(x)) <= x.

Question: Is -1 a term of this sequence?

Examples

			a(1) = 1 because phi(psi(1)) = 1.
a(2) = 1 because phi(psi(2)) = 2.
a(5) = 2 because phi(psi(5)) = 2, and phi(psi(2)) = 2.
a(9) = 3 because phi(psi(9)) = 4, phi(psi(4)) = 2, and phi(psi(2)) = 2.
		

Crossrefs

Cf. A000010, A001615, A003434.

Programs

Mathematica

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

PARI

dpsi(n) = n * sumdivmult(n, d, issquarefree(d)/d); \\ A001615
a(n) = my(k=0, m); while (1, m=eulerphi(dpsi(n)); k++; if (m ==n, return(k)); n=m); \\ Michel Marcus, Aug 07 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 = totient(psi(r))
        if (rc == r):
            break;
        r = rc
        i += 1
    return i

Formula

a(2^k) = A003434(2^k) = k since phi(psi(2^k)) = phi(2^k) = 2^(k-1).