This site is supported by donations to The OEIS Foundation.



Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

(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)

%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 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 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 ...</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 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 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 (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)), A000010 (J_1), 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 Cf. A003558, A135303.

%Y Cf. A152455, A080737

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

%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 November 21 13:53 EST 2017. Contains 295001 sequences.