This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000010 Euler totient function phi(n): count numbers <= n and prime to n.
(Formerly M0299 N0111)

%I M0299 N0111

%S 1,1,2,2,4,2,6,4,6,4,10,4,12,6,8,8,16,6,18,8,12,10,22,8,20,12,18,12,

%T 28,8,30,16,20,16,24,12,36,18,24,16,40,12,42,20,24,22,46,16,42,20,32,

%U 24,52,18,40,24,36,28,58,16,60,30,36,32,48,20,66,32,44

%N Euler totient function phi(n): count numbers <= n and prime to n.

%C Number of elements in a reduced residue system modulo n.

%C Degree of the n-th cyclotomic polynomial (cf. A013595). - _Benoit Cloitre_, Oct 12 2002

%C 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_, Mar 31 2005

%C Also number of complex Dirichlet characters modulo n; sum(k = 1, n, a(k)) is asymptotic to (3/Pi^2)*n^2. - _Steven Finch_, Feb 16 2006

%C a(n) is the highest degree of irreducible polynomial dividing 1 + x + x^2 + ... + x^(n-1) = (x^n - 1)/(x - 1). - _Alexander Adamchuk_, Sep 02 2006, corrected Sep 27 2006

%C 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_, Jan 25 2007

%C Number of automorphisms of the cyclic group of order n. - _Benoit Jubin_, Aug 09 2008

%C a(n+2) equals the number of palindromic Sturmian words of length n which are 'bispecial', prefix or suffix of two Sturmian words of length n + 1. - _Fred Lunnon_, Sep 05 2010

%C Suppose that a and n are coprime positive integers, then by Euler's totient theorem, any factor of n divides a^phi(n) - 1. - _Lei Zhou_, Feb 28 2012

%C a(n) = A096396(n) + A096397(n). - _Reinhard Zumkeller_, Mar 24 2012

%C If m has k prime factors,(f1, f2, ..., fk), then phi(m*n) = phi(f1*n) * phi(f2*n) * ... * phi(fk*n)/phi(n)^(k-1). For example, phi(42*n) = phi(2*n) * phi(3*n) * phi(7*n)/phi(n)^2. - _Gary Detlefs_, Apr 21 2012

%C sum(n>=1, a(n)/n! ) = 1.954085357876006213144... This sum is referenced in Plouffe's inverter. - _Alexander R. Povolotsky_, Feb 02 2013

%C The order of the multiplicative group of units modulo n. - _Michael Somos_, Aug 27 2013

%C A strong divisibility sequence, that is, gcd(a(n), a(m)) = a(gcd(n, m)) for all positive integers n and m. - _Michael Somos_, Dec 30 2016

%C From _Eric Desbiaux_, Jan 01 2017: (Start)

%C a(n) equals the Ramanujan sum C_n(n) (last term on n-th row of triangle A054533).

%C a(n) equals the Jordan function J_1(n) (cf. A007434, A059376, A059377, which are the Jordan functions J_2, J_3, J_4, respectively). (End)

%D 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.

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

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

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

%D L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923, see vol. 1, Chapter V.

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

%D Carl Friedrich Gauss, "Disquitiones Arithmeticae", Yale University Press, 1965; see p. 21.

%D Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Math., 2n-d ed.; Addison-Wesley, 1994, p. 137.

%D 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.

%D Peter Hilton and Jean Pedersen, A Mathematical Tapestry, Demonstrating the Beautiful Unity of Mathematics, Cambridge University Press, (pages 261-264, the Coach theorem)

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

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

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

%H N. J. A. Sloane and Daniel Forgues, <a href="/A000010/b000010.txt">Table of n, phi(n) for n=1..100000</a> (first 10000 terms from N. J. A. Sloane)

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 39.7, pp. 776-778

%H M. Abramowitz and I. A. Stegun, eds., <a href="http://apps.nrbook.com/abramowitz_and_stegun/index.html">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

%H D. Alpern, <a href="http://www.alpertron.com.ar/ECM.HTM">Factorization using the Elliptic Curve Method(along with sigma_0, sigma_1 and phi functions)</a>

%H F. Bayart, <a href="http://www.bibmath.net/dico/index.php3?action=affiche&amp;quoi=./i/indicateureuler.html">Indicateur d'Euler</a>

%H A. Bogomolny, <a href="http://www.cut-the-knot.org/blue/Euler.shtml">Euler Function and Theorem</a>

%H C. K. Caldwell, The Prime Glossary, <a href="http://primes.utm.edu/glossary/page.php?sort=EulersPhi">Euler's phi function</a>

%H R. D. Carmichael, <a href="/A002180/a002180.pdf">A table of the values of m corresponding to given values of phi(m)</a>, Amer. J. Math., 30 (1908),394-400. [Annotated scanned copy]

%H K. Ford, <a href="http://arXiv.org/abs/math.NT/9907204">The number of solutions of phi(x)=m</a>, arXiv:math/9907204 [math.NT], 1999.

%H Kevin Ford, Florian Luca and Pieter Moree, <a href="http://arxiv.org/abs/1108.3805">Values of the Euler phi-function not divisible by a given odd prime, and the distribution of Euler-Kronecker constants for cyclotomic fields</a>, arXiv:1108.3805 [math.NT], 2011.

%H H. Fripertinger, <a href="http://www-ang.kfunigraz.ac.at/~fripert/fga/k1euler.html">The Euler phi function</a>

%H Daniele A. Gewurz and Francesca Merola, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Gewurz/gewurz5.html">Sequences realized as Parker vectors ...</a>, J. Integer Seqs., Vol. 6, 2003.

%H E. Pérez Herrero, <a href="http://psychedelic-geometry.blogspot.com/2010/07/totient-carnival.html">Totient Carnival partitions</a>, Psychedelic Geometry Blogspot

%H M. Lal and P. Gillard, <a href="http://dx.doi.org/10.1090/S0025-5718-69-99858-5">Table of Euler's phi function, n < 10^5</a>, Math. Comp., 23 (1969), 682-683.

%H D. N. Lehmer, <a href="http://projecteuclid.org/euclid.bams/1183425137">Review of Dickson's History of the Theory of Numbers</a>, Bull. Amer. Math. Soc., 26 (1919), 125-132.

%H Mathforum, <a href="http://mathforum.org/library/drmath/view/51541.html">Proving phi(m) Is Even</a>

%H K. Matthews, <a href="http://www.numbertheory.org/php/factor.html">Factorizing n and calculating phi(n),omega(n),d(n),sigma(n) and mu(n)</a>

%H Graeme McRae, <a href="http://2000clicks.com/MathHelp/NumberFactorsTotientFunction.aspx">Euler's Totient Function</a>

%H Carl Pomerance and Hee-Sung Yang, <a href="http://www.math.dartmouth.edu/~carlp/uupaper7.pdf">Variant of a theorem of Erdos on the sum-of-proper-divisors function</a>, Math. Comp., to appear (2014).

%H Primefan, <a href="http://primefan.tripod.com/Phi500.html">Euler's Totient Function Values For n=1 to 500, with Divisor Lists</a>

%H Marko Riedel, <a href="http://www.mathematik.uni-stuttgart.de/~riedelmo/combnumth.html">Combinatorics and number theory page.</a>

%H K. Schneider, PlanetMath.org, <a href="http://planetmath.org/encyclopedia/EulerPhifunction.html">Euler phi-function</a>

%H W. Sierpiński, <a href="http://matwbn.icm.edu.pl/ksiazki/mon/mon42/mon4206.pdf">Euler's Totient Function And The Theorem Of Euler</a>

%H U. Sondermann, <a href="http://home.earthlink.net/~usondermann/eulertot.html">Euler's Totient Function</a>

%H W. A. Stein, <a href="http://modular.math.washington.edu/edu/Fall2001/124/lectures/lecture6/html/node3.html">Phi is a Multiplicative Function</a>

%H G. Villemin, <a href="http://villemin.gerard.free.fr/Wwwgvmm/Nombre/TotEuler.htm">Totient d'Euler</a>

%H A. de Vries, <a href="http://math-it.org/Mathematik/Zahlentheorie/Zahl/ZahlApplet.html">The prime factors of an integer (along with Euler's phi and Carmichael's lambda functions)</a>

%H K. W. Wegner, <a href="/A002180/a002180_1.pdf">Values of phi(x) = n for n from 2 through 1978</a>, mimeographed manuscript, no date [Annotated scanned copy]

%H Eric W. Weisstein, <a href="http://mathworld.wolfram.com/ModuloMultiplicationGroup.html">MathWorld: Modulo Multiplication Group</a>

%H Eric W. Weisstein, <a href="http://mathworld.wolfram.com/MoebiusTransform.html">MathWorld: Moebius Transform</a>

%H Eric W. Weisstein, <a href="http://mathworld.wolfram.com/TotientFunction.html">MathWorld: Totient Function</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Euler%27s_phi_function">Euler's totient function</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n">Multiplicative group of integers modulo n</a>

%H Wolfram Research, <a href="http://functions.wolfram.com/NumberTheoryFunctions/EulerPhi/03/02">First 50 values of phi(n)</a>

%H G. Xiao, Numerical Calculator, <a href="http://wims.unice.fr/wims/en_tool~number~calcnum.en.html">To display phi(n) operate on "eulerphi(n)"</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%H <a href="/index/Di#divseq">Index to divisibility sequences</a>

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

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

%F phi(n) = Sum_{ d divides n } mu(d)*n/d, i.e., the Moebius transform of the natural numbers; mu() = Moebius function A008683().

%F Dirichlet generating function 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.

%F Multiplicative with a(p^e) = (p-1)*p^(e-1). - _David W. Wilson_, Aug 01 2001

%F Sum_{n >= 1} [phi(n)*log(1-x^n)/n] = -x/(1-x) for -1 < x < 1 (cf. A002088) - _Henry Bottomley_, Nov 16 2001

%F a(n) = binomial(n+1, 2) - sum{i = 1, n - 1, a(i)*floor(n/i)} (see A000217 for inverse) - _Jon Perry_, Mar 02 2004

%F 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. - Pieter Moree, Sep 10 2004

%F 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 }. - _Benoit Cloitre_, Aug 06 2004

%F Conjecture: limit Sum_{i>=2} (-1)^i/(i * phi(i)) exists and is approximately 0.558. - Orges Leka (oleka(AT)students.uni-mainz.de), Dec 23 2004

%F From _Enrique Pérez Herrero_, Sep 07 2010: (Start)

%F a(n) = Sum_{i = 1..n}{floor(sigma_k(i*n)/sigma_k(i)*sigma_k(n))}, where sigma_2 is A001157.

%F a(n) = Sum_{i = 1..n}{floor(tau_k(i*n)/tau_k(i)*tau_k(n))}, where tau_3 is A007425.

%F a(n) = Sum_{i = 1..n}{floor(rad(i*n)/rad(i)*rad(n))}, where rad is A007947 (End)

%F a(n) = A173557(n) * A003557(n). - _R. J. Mathar_, Mar 30 2011

%F phi(p*n) = phi(n)*[floor(((n+p-1) mod p)/(p-1))+p-1], for prime p. - _Gary Detlefs_, Apr 21 2012

%F a(n), n odd = 2 * A135303((n-1)/2) * A003558((n-1)/2) or phi(n) = 2 * c * k; the Coach theorem of Pedersen et al. Cf. A135303. - _Gary W. Adamson_, Aug 15 2012

%F G.f.: Sum_{n>=1} mu(n)*x^n/(1-x^n)^2, where mu(n) = A008683(n). - _Mamuka Jibladze_, Apr 05 2015

%F a(n) = n - cototient(n) = n - A051953(n). - _Omar E. Pol_, May 14 2016

%F a(n) = lim_{s->1} n*zeta(s)*(Sum_{d divides n} A008683(d)/(e^(1/d))^(s-1)), for n > 1. - _Mats Granvik_, Jan 26 2017

%F Conjecture: a(n) = Sum_{a = 1..n} Sum_{b = 1..n} Sum_{c = 1..n} 1 for n > 1. The sum is over a,b,c such that n*c - a*b = 1. - _Benedict W. J. Irwin_, Apr 03 2017

%e G.f. = x + x^2 + 2*x^3 + 2*x^4 + 4*x^5 + 2*x^6 + 6*x^7 + 4*x^8 + 6*x^9 + 4*x^10 + ...

%e a(8) = 4 with {1, 3, 5, 7} units modulo 8. a(10) = 4 with {1, 3, 7, 9} units modulo 10. - _Michael Somos_, Aug 27 2013

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

%p 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

%t Array[EulerPhi, 70]

%o (Axiom) [eulerPhi(n) for n in 1..100]

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

%o (PARI) {a(n) = if( n==0, 0, eulerphi(n))}; /* _Michael Somos_, Feb 05 2011 */

%o (Sage)

%o # euler_phi is a standard function in Sage.

%o def A000010(n): return euler_phi(n)

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

%o # Jaap Spies, Jan 07 2007

%o (PARI) { for (n=1, 100000, write("b000010.txt", n, " ", eulerphi(n))); } \\ _Harry J. Smith_, Apr 26 2009

%o (Sage) [euler_phi(n)for n in xrange(1,70)] # _Zerinvary Lajos_, Jun 06 2009

%o (Maxima) makelist(totient(n),n,0,1000); /* _Emanuele Munarini_, Mar 26 2011 */

%o (Haskell) a n = length (filter (==1) (map (gcd n) [1..n])) -- _Allan C. Wechsler_, Dec 29 2014

%o (Python)

%o from sympy.ntheory import totient

%o print[totient(i) for i in xrange(1, 101)] # _Indranil Ghosh_, Mar 17 2017

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

%Y Cf. A005277 (nontotient numbers). For inverse see A002181, A006511, A058277.

%Y 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).

%Y Cf. A054521, A023022, A054525, A134540.

%Y Row sums of triangle A134540.

%Y Equals right and left borders of triangle A159937. - _Gary W. Adamson_, Apr 26 2009

%Y Row sums of A127448. - _Mats Granvik_, May 28 2008

%Y Equals row sums of triangle A143239 (a consequence of the Dedekind-Liouville rule, see Concrete Mathematics p. 137). - _Gary W. Adamson_, Aug 01 2008

%Y Equals row sums of triangle A143353 and of A143276.

%Y Cf. A003558, A135303.

%K easy,core,nonn,mult,nice,hear

%O 1,3

%A _N. J. A. Sloane_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified April 25 00:46 EDT 2017. Contains 285346 sequences.