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, (p_1, p_2, ..., p_k), then phi(m*n) = (Product_{i=1..k} phi (p_i*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)

%C For n>1, a(n) appears to be equal to the number of semi-meander solutions for n with top arches containing exactly 2 mountain ranges and exactly 2 arches of length 1. - _Roger Ford_, Oct 11 2017

%C a(n) is the minimum dimension of a lattice able to generate, via cut-and-project, the quasilattice whose diffraction pattern features n-fold rotational symmetry. The case n=15 is the first n > 1 in which the following simpler definition fails: "a(n) is the minimum dimension of a lattice with n-fold rotational symmetry". - _Felix Flicker_, Nov 08 2017

%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 M. Baake and U. Grimm, Aperiodic Order Vol. 1: A Mathematical Invitation, Encyclopedia of Mathematics and its Applications 149, Cambridge University Press, 2013: see Tables 3.1 and 3.2

%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 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 M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards Applied Math.Series 55, Tenth Printing, 1972.

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

%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 Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, <a href="http://math.dartmouth.edu/~carlp/iterate.pdf">On the normal behavior of the iterates of some arithmetic functions</a>, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.

%H Paul Erdos, Andrew Granville, Carl Pomerance and Claudia Spiro, <a href="/A000010/a000010_1.pdf">On the normal behavior of the iterates of some arithmetic functions</a>, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]

%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 of oligomorphic permutation groups</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 Peter Luschny, <a href="http://oeis.org/wiki/User:Peter_Luschny/EulerTotient">Sequences related to Euler's totient function</a>

%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 Matthew Parker, <a href="https://oeis.org/A000010/a000010_5M.7z">The first 5 million terms (7-Zip compressed file)</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 Pinthira Tangsupphathawat, Takao Komatsu, Vichian Laohakosol, <a href="https://www.emis.de/journals/JIS/VOL21/Laohakosol/lao8.html">Minimal Polynomials of Algebraic Cosine Values, II</a>, J. Int. Seq., Vol. 21 (2018), Article 18.9.5.

%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 Wikipedia, <a href="http://en.wikipedia.org/wiki/Ramanujan&#39;s_sum">Ramanujan's sum</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) = n - #{1 <= i <= n : k(n, i) = 0}. - _Benoit Cloitre_, Aug 06 2004 [Corrected by _Jianing Song_, Sep 25 2018]

%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 primes p. - _Gary Detlefs_, Apr 21 2012

%F For odd n, a(n) = 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

%F a(n) = Sum_{j=1..n} gcd(j, n) cos(2*Pi*j/n) = Sum_{j=1..n} gcd(j, n) exp(2*Pi*i*j/n) where i is the imaginary unit. Notice that the Ramanujan's sum c_n(k) := Sum_{j=1..n, gcd(j, n) = 1} exp(2*Pi*i*j*k/n) gives a(n) = Sum_{k|n} k*c_(n/k)(1) = Sum_{k|n} k*mu(n/k). - _Michael Somos_, May 13 2018

%F G.f.: x*d/dx(x*d/dx(log(Product_{k>=1} (1 - x^k)^(-mu(k)/k^2)))), where mu(n) = A008683(n). - _Mamuka Jibladze_, Sep 20 2018

%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 (steps to reach 1), 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)), this sequence (J_1), A007434 (J_2), A059376 (J_3), A059377 (J_4), A059378 (J_5).

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

%Y Row sums of triangles A134540, A127448, A143239, A143353 and A143276.

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

%Y Values for prime powers p^e: A006093 (e=1), A036689 (e=2), A135177 (e=3), A138403 (e=4), A138407 (e=5), A138412 (e=6).

%Y Values for perfect powers n^e: A002618 (e=2), A053191 (e=3), A189393 (e=4), A238533 (e=5), A239442 (e=7), A239443 (e=9).

%Y Cf. A003558, A135303.

%Y Cf. A152455, A080737.

%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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 21 04:59 EDT 2019. Contains 321364 sequences. (Running on oeis4.)