A049107 -id:A049107 - cp's OEIS frontend

A010554 a(n) = phi(phi(n)), where phi is the Euler totient function.

1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 4, 2, 4, 2, 4, 4, 8, 2, 6, 4, 4, 4, 10, 4, 8, 4, 6, 4, 12, 4, 8, 8, 8, 8, 8, 4, 12, 6, 8, 8, 16, 4, 12, 8, 8, 10, 22, 8, 12, 8, 16, 8, 24, 6, 16, 8, 12, 12, 28, 8, 16, 8, 12, 16, 16, 8, 20, 16, 20, 8, 24, 8

Offset: 1

N. J. A. Sloane

If n has a primitive root, then it has exactly phi(phi(n)) of them (Burton 1989, p. 188), which means that if p is a prime number, then there are exactly phi(p-1) incongruent primitive roots of p (Burton 1989). - Jonathan Vos Post, Sep 10 2010

See A046144 for the number of primitive roots mod n. - Wolfdieter Lang, Mar 09 2012

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 840.
Burton, D. M. "The Order of an Integer Modulo n," "Primitive Roots for Primes," and "Composite Numbers Having Primitive Roots." Sections 8.1-8.3 in Elementary Number Theory, 4th ed. Dubuque, IA: William C. Brown Publishers, pp. 184-205, 1989.

T. D. Noe, Table of n, a(n) for n = 1..10000
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
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 Erdos, 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]
S. R. Finch, Idempotents and Nilpotents Modulo n (arXiv:math.NT/0605019)
Boris Putievskiy, Transformations [Of] Integer Sequences And Pairing Functions, arXiv preprint arXiv:1212.2732 [math.CO], 2012.
Eric Weisstein's World of Mathematics, Primitive Root.

Cf. A000010, A049099, A049100, A049107, A077197.

a010554 = a000010 . a000010  -- Reinhard Zumkeller, Dec 26 2012

[EulerPhi(EulerPhi(n)): n in [1..100]]; // Vincenzo Librandi, Feb 24 2018

Maple
```
with(numtheory): f := n->phi(phi(n));
```

Table[EulerPhi[EulerPhi[n]],{n,0,200}] (* Vladimir Joseph Stephan Orlovsky, Nov 10 2009 *)
Nest[EulerPhi[#]&,Range[100],2] (* Harvey P. Dale, Jan 13 2024 *)

a(n)=eulerphi(eulerphi(n)) \\ Charles R Greathouse IV, Feb 06 2017

A053478 Sum of iterates when phi, A000010, is iterated until fixed point 1.

Original entry on oeis.org

1, 3, 6, 7, 12, 9, 16, 15, 18, 17, 28, 19, 32, 23, 30, 31, 48, 27, 46, 35, 40, 39, 62, 39, 60, 45, 54, 47, 76, 45, 76, 63, 68, 65, 74, 55, 92, 65, 78, 71, 112, 61, 104, 79, 84, 85, 132, 79, 110, 85, 114, 91, 144, 81, 126, 95, 112, 105, 164, 91, 152, 107, 118, 127, 144, 101

Offset: 1

Labos Elemer, Jan 14 2000

nonn

For n = 2^w, the sum is 2^(w+1) - 1.

			If phi is applied repeatedly to n = 91, the iterates {91, 72, 24, 8, 4, 2, 1} are obtained. Their sum is a(91) = 91 + 72 + 24 + 8 + 4 + 2 + 1 = 202.

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A000010, A010554, A049099, A049100, A049107, A049108, A032358.

Row sums of A375478.

a053478 = (+ 1) . sum . takeWhile (/= 1) . iterate a000010
-- Reinhard Zumkeller, Oct 27 2011

f[n_] := Plus @@ Drop[ FixedPointList[ EulerPhi, n], -1]; Table[ f[n], {n, 66}] (* Robert G. Wilson v, Dec 16 2004 *)
f[1] := 1; f[n_] := n + f[EulerPhi[n]]; Table[f[n], {n, 66}] (* Carlos Eduardo Olivieri, May 26 2015 *)

a(n)=my(s=n);while(n>1,s+=n=eulerphi(n)); s \\ Charles R Greathouse IV, Feb 21 2013

a(n) = n + a(phi(n)).

a(n) = A092693(n) + n. - Vladeta Jovovic, Jul 02 2004

A049099 a(n) = Euler phi function applied thrice to n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 2, 4, 1, 2, 2, 2, 2, 4, 2, 4, 2, 2, 2, 4, 2, 4, 4, 4, 4, 4, 2, 4, 2, 4, 4, 8, 2, 4, 4, 4, 4, 10, 4, 4, 4, 8, 4, 8, 2, 8, 4, 4, 4, 12, 4, 8, 4, 4, 8, 8, 4, 8, 8, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 8, 6, 8, 16, 4, 16, 4, 8, 8, 16, 4, 8, 8, 8, 10, 8, 8, 16, 4, 8, 8, 16

Offset: 1

Labos Elemer

nonn

			n=163: the successive iterates of Euler totient function are 163,162,54,18,6,2,1. The 4th term is 18, when Phi was applied 3 times. So a(163)=18.

Antti Karttunen, Table of n, a(n) for n = 1..10000
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 Erdos, 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]
Boris Putievskiy, Transformations [Of] Integer Sequences And Pairing Functions, arXiv preprint arXiv:1212.2732 [math.CO], 2012.

Cf. A000010, A010554, A049100, A049107, A049115.

Mathematica
```
a(n)=Nest[ EulerPhi, n, 3 ]
```

A049099(n) = eulerphi(eulerphi(eulerphi(n))); \\ Antti Karttunen, Aug 22 2017

a(n) = A000010(A010554(n)) = A000010(A000010(A000010(n))). - Antti Karttunen, Aug 22 2017

A049100 a(n) = Euler phi function applied 4 times to n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 1, 2, 1, 2, 2, 4, 1, 2, 2, 2, 2, 4, 2, 2, 2, 4, 2, 4, 1, 4, 2, 2, 2, 4, 2, 4, 2, 2, 4, 4, 2, 4, 4, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 4, 2, 4, 8, 2, 8, 2, 4, 4, 8, 2, 4, 4, 4, 4, 4, 4, 8, 2, 4, 4, 8, 4, 8, 4, 4

Offset: 1

Labos Elemer

nonn

			n=163, the successive iterates applying Euler totient function are as follows: 163,162,54,18,6,2,1. The 5th term is 6, when Phi was applied 4 times. So a(163)=6.

Antti Karttunen, Table of n, a(n) for n = 1..10000
Boris Putievskiy, Transformations [Of] Integer Sequences And Pairing Functions, arXiv preprint arXiv:1212.2732 [math.CO], 2012.

Cf. A000010, A010554, A049099, A049107, A049115.

with(numtheory): seq(phi(phi(phi(phi(n)))),n=1..130); # Emeric Deutsch, May 14 2006

Mathematica
```
a(n)=Nest[ EulerPhi, n, 4 ]
```

A049100(n) = eulerphi(eulerphi(eulerphi(eulerphi(n)))); \\ Antti Karttunen, Aug 22 2017

a(n) = phi(phi(phi(phi(n)))) = A000010(A000010(A000010(A000010(n)))) = A010554(A010554(n)) = A000010(A049099(n)).

Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Jun 23 2007

A053473 a(n) is the cototient of n (A051953) iterated 5 times.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 2, 0, 2, 0, 2, 0, 2, 0, 4, 0, 2, 0, 2, 0, 2, 0, 4, 0, 2, 0, 4, 0, 2, 0, 4, 0, 4, 0, 2, 0, 2, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 8, 0, 4, 0, 8, 0, 8, 0, 4, 0, 4, 0, 8, 0, 4, 0, 4, 0, 4, 0, 4, 0, 8, 0, 8, 0, 4, 1

Offset: 1

Labos Elemer, Jan 14 2000

nonn

As iteration of A051953 progresses, more and more powers of 2 and 0 appear. The fixed point is 0. Analogous 5th iterates for A000005 or A000010 are A036453 and A049107.

It is assumed here that the value of A051953 at 0 is 0. - Antti Karttunen, Dec 22 2017

			n=50, n_1 = n - phi(n) = 50 - 20 = 30, n_2 = n_1 - Phi(n_1) = 30 - 8 = 22, n_3 = 22 - Phi(22) = 12, n_4 = n_3 - Phi(n_3) = 12 - 4 = 8, n_5 = 8 - Phi(8) = 4 so the 50th term is 4.

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

Cf. A051953, A000005, A000010, A036453, A049107.

Cf. A053470, A053471, A053472.

a[n_] := Nest[# - EulerPhi[#]&, n, 5];
Array[a, 105] (* Jean-François Alcover, Dec 26 2017 *)

A051953(n) = if(!n,n,(n-eulerphi(n))); \\ With modification that returns zero for zero.
A053473(n) = A051953(A051953(A051953(A051953(A051953(n))))); \\ Antti Karttunen, Dec 22 2017

A068582 Let phi_m(x) = phi(phi(...(phi(x))...)) m times; sequence gives values of k such that phi_5(k) = tau(k).

Original entry on oeis.org

1, 41, 47, 53, 59, 61, 67, 71, 73, 79, 85, 109, 115, 119, 123, 125, 127, 141, 143, 145, 155, 159, 161, 163, 166, 177, 178, 183, 185, 194, 201, 202, 203, 206, 209, 213, 214, 215, 217, 219, 226, 237, 247, 255, 259, 262, 278, 298, 301, 302, 314, 327, 328, 343

Offset: 1

Benoit Cloitre, Mar 26 2002

Last term is a(340) = 24570.

Numbers k such that A049107(k) = A000005(k).

Jinyuan Wang, Table of n, a(n) for n = 1..340

Cf. A000005, A000010, A049107, A068579, A068580, A068581.

Select[Range[343], Nest[EulerPhi, #, 5] === DivisorSigma[0, #] &] (* Amiram Eldar, Jun 12 2022 *)

A162964 a(n) = sigma(sigma(sigma(sigma(sigma(n))))).

Original entry on oeis.org

1, 15, 24, 60, 120, 360, 168, 480, 168, 360, 360, 1170, 480, 1512, 1512, 210, 360, 1170, 728, 1680, 576, 480, 1512, 4800, 210, 1680, 1344, 3276, 992, 2016, 576, 1651, 1560, 3276, 1560, 1512, 1512, 4800, 3276, 4064, 1680, 5952, 1560, 5040, 4800, 2016, 1560, 5040

Offset: 1

Jaroslav Krizek, Jul 19 2009

nonn

Antti Karttunen, Table of n, a(n) for n = 1..16384
Index entries for sequences related to sigma(n)

Cf. A000203, A129076, A066971, A051027.

Cf. also A049107.

with(numtheory); f:=n->sigma(sigma(sigma(sigma(sigma(n))))); [seq(f(n),n=1..100)];

Table[Nest[DivisorSigma[1,#]&,n,5],{n,50}] (* Harvey P. Dale, Apr 19 2013 *)

A162964(n) = sigma(sigma(sigma(sigma(sigma(n))))); \\ Antti Karttunen, Nov 18 2017

a(n) = A000203(A000203(A000203(A000203(A000203(n))))).

More terms from N. J. A. Sloane, Mar 20 2010

cp's OEIS Frontend

A010554 a(n) = phi(phi(n)), where phi is the Euler totient function.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

A053478 Sum of iterates when phi, A000010, is iterated until fixed point 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A049099 a(n) = Euler phi function applied thrice to n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A049100 a(n) = Euler phi function applied 4 times to n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A053473 a(n) is the cototient of n (A051953) iterated 5 times.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A068582 Let phi_m(x) = phi(phi(...(phi(x))...)) m times; sequence gives values of k such that phi_5(k) = tau(k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A162964 a(n) = sigma(sigma(sigma(sigma(sigma(n))))).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple