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,3

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?

Links

Table of n, a(n) for n=1..88.

Formula

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

Example

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.

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

Prog

(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
(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

Crossrefs

Cf. A000010, A001615, A003434.

Sequence in context: A095840 A131343 A089051 * A331255 A362881 A317359

Adjacent sequences: A364628 A364629 A364630 * A364632 A364633 A364634

Keyword

nonn

Author

Torlach Rush, Jul 30 2023

Status

approved