A003434 -id:A003434 - 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.

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

Torlach Rush, Jul 30 2023

nonn

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?

			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.

Cf. A000010, A001615, A003434.

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

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

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

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

A364800 The number of iterations that n requires to reach 1 under the map x -> A356874(x).

Original entry on oeis.org

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

Offset: 1

Amiram Eldar, Aug 08 2023

a(n) is well-defined since A356874(1) = 1, and A356874(n) < n for n >= 2.

			For n = 3 the trajectory is 3 -> 2 -> 1. The number of iterations is 2, thus a(3) = 2.

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

Cf. A356874.

Similar sequences: A003434, A364801.

f[n_] := f[n] = Module[{d = IntegerDigits[n, 2], nd}, nd = Length[d]; Total[d * Fibonacci[Range[nd, 1, -1]]]]; (* A356874 *)
a[n_] := Length@ NestWhileList[f, n, # > 1 &] - 1; Array[a, 100]

f(n) = {my(b = binary(n), nb = #b); sum(i = 1, nb, b[i] * fibonacci(nb - i + 1));} \\ A356874
a(n) = if(n == 1, 0, a(f(n)) + 1);

a(n) = a(A356874(n)) + 1, for n >= 2.

A364801 The number of iterations that n requires to reach a fixed point under the map x -> A022290(x).

Original entry on oeis.org

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

Offset: 0

Amiram Eldar, Aug 08 2023

a(n) is well-defined since A022290(n) = n for n <= 3 (the fixed points), and A022290(n) < n for n >= 4.

			For n = 4 the trajectory is 4 -> 3. The number of iterations is 1, thus a(4) = 1.
For n = 6 the trajectory is 6 -> 5 -> 4 -> 3. The number of iterations is 3, thus a(6) = 3.

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

Cf. A022290.

Similar sequences: A003434, A364800.

f[n_] := f[n] = Module[{d = IntegerDigits[n, 2], nd}, nd = Length[d]; Total[d * Fibonacci[Range[nd + 1, 2, -1]]]]; (* A022290 *)
a[n_] := -2 + Length@ FixedPointList[f, n]; Array[a, 100, 0]

f(n) = {my(b = binary(n), nb = #b); sum(i = 1, nb, b[i] * fibonacci(nb - i + 2)); } \\ A022290
a(n) = if(n < 4, 0, a(f(n)) + 1);

def A364801(n):
    if n<4: return 0
    a, b, s = 1, 2, 0
    for i in bin(n)[-1:1:-1]:
        if int(i):
            s += a
        a, b = b, a+b
    return A364801(s)+1 # Chai Wah Wu, Aug 10 2023

a(n) = a(A022290(n)) + 1, for n >= 4.

A053096 When the Euler phi function is iterated with initial value A002110(n) = primorial, a(n) = number of iterations required to reach the fixed number = 1.

Original entry on oeis.org

1, 2, 4, 6, 9, 12, 16, 19, 23, 27, 31, 35, 40, 44, 49, 54, 59, 64, 69, 74, 79, 84, 90, 96, 102, 108, 114, 120, 125, 131, 136, 142, 149, 155, 161, 167, 173, 178, 185, 191, 198, 204, 210, 217, 223, 229, 235, 241, 248, 254, 261, 268, 275, 282, 290, 297, 304, 310

Offset: 1

Labos Elemer, Feb 28 2000

nonn

Analogous to A053025, A053034, A053044. For comparison: iteration of, e.g., A000005 to primorial i.v. is trivially computable: q(n)=A002110(n), d(q(n)) = 2^n, d(d(q(n))) = n+1 and so A036450(A002110(n)) = A000005(n+1).

			n=7, A002110(7)=510510; the corresponding iteration chain is {510510, 92160, 24576, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1}. Its length is 17, so the required number of iterations is a(7)=16.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A000010, A002110, A003434.

Array[-2 + Length@ FixedPointList[EulerPhi, Product[Prime@ i, {i, #}]] &, 58] (* Michael De Vlieger, Nov 20 2017 *)

a(n)=my(t=prod(i=1,n,prime(i)-1),s=1); while(t>1, t=eulerphi(t); s++); s \\ Charles R Greathouse IV, Jan 06 2016

A003434(n)=my(s);while(n>1,n=eulerphi(n);s++);s
first(n)=my(s=1); vector(n,k,s+=A003434(prime(k))-1) \\ Charles R Greathouse IV, Jan 06 2016

a(n) is the smallest number such that Nest[EulerPhi, A002110, a(n)]=1

A060607 Number of iterations of phi(x) at prime(n) needed to reach 1.

Original entry on oeis.org

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

Offset: 1

Labos Elemer, Apr 13 2001

Indices of records in this sequence: 1, 2, 3, 5, 7, 13, 23, 33, 55, 116, 184, 384, 719, 1323, 2010, 4289, 6543, 13044, 25685, 45859, 92479, 175261, 298106, 636606, ... The records appear to be A000027. - Michael De Vlieger, Mar 27 2019.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A000010, A000040, A003434, A006093, A049108.

Array[-1 + Length@ NestWhileList[EulerPhi, Prime@ #, # > 1 &] &, 105] (* Michael De Vlieger, Mar 27 2019 *)

a(n) = my(t=0, p=prime(n)); while(p>1, t++; p=eulerphi(p)); t; \\ Michel Marcus, Mar 27 2019

a(n) = A003434(A000040(n)). [corrected by Michel Marcus, Mar 27 2019]

a(n) = A003434(A006093(n)) + 1. - Amiram Eldar, Nov 27 2024

Name edited by Michel Marcus, Mar 27 2019

A225563 Numbers whose totient-trajectory can be partitioned into two sets with the same sum.

Original entry on oeis.org

3, 5, 7, 9, 11, 13, 15, 17, 25, 27, 31, 33, 35, 39, 41, 49, 51, 55, 61, 65, 69, 77, 81, 85, 87, 91, 95, 97, 103, 111, 115, 119, 121, 123, 125, 133, 137, 141, 143, 145, 153, 155, 159, 161, 175, 183, 185, 187, 193, 201, 203, 205, 209, 213, 215, 217, 219, 221

Offset: 1

Kevin L. Schwartz and Christian N. K. Anderson, May 10 2013

nonn

The "totient-trajectory" of a number m is the sequence obtained by starting with m and repeatedly applying the map x -> phi(x) (cf. A000010) until reaching 1.
Because all totient-trajectories contain only even numbers apart from the final 1 and (perhaps) the initial term ending in 1, only odd numbers will be in the sequence.
Conjecture: No totient-trajectory can be partitioned into an odd number of sets with the same sum.
Observation: for the first 1000 terms, numbers ending in 5 are more than twice as frequent as those ending in any other number.

			17 is in the sequence because its totient-trajectory is {17,16,8,4,2,1}, which can be partitioned into 17+4+2+1 = 16+8.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Christian N. K. Anderson)
Christian N. K. Anderson, Decomposition of the first 1000 terms.

Cf. A008683, A003434, A007755, A049108, A002202, A000010, A083207.

totQ[n_] := Module[{it = Most@FixedPointList[EulerPhi, n], sum, x}, sum = Plus @@ it; If[OddQ[sum], False, CoefficientList[Product[1 + x^i, {i, it}], x][[1 +sum/2]] > 0]]; Select[Range[221], totQ] (* Amiram Eldar, May 24 2020 *)

library(numbers); totseq<-function(x) { while(x[length(x)]>1) x[length(x)+1]=eulersPhi(x[length(x)]); x };
eqsum<-function(xvec) {
mkgrp<-function(grp) {
    if(length(grp)==length(xvec)) {
        tapply(xvec,grp,sum)->tot;
        if(length(tot)==2) if(tot[1]==tot[2]) {faxp<<-grp; return(T)}; return(F);
    }
    ifelse(mkgrp(c(grp,1)),T,mkgrp(c(grp,2)));
}
ifelse(length(xvec)<2,F,mkgrp(c()));
}
which(sapply(2*(1:100)-1,function(x) eqsum(totseq(x))))*2-1

Edited by N. J. A. Sloane, May 17 2013

A322418 Least k > 0 such that A014221(k) == A014221(k+1) mod n.

Original entry on oeis.org

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

Offset: 1

Jinyuan Wang, Dec 07 2018

nonn

For any fixed integer n > 0, the sequence 2 mod n, 2^2 mod n, 2^2^2 mod n, that is, the sequence {A014221(i) mod n} for i >= 1 is eventually constant. a(n) is the least index k such that A014221(k) mod n equals this constant.

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

			2, 4, 16, ... mod 6 equal 2, 4, 4, ..., so A014221(k) mod 6 = 4 for all k >= 2, hence a(6) = 2.

USAMO, Problem 3, 1991.

Cf. A014221, A038081, A000010, A003434.

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

a(n) <= A003434(n).
a(n) <= a(A000010(n)) + 1.
If A014221(k) == b(k) mod eulerphi(n), 0 < b(k) <= eulerphi(n), then a(n) is the least m > 0 such that 2^b(m-1) == 2^b(m) mod n.

A333870 The number of iterations of the absolute Möbius divisor function (A173557) required to reach from n to 1.

Original entry on oeis.org

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

Offset: 1

Amiram Eldar, Apr 08 2020

nonn

Apparently, the least number that reaches 1 after k iterations is A082449(k-1) (checked numerically for 1 <= k <= 17).

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

Amiram Eldar, Table of n, a(n) for n = 1..10000
Daeyeoul Kim, Umit Sarp, and Sebahattin Ikikardes, Iterating the Sum of Möbius Divisor Function and Euler Totient Function, Mathematics, Vol. 7, No. 11 (2019), pp. 1083-1094.

Cf. A003434, A082449, A173557.

f[p_, e_] := p - 1; u[1] = 1; u[n_] := Times @@ (f @@@ FactorInteger[n]);a[n_] := Length @ FixedPointList[u, n] - 2; Array[a, 100]

A340762 Numbers k such that iterations of phi(k), phi(phi(k)), ... end in ... 4, 2, 1.

Original entry on oeis.org

4, 5, 8, 10, 11, 12, 13, 15, 16, 17, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72

Offset: 1

Franz Vrabec, Jan 20 2021

nonn

Infinite set (see reference).

			11 is in the list because phi(phi(11)) = phi(10) = 4.

Robert Israel, Table of n, a(n) for n = 1..10000
Eliot T. Jacobson and Alan E. Parks, Infinite branches of the phi-tree, Amer. Math. Monthly, Vol. 93, No. 7 (August-September 1986), pp. 552-554.
Keith Matthews, Solving phi(x)=n, where phi(x) is Euler's totient function.

Cf. A000010, A340765 (complement relative to {n>=4}).

Cf. A003434, A032358, A049108.

filter:= proc(n) option remember;
  if n < 4 then false
  elif n = 4 then true
  else procname(numtheory:-phi(n))
  fi
end proc:
select(filter, [$4..100]); # Robert Israel, Dec 23 2021

Select[Range[4, 72], FixedPointList[EulerPhi, #][[-4]] == 4 &] (* Amiram Eldar, Jan 27 2021 *)

isok(k) = if (k>=4, while((k!=6) && (k!=4), k=eulerphi(k))); k == 4; \\ Michel Marcus, Feb 01 2021

A340765 Numbers k such that iterations of phi(k), phi(phi(k)), ... end in ... 6, 2, 1.

Original entry on oeis.org

6, 7, 9, 14, 18, 19, 27, 38, 54, 81, 162, 163, 243, 326, 486, 487, 729, 974, 1458, 1459, 2187, 2918, 4374, 6561, 13122, 19683, 39366, 39367, 59049, 78734, 118098, 177147, 354294, 531441, 1062882, 1594323, 3188646, 4782969, 9565938, 14348907, 28697814, 43046721, 86093442, 86093443, 129140163, 172186886

Offset: 1

Franz Vrabec, Jan 20 2021

nonn

Infinite set (see reference).

Contains 3^k for k >= 2 and 2*3^k for k >= 1, and all members of A111974 except 3. - Robert Israel, Dec 23 2021

			19 is in the list because phi(phi(19)) = phi(18) = 6.

Robert Israel, Table of n, a(n) for n = 1..1000
Eliot T. Jacobson and Alan E. Parks, Infinite branches of the phi-tree, Amer. Math. Monthly, Vol. 93, No. 7 (August-September 1986), pp. 552-554.
Keith Matthews, Solving phi(x)=n, where phi(x) is Euler's totient function.

Cf. A000010, A340762 (complement relative to {n>=4}).

Cf. A003434, A032358, A049108, A111974.

R:= {6}: Agenda:= {6}: count:= 1:
while count - nops(Agenda) < 99 do
  v:= min(Agenda);
  W:= convert(numtheory:-invphi(v),set);
  count:= count + nops(W);
  Agenda:= Agenda minus {v} union W;
  R:= R union W;
od:
sort(select(`<=`, convert(R,list),min(Agenda))); # Robert Israel, Dec 23 2021

Select[Range[4, 10000], FixedPointList[EulerPhi, #][[-4]] == 6 &] (* Amiram Eldar, Jan 27 2021 *)

isok(k) = if (k>=6, while((k!=6) && (k!=4), k=eulerphi(k))); k == 6; \\ Michel Marcus, Feb 01 2021

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A364800 The number of iterations that n requires to reach 1 under the map x -> A356874(x).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A364801 The number of iterations that n requires to reach a fixed point under the map x -> A022290(x).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A053096 When the Euler phi function is iterated with initial value A002110(n) = primorial, a(n) = number of iterations required to reach the fixed number = 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A060607 Number of iterations of phi(x) at prime(n) needed to reach 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A225563 Numbers whose totient-trajectory can be partitioned into two sets with the same sum.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

R

Extensions

A322418 Least k > 0 such that A014221(k) == A014221(k+1) mod n.

Views

Author

Keywords

Comments