A364631 -id:A364631 - cp's OEIS frontend

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

Torlach Rush, Jul 30 2023

nonn

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.

			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.

Cf. A000010, A001615, A003434, A364631.

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

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

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

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

A364932 a(n) = phi(psi(n)).

Original entry on oeis.org

1, 2, 2, 2, 2, 4, 4, 4, 4, 6, 4, 8, 6, 8, 8, 8, 6, 12, 8, 12, 16, 12, 8, 16, 8, 12, 12, 16, 8, 24, 16, 16, 16, 18, 16, 24, 18, 16, 24, 24, 12, 32, 20, 24, 24, 24, 16, 32, 24, 24, 24, 24, 18, 36, 24, 32, 32, 24, 16, 48, 30, 32, 32, 32, 24, 48, 32, 36, 32, 48, 24

Offset: 1

Torlach Rush, Aug 13 2023

Here phi is Euler's totient function and psi is the Dedekind psi function.
Values of psi(n), n > 1 are always greater than n, while values of phi(n), n > 1 are always less than n.
a(39270) = 41472 is the first term where phi(psi(n)) exceeds n.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000010, A001615, A293713, A364631.

f:= proc(n) local p; numtheory:-phi(n * mul(1+1/p, p = numtheory:-factorset(n))) end proc:
map(f, [$1..100]); # Robert Israel, Feb 13 2024

a[n_] := EulerPhi[n*Times @@ (1 + 1/FactorInteger[n][[;; , 1]])]; a[1] = 1; Array[a, 100] (* Amiram Eldar, Aug 13 2023 *)

a(n) = eulerphi(n * sumdivmult(n, d, issquarefree(d)/d)); \\ Michel Marcus, Aug 13 2023

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): return totient(psi(n))

a(n) = A000010(A001615(n)).

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

A364581 Numbers k such that the number of iterations of psi(phi(x)) starting at x = k and terminating when psi(phi(x)) = x (k is counted), -1 otherwise is the same for phi(psi(k)).

Original entry on oeis.org

1, 4, 8, 14, 15, 16, 21, 22, 26, 28, 32, 39, 44, 45, 46, 50, 51, 52, 56, 58, 64, 74, 82, 85, 86, 88, 92, 94, 98, 100, 104, 105, 111, 112, 114, 116, 118, 122, 128, 129, 135, 142, 146, 147, 148, 153, 154, 159, 164, 165, 166, 172, 176, 178, 182, 183, 184, 186, 188

Offset: 1

Torlach Rush, Jul 28 2023

nonn

Numbers k such that A364631(k) = A364642(k).
Conjecture: For each a(n), n > 1, a(n)*7 is a term.
Conjecture: For each even a(n), a(n)*2 is a term.

			a(1) = 1 is a term because A364631(1) = A364642(1).
a(2) = 4 is a term because A364631(4) = A364642(4).
a(3) = 8 is a term because A364631(8) = A364642(8).

Cf. A000010, A001615, A364631, A364642.

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

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 a364631(n):
    i = 1
    r = n
    while (True):
        rc = totient(psi(r))
        if (rc == r):
            break;
        r = rc
        i += 1
    return i
def a364642(n):
    i = 1
    r = n
    while (True):
        rc = psi(totient(r))
        if (rc == r):
            break;
        r = rc
        i += 1
    return i
# Output display terms.
for n in range(1,222):
    if(a364631(n) == a364642(n)):
        print(n, end = ", ")

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A364932 a(n) = phi(psi(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A364581 Numbers k such that the number of iterations of psi(phi(x)) starting at x = k and terminating when psi(phi(x)) = x (k is counted), -1 otherwise is the same for phi(psi(k)).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python