%I A000010 M0299 N0111
%S A000010 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,
%T A000010 12,28,8,30,16,20,16,24,12,36,18,24,16,40,12,42,20,24,22,46,16,
%U A000010 42,20,32,24,52,18,40,24,36,28,58,16,60,30,36,32,48,20,66,32,44
%N A000010 Euler totient function phi(n): count numbers <= n and prime to n.
%C A000010 Number of elements in a reduced residue system modulo n.
%C A000010 Degree of the n-th cyclotomic polynomial (cf. A013595). - Benoit Cloitre
(benoit7848c(AT)orange.fr), Oct 12 2002
%C A000010 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
%C A000010 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
%C A000010 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
%C A000010 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
%C A000010 Row sums of A127448. - Mats O. Granvik (mgranvik(AT)abo.fi), May 28 2008
%C A000010 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]
%C A000010 Number of automorphisms of the cyclic group of order n. [From Benoit
Jubin (benoit_jubin(AT)yahoo.fr), Aug 09 2008]
%C A000010 Equals row sums of triangle A143353. [From Gary W. Adamson (qntmpkt(AT)yahoo.com),
Aug 10 2008]
%D A000010 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 A000010 T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag,
1976, page 24.
%D A000010 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 193.
%D A000010 C. W. Curtis, Pioneers of Representation Theory ..., Amer. Math. Soc.,
1999; see p. 3.
%D A000010 S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 115-119.
%D A000010 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]
%D A000010 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 A000010 M. Lal and P. Gillard, Table of Euler's phi function, n < 10^5, Math.
Comp., 23 (1969), 682-683.
%D A000010 P. Ribenboim, The New Book of Prime Number Records.
%D A000010 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973
(includes this sequence).
%D A000010 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences,
Academic Press, 1995 (includes this sequence).
%H A000010 Daniel Forgues, <a href="b000010.txt">Table of n, phi(n) for n=1..100000</
a>
%H A000010 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Fxtbook</a>
%H A000010 M. Abramowitz and I. A. Stegun, eds., <a href="http://www.nrbook.com/
abramowitz_and_stegun/">Handbook of Mathematical Functions</a>, National
Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972
[alternative scanned copy].
%H A000010 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 A000010 F. Bayart, <a href="http://www.bibmath.net/dico/index.php3?action=affiche&quoi=./
i/indicateureuler.html">Indicateur d'Euler</a>
%H A000010 A. Bogomolny, <a href="http://www.cut-the-knot.org/blue/Euler.shtml">
Euler Function and Theorem</a>
%H A000010 C. K. Caldwell, The Prime Glossary, <a href="http://primes.utm.edu/glossary/
page.php?sort=EulersPhi">Euler's phi function</a>
%H A000010 K. Ford, <a href="http://arXiv.org/abs/math.NT/9907204">[math/9907204]
The number of solutions of phi(x)=m</a>
%H A000010 H. Fripertinger, <a href="http://www-ang.kfunigraz.ac.at/~fripert/fga/
k1euler.html">The Euler phi function</a>
%H A000010 Daniele A. Gewurz and Francesca Merola, <a href="http://www.cs.uwaterloo.ca/
journals/JIS/index.html">Sequences realized as Parker vectors ...</
a>, J. Integer Seqs., Vol. 6, 2003.
%H A000010 Mathforum, <a href="http://mathforum.org/library/drmath/view/51541.html">
Proving phi(m) Is Even</a>
%H A000010 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 A000010 Graeme McRae, <a href="http://2000clicks.com/MathHelp/NumberFactorsTotientFunction.htm">
Euler's Totient Function</a>
%H A000010 Primefan, <a href="http://primefan.tripod.com/Phi500.html">Euler's Totient
Function Values For n=1 to 500, with Divisor Lists</a>
%H A000010 Marko Riedel, <a href="http://www.geocities.com/markoriedelde/combnumth.html">
Combinatorics and number theory page.</a>
%H A000010 K. Schneider, PlanetMath.org, <a href="http://planetmath.org/encyclopedia/
EulerPhifunction.html">Euler phi-function</a>
%H A000010 W. Sierpinski, <a href="http://matwbn.icm.edu.pl/ksiazki/mon/mon42/mon4206.pdf">
Euler's Totient Function And The Theorem Of Euler</a>
%H A000010 U. Sondermann, <a href="http://home.earthlink.net/~usondermann/eulertot.html">
Euler's Totient Function</a>
%H A000010 W. A. Stein, <a href="http://modular.fas.harvard.edu/edu/Fall2001/124/
lectures/lecture6/html/node3.html">Phi is a Multiplicative Function</
a>
%H A000010 G. Villemin, <a href="http://villemin.gerard.free.fr/Wwwgvmm/Nombre/TotEuler.htm">
Totient d'Euler</a>
%H A000010 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 A000010 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
ModuloMultiplicationGroup.html">Link to a section of The World of
Mathematics.</a>
%H A000010 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
MoebiusTransform.html">Link to a section of The World of Mathematics.</
a>
%H A000010 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
TotientFunction.html">Link to a section of The World of Mathematics.</
a>
%H A000010 Wikipedia, <a href="http://www.wikipedia.org/wiki/Euler%27s_phi_function">
Euler's totient function</a>
%H A000010 Wolfram Research, <a href="http://functions.wolfram.com/NumberTheoryFunctions/
EulerPhi/03/02">First 50 values of phi(n)</a>
%H A000010 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 A000010 <a href="Sindx_Cor.html#core">Index entries for "core" sequences</a>
%F A000010 phi(n) = n*Product_{distinct primes p dividing n} (1-1/p).
%F A000010 Sum_{ d divides n } phi(d) = n.
%F A000010 phi(n) = Sum_{ d divides n } mu(d)*n/d, mu(d) = Moebius function A008683.
%F A000010 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 A000010 Multiplicative with a(p^e) = (p-1)*p^(e-1). - David W. Wilson (davidwwilson(AT)comcast.net),
Aug 01, 2001.
%F A000010 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
%F A000010 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
%F A000010 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.
%F A000010 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
%F A000010 Dirichlet generating function: zeta(s-1)/zeta(s). - Franklin T. Adams-Watters,
Sep 11 2005.
%F A000010 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
%F A000010 Equals A054525 * [1,2,3,...]; i.e. the Moebius transform of the natural
numbers. - Gary W. Adamson (qntmpkt(AT)yahoo.com), May 20 2007
%F A000010 Equals row sums of triangle A143276 [From Gary W. Adamson (qntmpkt(AT)yahoo.com),
Aug 03 2008]
%p A000010 with(numtheory): A000010 := phi; [ seq(phi(n), n=1..100) ]; # version
1
%p A000010 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 A000010 a[n_] := EulerPhi[n]
%o A000010 (AXIOM) [eulerPhi(n) for n in 1..100]
%o A000010 (MAGMA) [ EulerPhi(n) : n in [1..100] ]; - from Sergei Haller (sergei(AT)sergei-haller.de),
Dec 21 2006
%o A000010 (PARI) A000010(n)=eulerphi(n)
%o A000010 (SAGE program from Jaap Spies, Jan 7, 2007)
%o A000010 # euler_phi is a standard function in SAGE.
%o A000010 def A000010(n): return euler_phi(n)
%o A000010 def A000010_list(n): return [ euler_phi(i) for i in range(1,n+1)]
%o A000010 (PARI) { for (n=1, 100000, write("b000010.txt", n, " ", eulerphi(n)));
} [From Harry J. Smith (hjsmithh(AT)sbcglobal.net), Apr 26 2009]
%o A000010 (Other) sage: [euler_phi(n)for n in xrange(1,70)]# [From Zerinvary Lajos
(zerinvarylajos(AT)yahoo.com), Jun 06 2009]
%Y A000010 Cf. A008683, A003434, A007755, A049108, A002202 (values).
%Y A000010 For inverse see A002181, A006511, A058277.
%Y A000010 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 A000010 Cf. A054521, A023022, A054525, A134540.
%Y A000010 Row sums of triangle A134540.
%Y A000010 A143276 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Aug 03 2008]
%Y A000010 Equals right and left borders of triangle A159937. [From Gary W. Adamson
(qntmpkt(AT)yahoo.com), Apr 26 2009]
%Y A000010 Sequence in context: A011773 A080737 A152455 this_sequence A003978 A122645
A122646
%Y A000010 Adjacent sequences: A000007 A000008 A000009 this_sequence A000011 A000012
A000013
%K A000010 easy,core,nonn,mult,nice,new
%O A000010 1,3
%A A000010 N. J. A. Sloane (njas(AT)research.att.com).
%E A000010 Replaced a geocities.com URL - R. J. Mathar (mathar(AT)strw.leidenuniv.nl),
Oct 30 2009
|
