|
| |
|
|
A000010
|
|
Euler totient function phi(n): count numbers <= n and prime to n.
(Formerly M0299 N0111)
|
|
1527
|
|
|
|
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, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52, 18, 40, 24, 36, 28, 58, 16, 60, 30, 36, 32, 48, 20, 66, 32, 44
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
Number of elements in a reduced residue system modulo n.
Degree of the n-th cyclotomic polynomial (cf. A013595). - Benoit Cloitre, 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, Mar 31 2005
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
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
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
Number of automorphisms of the cyclic group of order n. [From Benoit Jubin, Aug 09 2008]
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. [From Fred Lunnon (Fred.Lunnon(AT)may.ie), Sep 05 2010]
Suppose that a and n are coprime positive integers, then by Euler's totient theorem, any factor of n divides a^phi(n)-1. [From Lei Zhou, Feb 28 2012]
a(n) = A096396(n) + A096397(n). [Reinhard Zumkeller, Mar 24 2012]
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.
sum(n>=1, a(n)/n!) is a convergent series. The sum is approximately 1.95408535787600621314459486. This sum is referenced in Plouffe's inverter. - Alexander R. Povolotsky, Feb 02 2013
|
|
|
REFERENCES
|
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.
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.
S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 115-119.
Carl Friedrich Gauss, "Disquitiones Arithmeticae", Yale University Press, 1965; see p. 21.
Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Math., 2n-d ed.; Addison-Wesley, 1994, p. 137.
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.
Peter Hilton and Jean Pedersen, A Mathematical Tapestry, Demonstrating the Beautiful Unity of Mathematics, Cambridge University Press, (pages 261-264, the Coach theorem)
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).
|
|
|
LINKS
|
N. J. A. Sloane and Daniel Forgues, Table of n, phi(n) for n=1..100000 (first 10000 terms from N. J. A. Sloane)
Joerg Arndt, Fxtbook, section 39.7, pp. 776-778
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
Kevin Ford, Florian Luca and Pieter Moree, Values of the Euler phi-function not divisible by a given odd prime, and the distribution of Euler-Kronecker constants for cyclotomic fields, arXiv:1108.3805, 2011
H. Fripertinger, The Euler phi function
Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors ..., J. Integer Seqs., Vol. 6, 2003.
E. Pérez Herrero, Totient Carnival partitions, Psychedelic Geometry Blogspot, 11,Jul,2010 [From Enrique Pérez Herrero, Sep 07 2010]
D. N. Lehmer, Review of Dickson's History of the Theory of Numbers, Bull. Amer. Math. Soc., 26 (1919), 125-132.
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 W. Weisstein, MathWorld: Modulo Multiplication Group
Eric W. Weisstein, MathWorld: Moebius Transform
Eric W. Weisstein, MathWorld: Totient Function
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
Index to divisibility sequences
|
|
|
FORMULA
|
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, i.e., the Moebius transform of the natural numbers; mu() = Moebius function A008683().
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.
Multiplicative with a(p^e) = (p-1)*p^(e-1). - David W. Wilson, Aug 01 2001.
Sum_{n>=1} [phi(n)*ln(1-x^n)/n] = -x/(1-x) for -1<x<1 (cf. A002088) - Henry Bottomley, 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, 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, Aug 06 2004
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
Contribution from Enrique Pérez Herrero, Sep 07 2010: (Start)
a(n)=sum_{i=1}^{n}{floor(sigma_k(i*n)/sigma_k(i)*sigma_k(n))}, where sigma_2 is A001157
a(n)=sum_{i=1}^{n}{floor(tau_k(i*n)/tau_k(i)*tau_k(n))}, where tau_3 is A007425
a(n)=sum_{i=1}^{n}{floor(rad(i*n)/rad(i)*rad(n))}, where rad is A007947 (End)
a(n) = A173557(n) * A003557(n). - R. J. Mathar, Mar 30 2011
phi(p*n)= phi(n)*[floor(((n+p-1) mod p)/(p-1))+p-1], for prime p. - Gary Detlefs, Apr 21 2012
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.
|
|
|
MAPLE
|
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
|
|
|
MATHEMATICA
|
f[n_] := EulerPhi@ n; Array[f, 70]
|
|
|
PROG
|
(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) {a(n) = if( n==0, 0, eulerphi(n))} /* Michael Somos Feb 05 2011 */
(Sage)
# 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)]
# Jaap Spies, Jan 07 2007
(PARI) { for (n=1, 100000, write("b000010.txt", n, " ", eulerphi(n))); } [From Harry J. Smith, Apr 26 2009]
(Sage) [euler_phi(n)for n in xrange(1, 70)]# [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 06 2009]
(Maxima) makelist(totient(n), n, 0, 1000); [Emanuele Munarini, Mar 26 2011]
|
|
|
CROSSREFS
|
Cf. A008683, A003434, A007755, A049108, A002202 (values).
Cf. A005277 (nontotient numbers). 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.
Equals right and left borders of triangle A159937. [From Gary W. Adamson, Apr 26 2009]
Row sums of A127448. - Mats Granvik, May 28 2008
Equals row sums of triangle A143239 (a consequence of the Dedekind-Liouville rule, see Concrete Mathematics p. 137). [From Gary W. Adamson, Aug 01 2008]
Equals row sums of triangle A143353 and of A143276.
Cf. A003558, A135303
Sequence in context: A011773 A080737 A152455 * A003978 A122645 A122646
Adjacent sequences: A000007 A000008 A000009 * A000011 A000012 A000013
|
|
|
KEYWORD
|
easy,core,nonn,mult,nice
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
STATUS
|
approved
|
| |
|
|
