A049099 -id:A049099 - 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

A049107 a(n) = Euler phi function applied 5 times to n.

Original entry on oeis.org

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

Offset: 1

Labos Elemer

nonn

			For n = 163, the successive iterates applying Euler totient function are as follows: 163, 162, 54, 18, 6, 2, 1. The 6th term is 2, when Phi was applied 5 times. So a(163)=2, already a power of 2.
For n = 487, the successive iterates are 486, 162, 54, 18, 6, 2, 1. On the fifth iteration we reach 6, thus a(487) = 6. This is also the first term of A049107 that is not a power of 2. - _Antti Karttunen_, Aug 22 2017

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

Cf. A000010, A010554, A049099, A049100, A049115.

a(n)=Nest[ EulerPhi, n, 5 ]
Nest[EulerPhi,Range[110],5] (* Harvey P. Dale, May 19 2019 *)

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

a(n) = A000010(A049100(n)) = A010554(A049099(n)) = phi(phi(phi(phi(phi(n))))), where phi = A000010. - Antti Karttunen, Aug 22 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

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

A053471 a(n) is the cototient of n (A051953) iterated 3 times.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 1, 0, 2, 0, 2, 0, 2, 0, 2, 0, 4, 0, 4, 1, 4, 0, 4, 0, 4, 1, 4, 0, 8, 0, 4, 0, 8, 0, 8, 0, 8, 1, 8, 0, 12, 0, 8, 3, 8, 0, 8, 0, 12, 0, 8, 0, 16, 1, 8, 3, 12, 0, 16, 0, 8, 3, 8, 0, 16, 0, 16, 1, 16, 0, 16, 0, 12, 1, 16, 0, 24, 0, 16, 3, 22, 0, 24, 3, 16, 0, 16, 0, 24, 0, 16, 1, 16, 0

Offset: 1

Labos Elemer, Jan 14 2000

nonn

Iteration of A051953 behaves similarly to that of Euler Phi. Analogous 3rd iterates for A000005 or A000010 are A036455 and A049099.

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 so the 50th term is 12.

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

Cf. A051953, A000005, A000010, A036455, A049099.

Cf. A053470, A053472, A053473.

Array[Nest[# - EulerPhi@ # &, #, 3] &, 95] (* Michael De Vlieger, Dec 23 2017 *)

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

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

Original entry on oeis.org

1, 11, 13, 19, 33, 34, 35, 39, 46, 57, 58, 62, 74, 86, 88, 102, 104, 105, 110, 130, 135, 138, 152, 154, 174, 182, 186, 190, 222, 258, 264, 280, 312, 330, 342, 390, 456, 462, 546, 570, 594, 756, 840, 1080

Offset: 1

Benoit Cloitre, Mar 26 2002

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

Cf. A000005, A000010, A049099, A068580, A068581, A068582.

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

is(k) = numdiv(k) == eulerphi(eulerphi(eulerphi(k))); \\ Jinyuan Wang, Apr 05 2020

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

A049107 a(n) = Euler phi function applied 5 times to n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A053471 a(n) is the cototient of n (A051953) iterated 3 times.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI