A003434 -id:A003434 - cp's OEIS frontend

A362024 The number of iterations of the infinitary totient function iphi (A064380) required to reach from n to 1.

1, 2, 3, 4, 3, 4, 4, 5, 5, 6, 5, 6, 5, 6, 7, 8, 7, 8, 7, 6, 6, 7, 6, 7, 8, 8, 9, 10, 7, 8, 8, 7, 7, 8, 9, 10, 7, 9, 8, 9, 9, 10, 9, 8, 11, 12, 8, 9, 9, 10, 10, 11, 7, 10, 9, 9, 11, 12, 8, 9, 9, 10, 9, 10, 8, 9, 11, 10, 9, 10, 8, 9, 9, 8, 10, 10, 10, 11, 11, 12

Offset: 2

Amiram Eldar, Apr 05 2023

nonn

			a(6) = 3 since there are 3 iterations from 6 to 1: iphi(6) = 3, iphi(3) = 2 and iphi(2) = 1.

Amiram Eldar, Table of n, a(n) for n = 2..10000

Cf. A064380, A362025 (indices of records).

Similar sequences: A003434, A049865, A333609.

infCoprimeQ[n1_, n2_] := Module[{g = GCD[n1, n2]}, If[g == 1, True, AllTrue[FactorInteger[g][[;; , 1]], BitAnd @@ IntegerExponent[{n1, n2}, #] == 0 &]]];
iphi[n_] := Sum[Boole[infCoprimeQ[j, n]], {j, 1, n - 1}];
a[n_] := Length@ NestWhileList[iphi, n, # > 1 &] - 1;
Array[a, 100, 2]

isinfcoprime(n1, n2) = {my(g = gcd(n1, n2), p, e1, e2); if(g == 1, return(1)); p = factor(g)[, 1]; for(i=1, #p, e1 = valuation(n1, p[i]); e2 = valuation(n2, p[i]); if(bitand(e1, e2) > 0, return(0))); 1; }
iphi(n) = sum(j = 1, n-1, isinfcoprime(j, n));
a(n) = if(n==2, 1, a(iphi(n)) + 1);

a(n) = a(A064380(n)) + 1 for n > 2.

A060606 The n-th term is the sum of lengths of iteration chains to get fixed points (=1) for the Euler totient function from 1 to n.

Original entry on oeis.org

0, 1, 3, 5, 8, 10, 13, 16, 19, 22, 26, 29, 33, 36, 40, 44, 49, 52, 56, 60, 64, 68, 73, 77, 82, 86, 90, 94, 99, 103, 108, 113, 118, 123, 128, 132, 137, 141, 146, 151, 157, 161, 166, 171, 176, 181, 187, 192, 197, 202, 208, 213, 219, 223, 229, 234, 239, 244, 250, 255

Offset: 0

Labos Elemer, Apr 13 2001

nonn

			Iteration sequences of Phi applied to 1,2,3,4,5,6 give lengths 0,1,2,2,3,2 with partial sums as follows:0,1,3,5,8,10 resulting in the first six terms of this sequence. It differs by n from the analogous sums applied to A049108 sequence.

Amiram Eldar, Table of n, a(n) for n = 0..10000
Hartosh Singh Bal and Gaurav Bhatnagar, Prime number conjectures from the Shapiro class structure, arXiv:1903.09619 [math.NT], 2019. See function S(n), p. 2.
Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.
Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]
Harold Shapiro, An arithmetic function arising from Phi-function, American Math. Monthly, Vol. 50, No. 1 (1943), pp. 18-30.

Cf. A003434, A049108.

f[1] = 0; f[n_] := f[n] = f[EulerPhi[n]] + 1; Accumulate[Array[f, 100]] (* Amiram Eldar, Nov 27 2024 *)

a(n) = Sum_{j=1..n} A003434(j).

A060609 Repeatedly apply Euler phi to n-th prime; a(n) = highest power of 2 that is seen.

Original entry on oeis.org

2, 2, 4, 2, 4, 4, 16, 2, 4, 4, 8, 4, 16, 4, 4, 8, 4, 16, 8, 8, 8, 8, 16, 16, 32, 16, 32, 8, 4, 16, 4, 16, 64, 8, 8, 16, 16, 2, 16, 8, 16, 16, 8, 64, 8, 16, 16, 8, 16, 8, 16, 32, 64, 16, 256, 16, 16, 8, 16, 32, 8, 16, 32, 32, 32, 16, 32, 32, 8, 16, 64, 16, 32, 32, 4, 8, 64, 32, 64, 128

Offset: 1

Labos Elemer, Apr 13 2001

			n=100,p(100)=541, Phi-iteration chain is {541,540,144,48,16,8,4,2,1} with 9 terms. The largest power of 2 is the 5th term=16=a(100).

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000040, A000010, A049108, A049113, A049116, A003434.

Table[Max[Select[NestWhileList[EulerPhi[#]&,Prime[n],#>1&],IntegerQ[Log2[#]]&]],{n,80}] (* Harvey P. Dale, Aug 23 2025 *)

a(n) = A049116(A000040(n)).

A060610 Repeatedly apply Euler phi to the n-th prime; a(n) is the number of terms in the resulting iteration chain which are not powers of 2 (number of initial iterations until reaching the first power of 2).

Original entry on oeis.org

0, 1, 1, 2, 2, 2, 1, 3, 3, 3, 2, 3, 2, 3, 4, 3, 4, 2, 3, 3, 3, 3, 3, 3, 2, 3, 2, 4, 4, 3, 4, 3, 2, 4, 4, 3, 3, 5, 4, 4, 4, 3, 4, 2, 4, 3, 3, 4, 4, 4, 4, 3, 2, 4, 1, 4, 4, 4, 4, 3, 5, 4, 3, 3, 3, 4, 3, 3, 5, 4, 3, 5, 3, 3, 5, 5, 3, 3, 3, 2, 4, 3, 4, 4, 4, 3, 3, 4, 4, 3, 5, 4, 6, 4, 4, 5, 5, 3, 4, 4, 4, 5, 4, 4, 4

Offset: 1

Labos Elemer, Apr 13 2001

			n=100,p(100)=541, Phi-iteration chain is {541,540,144,48,16,8,4,2,1} with 9 terms. The first 4 terms (541,540,144,48) are not powers of 2, som a(100)=4.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000040, A000010, A049108, A049113, A049116, A049115, A003434.

Table[Count[FixedPointList[EulerPhi[#]&,Prime[n]],?(!IntegerQ[ Log[ 2,#]]&)],{n,110}] (* _Harvey P. Dale, Sep 18 2016 *)

a(n) = A049115(A000040(n)).

Definition clarified by Harvey P. Dale, Sep 18 2016

A064674 Number of primes q such that phiter(q)=n where phiter(n)=A064415(n).

Original entry on oeis.org

0, 2, 2, 3, 6, 12, 23, 46, 94, 198, 424, 854, 1859, 3884, 8362, 17837, 38977, 84188, 183167, 398685, 874078

Offset: 0

Christian WEINSBERG (cweinsbe(AT)fr.packardbell.org), Oct 10 2001

For n>1, a(n) is the number of primes in class n of the Phi iteration. See A003434 and A058812. [From T. D. Noe, Nov 05 2008]

Cf. A000010, A003434, A064415, A064416.

a(12)-a(16) from T. D. Noe, Nov 05 2008

a(17)-a(20) from Sean A. Irvine, Jul 22 2023

A308964 Least k > 0 such that A014222(k) == A014222(k+1) (mod n).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2, 2, 2, 2, 3, 2, 3, 2, 2, 3, 4, 1, 3, 2, 2, 2, 3, 2, 3, 2, 3, 3, 2, 2, 3, 3, 2, 2, 2, 2, 3, 3, 2, 4, 5, 2, 3, 3, 3, 2, 3, 2, 3, 2, 3, 3, 4, 2, 3, 3, 2, 3, 2, 3, 4, 3, 4, 2, 3, 2, 2, 3, 3, 3, 3, 2, 3, 2, 3, 2, 3, 2, 3, 3, 3

Offset: 1

Jinyuan Wang, Aug 30 2019

nonn

a(n) is the least positive integer k such that the sequence {A014222(i) mod n} for i >= k is constant. Proof: if g(i) = A014222(i), then n divides 3^g(i-1)*(3^(g(i)-g(i-1)) - 1) when g(i) == g(i+1) (mod n). g(j)-g(j-1) divides g(j+1)-g(j) for any j > 0, therefore, 3^(g(i)-g(i-1)) - 1 divides 3^(g(i+1)-g(i)) - 1. Then n divides 3^g(i)*(3^(g(i+1)-g(i)) - 1) = g(i+2) - g(i+1), that is, g(i) == g(i+1) == g(i+2) (mod n). Since a(n) is the least positive integer k such that g(k) == g(k+1) (mod n), the sequence {A014222(i) mod n} for i >= k is constant.

A014222(k+1) - A014222(k) is the largest n such that a(n) = k.

			3, 27, 7625597484987, ... mod 5 equal 3, 2, 2, ..., so A014222(k) mod 5 = 2 for all k >= 2, hence a(5) = 2.

Cf. A014222, A308972, A322418.

a(n) = {my(c=0, k=1, x=0, d=n); while(k==1, z=x++; y=0; b=1; while(z>0, while(y++

a(n) <= A003434(n).

a(n) <= a(A000010(n)) + 1.

A308972 Least k > 0 such that A114561(k) == A114561(k+1) mod n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 2, 1, 2, 2, 2, 1, 2, 2, 1, 3, 4, 2, 3, 2, 2, 1, 2, 2, 3, 2, 3, 2, 2, 1, 2, 2, 2, 2, 3, 1, 2, 3, 2, 4, 5, 2, 2, 3, 2, 2, 3, 2, 3, 2, 2, 2, 3, 2, 3, 3, 1, 2, 2, 3, 4, 2, 4, 2, 3, 2, 2, 2, 3, 2, 3, 2, 3, 2, 3, 3, 4, 1, 2, 2, 2

Offset: 1

Jinyuan Wang, Aug 30 2019

nonn

A114561(k+1) - A114561(k) is the largest n such that a(n) = k.

			4, 4^4, 4^4^4, ... mod 8 equal 4, 0, 0, ..., so A114561(k) mod 8 = 0 for all k >= 2, hence a(8) = 2.

Cf. A114561, A308964, A322418.

a(n) = {c=0; k=1; x=0; d=n; while(k==1, z=x++; y=0; b=1; while(z>0, while(y++

a(n) <= A003434(n).

a(n) <= a(A000010(n)) + 1. Proof: a(n) <= a(eulerphi(n)) + 1. Proof: If A114561(i) == b(i) mod eulerphi(n), 0 < b(i) <= eulerphi(n), then a(n) is the least k > 0 such that 2^b(k-1) == 2^b(k) mod n. Since A114561(a(eulerphi(n))) == A114561(a(eulerphi(n)) + 1), k <= a(A000010(n)) + 1.

A350969 Let phi^(k) denote the k-th iterate of phi (A000010); a(n) is smallest positive k such that phi^(k)(Fibonacci(n)) = 1.

Original entry on oeis.org

1, 1, 1, 2, 3, 3, 4, 4, 5, 6, 7, 6, 8, 8, 8, 9, 9, 10, 11, 12, 11, 13, 13, 13, 15, 16, 15, 16, 17, 17, 19, 18, 19, 19, 20, 20, 21, 22, 22, 23, 26, 23, 25, 25, 26, 27, 28, 27, 28, 30, 28, 31, 32, 30, 34, 32, 33, 34, 35, 34, 38, 37, 36, 37, 39, 38, 40, 39, 40, 40

Offset: 1

N. J. A. Sloane, Mar 03 2022

nonn

a(n) <= n.

The Fibonacci Quarterly asks what the range of a(n) is. For example, is a(n) ever equal to 14 or 24?

			Iterating phi, F_7 = 13 -> 12 -> 4 -> 2 -> 1 takes 4 steps to reach 1, so a(7) = 4.

Alois P. Heinz, Table of n, a(n) for n = 1..450
Douglas Lind (Proposer), Problem B-51, Elementary Problems and Solutions, The Fibonacci Quarterly, Vol. 2, No. 3 (1964), p. 232; Solution, ibid., Vol. 60, No. 1 (2022), pp. 83-84.
S. Sivasankaranarayana Pillai, On a function connected with phi(n), Bull. Amer. Math. Soc., Vol. 35, No. 6 (1929), pp. 837-841.

Cf. A000010, A000045, A003434, A049108, A060607.

a:= proc(n) uses numtheory; local f, k;
      f:= phi((<<0|1>, <1|1>>^n)[1, 2]);
      for k while f>1 do f:= phi(f) od; k
    end:
seq(a(n), n=1..70);  # Alois P. Heinz, Mar 03 2022

a[1] = a[2] = 1; a[n_] := Length@NestWhileList[EulerPhi, Fibonacci[n], # > 1 &] - 1; Array[a, 100] (* Amiram Eldar, Mar 03 2022 *)

a(n) = A049108(A000045(n)) - 1, for n > 2. - Amiram Eldar, Mar 03 2022.

a(n) = A003434(A000045(n)) for n > 2. - Alois P. Heinz, Mar 03 2022

A363612 Number of iterations of phi(x) at n needed to reach a square.

Original entry on oeis.org

0, 1, 2, 0, 1, 2, 3, 1, 0, 1, 2, 1, 2, 3, 2, 0, 1, 3, 4, 2, 2, 2, 3, 2, 0, 2, 4, 2, 3, 2, 3, 1, 3, 1, 3, 0, 1, 4, 3, 1, 2, 2, 3, 3, 3, 3, 4, 1, 0, 3, 2, 3, 4, 4, 2, 3, 1, 3, 4, 1, 2, 3, 1, 0, 2, 3, 4, 2, 4, 3, 4, 3, 4, 1, 2, 1, 2, 3, 4, 2, 0, 2, 3, 3, 1, 3, 4

Offset: 1

Darío Clavijo, Jun 11 2023

nonn

Cf. A000010 (phi), A003434 (to reach 1).

a:= proc(n) option remember;
     `if`(issqr(n), 0, 1+a(numtheory[phi](n)))
    end:
seq(a(n), n=1..105);  # Alois P. Heinz, Jun 12 2023

a[n_] := -1 + Length @ NestWhileList[EulerPhi, n, ! IntegerQ[Sqrt[#]] &]; Array[a, 100] (* Amiram Eldar, Jun 11 2023 *)

a(n) = my(nb=0); while(!issquare(n), n=eulerphi(n); nb++); nb; \\ Michel Marcus, Jun 15 2023

from sympy import totient
from sympy.ntheory.primetest import is_square
def a(n):
  x = n
  c = 0
  while not is_square(x):
    x = totient(x)
    c += 1
  return c

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.

Original entry on oeis.org

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.

cp's OEIS Frontend

A362024 The number of iterations of the infinitary totient function iphi (A064380) required to reach from n to 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A060606 The n-th term is the sum of lengths of iteration chains to get fixed points (=1) for the Euler totient function from 1 to n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A060609 Repeatedly apply Euler phi to n-th prime; a(n) = highest power of 2 that is seen.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A060610 Repeatedly apply Euler phi to the n-th prime; a(n) is the number of terms in the resulting iteration chain which are not powers of 2 (number of initial iterations until reaching the first power of 2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A064674 Number of primes q such that phiter(q)=n where phiter(n)=A064415(n).

Views

Author

Keywords

Comments

Crossrefs

Extensions

A308964 Least k > 0 such that A014222(k) == A014222(k+1) (mod n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A308972 Least k > 0 such that A114561(k) == A114561(k+1) mod n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A350969 Let phi^(k) denote the k-th iterate of phi (A000010); a(n) is smallest positive k such that phi^(k)(Fibonacci(n)) = 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple