cp's OEIS Frontend

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.

%I A364631 #49 Aug 14 2023 14:17:34
%S A364631 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,
%T A364631 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,
%U A364631 6,7,6,7,7,7,6,6,6,7,6,7,7,7,6,7,7,7,6,7
%N 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.
%C A364631 Here phi is Euler's totient function and psi is the Dedekind psi function.
%C A364631 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.
%C A364631 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.
%C A364631 If n = 2^k then a(n) = k. Hence for any x, should x = 2^k then the process terminates.
%C A364631 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.
%C A364631 Question: Is -1 a term of this sequence?
%F A364631 a(2^k) = A003434(2^k) = k since phi(psi(2^k)) = phi(2^k) = 2^(k-1).
%e A364631 a(1) = 1 because phi(psi(1)) = 1.
%e A364631 a(2) = 1 because phi(psi(2)) = 2.
%e A364631 a(5) = 2 because phi(psi(5)) = 2, and phi(psi(2)) = 2.
%e A364631 a(9) = 3 because phi(psi(9)) = 4, phi(psi(4)) = 2, and phi(psi(2)) = 2.
%t A364631 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 *)
%o A364631 (Python)
%o A364631 from sympy.ntheory.factor_ import totient
%o A364631 from sympy import isprime, primefactors, prod
%o A364631 def psi(n):
%o A364631     plist = primefactors(n)
%o A364631     return n*prod(p+1 for p in plist)//prod(plist)
%o A364631 def a(n):
%o A364631     i = 1
%o A364631     r = n
%o A364631     while (True):
%o A364631         rc = totient(psi(r))
%o A364631         if (rc == r):
%o A364631             break;
%o A364631         r = rc
%o A364631         i += 1
%o A364631     return i
%o A364631 (PARI) dpsi(n) = n * sumdivmult(n, d, issquarefree(d)/d); \\ A001615
%o A364631 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
%Y A364631 Cf. A000010, A001615, A003434.
%K A364631 nonn
%O A364631 1,3
%A A364631 _Torlach Rush_, Jul 30 2023