A049108 -id:A049108 - cp's OEIS frontend

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

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

A334196 a(1) = 0, then after the first differences of A003434.

Original entry on oeis.org

0, 1, 1, 0, 1, -1, 1, 0, 0, 0, 1, -1, 1, -1, 1, 0, 1, -2, 1, 0, 0, 0, 1, -1, 1, -1, 0, 0, 1, -1, 1, 0, 0, 0, 0, -1, 1, -1, 1, 0, 1, -2, 1, 0, 0, 0, 1, -1, 0, 0, 1, -1, 1, -2, 2, -1, 0, 0, 1, -1, 1, -1, 0, 1, 0, -1, 1, 0, 0, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, -2, 2, -2, 1, 0, 1, -2, 1, 0, 0, 0, 0, 0, 1, -2, 1, 0, 1, -1, 1, -1, 0

Offset: 1

Antti Karttunen, Apr 18 2020

sign

Also, from a(2) onward the first differences of A049108, and from a(3) onward the first differences of A032358.

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000010, A003434, A032358, A049108, A334195.

Differences[Array[Length[FixedPointList[EulerPhi, #]] &, 100, 0]] (* Paolo Xausa, Aug 18 2024 *)

A003434(n) = for(k=0, n, n>1 || return(k); n=eulerphi(n));
A334196(n) = if(1==n,0,A003434(n)-A003434(n-1));

a(1) = 0; and for n > 1, a(n) = A003434(n) - A003434(n-1).

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

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

A180633 a(n) is the number of iterations of function f(x) = phi(x)-1 needed before zero is reached, when starting from the initial value x = n.

Original entry on oeis.org

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

Offset: 0

Carmine Suriano, Sep 13 2010

nonn

Since phi(n) < n it follows that phi(n)-1 < n-1; therefore, after each iteration the argument decreases and eventually will reach zero.

Solution of equation phi(-1 + phi(-1 + phi(-1 + ...(phi(n))...))) = 1 where the totient function phi is applied a(n) times. (The original name of the sequence.)

			a(11)=5 since phi(-1+phi(-1+phi(-1+phi(-1+phi(-1+phi(11))))))=
phi(-1+phi(-1+phi(-1+phi(-1+phi(-1+10)))))=
phi(-1+phi(-1+phi(-1+phi(-1+6))))=
phi(-1+phi(-1+phi(-1+4)))=
phi(-1+phi(-1+2))=
phi(-1+1)=1 after 5 iterations.

Antti Karttunen, Table of n, a(n) for n = 0..10000

Cf. A000010.

Cf. A049108. - Robert G. Wilson v, Sep 25 2010

f[n_] := If[n < 3, 1, Length@ NestWhileList[ EulerPhi@# -1 &, n, # != 1 &]]; Array[f, 93, 0] (* Robert G. Wilson v, Sep 25 2010 *)

(define (A180633 n) (if (zero? n) n (+ 1 (A180633 (+ -1 (A000010 n)))))) ;; Antti Karttunen, Aug 07 2017

a(0) = 0; for n >= 1, a(n) = 1 + a(A000010(n)-1). - Antti Karttunen, Aug 07 2017

Corrected a(18), a(19) & a(73) and extended past a(80) by Robert G. Wilson v, Sep 25 2010

Name changed and value of a(0) changed from 1 to 0 by Antti Karttunen, Aug 07 2017

A287841 Number of iterations of number of distinct prime factors (A001221) needed to reach 1 starting at n (n is counted).

Original entry on oeis.org

1, 2, 2, 2, 2, 3, 2, 2, 2, 3, 2, 3, 2, 3, 3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 2, 3, 3, 3, 3, 2, 3, 3, 3, 2, 3, 2, 3, 3, 3, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 2, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 3, 2, 3, 2, 3, 3, 3, 3, 3, 2, 3, 2, 3, 2, 3, 3, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 3, 2, 3, 3, 3, 2, 3, 2, 3, 3

Offset: 1

Ilya Gutkovskiy, Jun 01 2017

nonn

			If n = 6 the trajectory is {6, 2, 1}. Its length is 3, thus a(6) = 3.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Eric Weisstein's World of Mathematics, Distinct Prime Factors
Index entries for sequences computed from exponents in factorization of n

Cf. A001221, A036430, A036459, A049108, A073855, A115658 (first occurrence), A246655 (positions of 2).

f[n_] := Length[NestWhileList[ PrimeNu, n, # != 1 &]]; Array[f, 105]
a[1] = 1; a[n_] := a[n] = a[PrimeNu[n]] + 1; Table[a[n], {n, 105}]

A287841(n) = if(1==n,n,1+A287841(omega(n))); \\ Antti Karttunen, Nov 23 2017

from sympy import primefactors
def a(n): return 1 if n==1 else a(len(primefactors(n))) + 1 # Indranil Ghosh, Jun 03 2017

a(n) = a(omega(n)) + 1 for n > 1, where omega() is the number of distinct prime factors.

cp's OEIS Frontend

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

A334196 a(1) = 0, then after the first differences of A003434.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

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