1,3

Number of elements in a reduced residue system modulo n.

Degree of the n-th cyclotomic polynomial (cf. A013595). - Benoit Cloitre (benoit7848c(AT)orange.fr), Oct 12 2002

Number of distinct generators of a cyclic group of order n. Number of primitive n-th roots of unity.(A primitive n-th root x is such that x^k is not equal to 1 for k=1, 2, ..., n-1, but x^n=1) - Lekraj Beedassy (blekraj(AT)yahoo.com), Mar 31 2005

Also number of complex Dirichlet characters modulo n and sum(k=1,n,a(k)) is asymptotic to (3/pi^2)*n^2. - S. R. Finch (Steven.Finch(AT)inria.fr), Feb 16 2006

a(n) is the highest degree of irreducible polynomial dividing 1 + x + x^2 + ... + x^(n-1) = (x^n - 1)/(x - 1). - Alexander Adamchuk (alex(AT)kolmogorov.com), Sep 02 2006, corrected Sep 27 2006

a(p) = p - 1 for prime p. a(n) is even for n>2. For n>2 a(n)/2 = A023022(n) = number of partitions of n into 2 ordered relatively prime parts. - Alexander Adamchuk (alex(AT)kolmogorov.com), Jan 25 2007

Row sums of A127448. - Mats O. Granvik (mgranvik(AT)abo.fi), May 28 2008

Equals row sums of triangle A143239 (a consequence of the Dedekind-Liouville rule, Cf. "Concrete Mathematics" p. 137). [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Aug 01 2008]

Number of automorphisms of the cyclic group of order n. [From Benoit Jubin (benoit_jubin(AT)yahoo.fr), Aug 09 2008]

Equals row sums of triangle A143353. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Aug 10 2008]

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.

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 24.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 193.

C. W. Curtis, Pioneers of Representation Theory ..., Amer. Math. Soc., 1999; see p. 3.

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 115-119.

Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Math., 2n-d ed.; Addison-Wesley, 1994, p. 137. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Aug 01 2008]

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, th. 60, 62, 63, 288, 323, 328, 330.

M. Lal and P. Gillard, Table of Euler's phi function, n < 10^5, Math. Comp., 23 (1969), 682-683.

P. Ribenboim, The New Book of Prime Number Records.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Daniel Forgues, Table of n, phi(n) for n=1..100000

Joerg Arndt, Fxtbook

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].

D. Alpern, Factorization using the Elliptic Curve Method(along with sigma_0, sigma_1 and phi functions)

F. Bayart, Indicateur d'Euler

A. Bogomolny, Euler Function and Theorem

C. K. Caldwell, The Prime Glossary, Euler's phi function

K. Ford, [math/9907204] The number of solutions of phi(x)=m

H. Fripertinger, The Euler phi function

Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors ..., J. Integer Seqs., Vol. 6, 2003.

Mathforum, Proving phi(m) Is Even

K. Matthews, Factorizing n and calculating phi(n),omega(n),d(n),sigma(n) and mu(n)

Graeme McRae, Euler's Totient Function

Primefan, Euler's Totient Function Values For n=1 to 500, with Divisor Lists

Marko Riedel, Combinatorics and number theory page.

K. Schneider, PlanetMath.org, Euler phi-function

W. Sierpinski, Euler's Totient Function And The Theorem Of Euler

U. Sondermann, Euler's Totient Function

W. A. Stein, Phi is a Multiplicative Function

G. Villemin, Totient d'Euler

A. de Vries, The prime factors of an integer (along with Euler's phi and Carmichael's lambda functions)

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Wikipedia, Euler's totient function

Wolfram Research, First 50 values of phi(n)

G. Xiao, Numerical Calculator, To display phi(n) operate on "eulerphi(n)"

Index entries for "core" sequences

phi(n) = n*Product_{distinct primes p dividing n} (1-1/p).

Sum_{ d divides n } phi(d) = n.

phi(n) = Sum_{ d divides n } mu(d)*n/d, mu(d) = Moebius function A008683.

Sum_{n >= 1} phi(n)/n^s = zeta(s-1)/zeta(s). Also Sum_{n >= 1} phi(n)*x^n/(1-x^n) = x/(1-x)^2.

Multiplicative with a(p^e) = (p-1)*p^(e-1). - David W. Wilson (davidwwilson(AT)comcast.net), Aug 01, 2001.

Sum_{n>=1} [phi(n)*ln(1-x^n)/n] = -x/(1-x) for -1<x<1 (cf. A002088) - Henry Bottomley (se16(AT)btinternet.com), Nov 16 2001

a(n)=binomial(n+1, 2) - sum{i=1, n-1, a(i)*floor(n/i)} (see A000217 for inverse) - Jon Perry (perry(AT)globalnet.co.uk), Mar 02 2004

Comment from Pieter Moree, Sep 10 2004: It is a classical result (certainly known to Landau, 1909) that lim inf n/phi(n)=1 (taking n to be primes), lim sup n/(phi(n) log log n)=e^{gamma}, with gamma = Euler's constant (taking n to be products of consecutive primes starting from 2 and applying Mertens' theorem). See e.g. Ribenboim, pp. 319-320.

a(n)=sum(i=1, n, | k(n, i) | ) where k(n, i) is the Kronecker symbol. Also a(n)=#{ 1<=i<=n : k(n, i)=0} where k(n, i) is the Kronecker symbol. - Benoit Cloitre (benoit7848c(AT)orange.fr), Aug 06 2004

Dirichlet generating function: zeta(s-1)/zeta(s). - Franklin T. Adams-Watters, Sep 11 2005.

Conjecture : limit Sum((-1)^i/(i * phi(i)) 2<=i<=Infinity) exists and is ca. 0.558. - Orges Leka (oleka(AT)students.uni-mainz.de), Dec 23 2004

Equals A054525 * [1,2,3,...]; i.e. the Moebius transform of the natural numbers. - Gary W. Adamson (qntmpkt(AT)yahoo.com), May 20 2007

Equals row sums of triangle A143276 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Aug 03 2008]

with(numtheory): A000010 := phi; [ seq(phi(n), n=1..100) ]; # version 1

with(numtheory): phi := proc(n) local i, t1, t2; t1 := ifactors(n)[2]; t2 := n*mul((1-1/t1[i][1]), i=1..nops(t1)); end; # version 2

a[n_] := EulerPhi[n]

(AXIOM) [eulerPhi(n) for n in 1..100]

(MAGMA) [ EulerPhi(n) : n in [1..100] ]; - from Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006

(PARI) A000010(n)=eulerphi(n)

(SAGE program from Jaap Spies, Jan 7, 2007)

# euler_phi is a standard function in SAGE.

def A000010(n): return euler_phi(n)

def A000010_list(n): return [ euler_phi(i) for i in range(1, n+1)]

(PARI) { for (n=1, 100000, write("b000010.txt", n, " ", eulerphi(n))); } [From Harry J. Smith (hjsmithh(AT)sbcglobal.net), Apr 26 2009]

(Other) sage: [euler_phi(n)for n in xrange(1, 70)]# [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 06 2009]

Cf. A008683, A003434, A007755, A049108, A002202 (values).

For inverse see A002181, A006511, A058277.

Jordan function J_k(n) is a generalization - see A059379 and A059380 (triangle of values of J_k(n)), A000010 (J_1), A059376 (J_3), A059377 (J_4), A059378 (J_5).

Cf. A054521, A023022, A054525, A134540.

Row sums of triangle A134540.

A143276 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Aug 03 2008]

Equals right and left borders of triangle A159937. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Apr 26 2009]

easy,core,nonn,mult,nice,new

N. J. A. Sloane (njas(AT)research.att.com).

Replaced a geocities.com URL - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Oct 30 2009