A000010 Euler totient function phi(n): count numbers <= n and prime to n.
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
Offset: 1
Examples
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 + ...
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
From _Eduard I. Vatutin_, Nov 01 2020: (Start)
The a(5)=4 cyclic Latin squares with the first row in ascending order are:
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4
1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3
2 3 4 0 1 4 0 1 2 3 1 2 3 4 0 3 4 0 1 2
3 4 0 1 2 1 2 3 4 0 4 0 1 2 3 2 3 4 0 1
4 0 1 2 3 3 4 0 1 2 2 3 4 0 1 1 2 3 4 0
(End)
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.
- 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.
- Florian Cajori, A History of Mathematical Notations, Dover edition (2012), par. 409.
- L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 193.
- John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 154-156.
- C. W. Curtis, Pioneers of Representation Theory ..., Amer. Math. Soc., 1999; see p. 3.
- J.-M. De Koninck & A. Mercier, 1001 Problèmes en Théorie Classique des Nombres, Ellipses, Paris, 2004, Problème 529, pp. 71-257.
- 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, "Disquisitiones 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.
- R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section B36.
- 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.
- Jean-Marie Monier, Analyse, Exercices corrigés, 2ème année MP, Dunod, 1997, Exercice 3.2.21 pp. 281-294.
- G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, New York, Heidelberg, Berlin, 2 vols., 1976, Vol. II, problem 71, p. 126.
- Paulo Ribenboim, The New Book of Prime Number Records.
- Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 28-33.
- 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).
- James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 162-167.
Links
- Daniel Forgues, Table of n, phi(n) for n = 1..100000 (first 10000 terms from N. J. A. Sloane)
- Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, Tenth Printing, 1972.
- Dario A. Alpern, Factorization using the Elliptic Curve Method (along with sigma_0, sigma_1 and phi functions)
- Joerg Arndt, Matters Computational (The Fxtbook), section 39.7, pp. 776-778.
- F. Bayart, Indicateur d'Euler (in French).
- Alexander Bogomolny, Euler Function and Theorem.
- Chris K. Caldwell, The Prime Glossary, Euler's phi function
- Robert D. Carmichael, A table of the values of m corresponding to given values of phi(m), Amer. J. Math., 30 (1908), 394-400. [Annotated scanned copy]
- Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.
- Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]
- Kevin Ford, The number of solutions of phi(x)=m, arXiv:math/9907204 [math.NT], 1999.
- 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 [math.NT], 2011.
- H. Fripertinger, The Euler phi function.
- Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seqs., Vol. 6, 2003.
- E. Pérez Herrero, Totient Carnival partitions, Psychedelic Geometry Blogspot.
- Peter H. van der Kamp, On the Fourier transform of the greatest common divisor, arXiv:1201.3139 [math.NT]
- M. Lal and P. Gillard, Table of Euler's phi function, n < 10^5, Math. Comp., 23 (1969), 682-683.
- Derrick N. Lehmer, Review of Dickson's History of the Theory of Numbers, Bull. Amer. Math. Soc., 26 (1919), 125-132.
- Peter Luschny, Sequences related to Euler's totient function.
- R. J. Mathar, Graphical representation among sequences closely related to this one (cf. N. J. A. Sloane, "Families of Essentially Identical Sequences").
- Mathematics Stack Exchange, Is the Euler phi function bounded below? (2013).
- Mathforum, Proving phi(m) Is Even.
- Keith Matthews, Factorizing n and calculating phi(n), omega(n), d(n), sigma(n) and mu(n).
- Graeme McRae, Euler's Totient Function.
- François Nicolas, A simple, polynomial-time algorithm for the matrix torsion problem, arXiv:0806.2068 [cs.DM], 2009.
- Matthew Parker, The first 5 million terms (7-Zip compressed file).
- Carl Pomerance and Hee-Sung Yang, Variant of a theorem of Erdős on the sum-of-proper-divisors function, Math. Comp., to appear (2014).
- Primefan, Euler's Totient Function Values For n=1 to 500, with Divisor Lists.
- Marko Riedel, Combinatorics and number theory page.
- J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), no. 1, 64-94.
- K. Schneider, Euler phi-function, PlanetMath.org.
- Wacław F. Sierpiński, Euler's Totient Function And The Theorem Of Euler.
- N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
- N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 14.
- Ulrich Sondermann, Euler's Totient Function.
- William A. Stein, Phi is a Multiplicative Function
- Pinthira Tangsupphathawat, Takao Komatsu and Vichian Laohakosol, Minimal Polynomials of Algebraic Cosine Values, II, J. Int. Seq., Vol. 21 (2018), Article 18.9.5.
- László Tóth, Multiplicative arithmetic functions of several variables: a survey, arXiv preprint arXiv:1310.7053 [math.NT], 2013.
- G. Villemin, Totient d'Euler.
- K. W. Wegner, Values of phi(x) = n for n from 2 through 1978, mimeographed manuscript, no date. [Annotated scanned copy]
- Eric Weisstein's World of Mathematics, Modulo Multiplication Group.
- Eric Weisstein's World of Mathematics, Moebius Transform.
- Eric Weisstein's World of Mathematics, Totient Function.
- Wikipedia, Euler's totient function.
- Wikipedia, Multiplicative group of integers modulo n.
- Wikipedia, Ramanujan's sum
- Wolfram Research, First 50 values of phi(n).
- Gang Xiao, Numerical Calculator, To display phi(n) operate on "eulerphi(n)".
- Index entries for "core" sequences
- Index to divisibility sequences
Crossrefs
Cf. A002088 (partial sums), A008683, A003434 (steps to reach 1), A007755, A049108, A002202 (values), A011755 (Sum k*phi(k)).
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).
Equals right and left borders of triangle A159937. - Gary W. Adamson, Apr 26 2009
Values for prime powers p^e: A006093 (e=1), A036689 (e=2), A135177 (e=3), A138403 (e=4), A138407 (e=5), A138412 (e=6).
Values for perfect powers n^e: A002618 (e=2), A053191 (e=3), A189393 (e=4), A238533 (e=5), A306411 (e=6), A239442 (e=7), A306412 (e=8), A239443 (e=9).
Cf. A076479.
Programs
-
Axiom
[eulerPhi(n) for n in 1..100]
-
Haskell
a n = length (filter (==1) (map (gcd n) [1..n])) -- Allan C. Wechsler, Dec 29 2014
-
Julia
# Computes the first N terms of the sequence. function A000010List(N) phi = [i for i in 1:N + 1] for i in 2:N + 1 if phi[i] == i for j in i:i:N + 1 phi[j] -= div(phi[j], i) end end end return phi end println(A000010List(68)) # Peter Luschny, Sep 03 2023
-
Magma
[ EulerPhi(n) : n in [1..100] ]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006
-
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 # Alternative without library function: A000010List := proc(N) local i, j, phi; phi := Array([seq(i, i = 1 .. N+1)]); for i from 2 to N + 1 do if phi[i] = i then for j from i by i to N + 1 do phi[j] := phi[j] - iquo(phi[j], i) od fi od; return phi end: A000010List(68); # Peter Luschny, Sep 03 2023
-
Mathematica
Array[EulerPhi, 70]
-
Maxima
makelist(totient(n),n,0,1000); /* Emanuele Munarini, Mar 26 2011 */
-
PARI
{a(n) = if( n==0, 0, eulerphi(n))}; /* Michael Somos, Feb 05 2011 */ -
Python
from sympy.ntheory import totient print([totient(i) for i in range(1, 70)]) # Indranil Ghosh, Mar 17 2017
-
Python
# Note also the implementation in A365339.
-
Sage
def A000010(n): return euler_phi(n) # Jaap Spies, Jan 07 2007
-
Sage
[euler_phi(n) for n in range(1, 70)] # Zerinvary Lajos, Jun 06 2009
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)*log(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
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
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]
Conjecture: Sum_{i>=2} (-1)^i/(i*phi(i)) exists and is approximately 0.558 (A335319). - Orges Leka (oleka(AT)students.uni-mainz.de), Dec 23 2004
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)
phi(p*n) = phi(n)*(floor(((n + p - 1) mod p)/(p - 1)) + p - 1), for primes p. - Gary Detlefs, Apr 21 2012
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
G.f.: Sum_{n>=1} mu(n)*x^n/(1 - x^n)^2, where mu(n) = A008683(n). - Mamuka Jibladze, Apr 05 2015
a(n) = n - cototient(n) = n - A051953(n). - Omar E. Pol, May 14 2016
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
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
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
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
a(n) = Sum_{d|n} A007431(d). - Steven Foster Clark, May 29 2019
G.f. A(x) satisfies: A(x) = x/(1 - x)^2 - Sum_{k>=2} A(x^k). - Ilya Gutkovskiy, Sep 06 2019
a(n) >= sqrt(n/2) (Nicolas). - Hugo Pfoertner, Jun 01 2020
a(n) > n/(exp(gamma)*log(log(n)) + 5/(2*log(log(n)))), except for n=223092870 (Rosser, Schoenfeld). - Hugo Pfoertner, Jun 02 2020
From Bernard Schott, Nov 28 2020: (Start)
Sum_{n >= 1} 1/a(n)^2 = A109695.
Sum_{n >= 1} 1/a(n)^3 = A335818.
Sum_{n >= 1} 1/a(n)^k is convergent iff k > 1.
a(2n) = a(n) iff n is odd, and, a(2n) > a(n) iff n is even. (End) [Actually, a(2n) = 2*a(n) for even n. - Jianing Song, Sep 18 2022]
a(n) = 2*A023896(n)/n, n > 1. - Richard R. Forberg, Feb 03 2021
From Richard L. Ollerton, May 09 2021: (Start)
For n > 1, Sum_{k=1..n} phi^{(-1)}(n/gcd(n,k))*a(gcd(n,k))/a(n/gcd(n,k)) = 0, where phi^{(-1)} = A023900.
For n > 1, Sum_{k=1..n} a(gcd(n,k))*mu(rad(gcd(n,k)))*rad(gcd(n,k))/gcd(n,k) = 0.
For n > 1, Sum_{k=1..n} a(gcd(n,k))*mu(rad(n/gcd(n,k)))*rad(n/gcd(n,k))*gcd(n,k) = 0.
Sum_{k=1..n} a(gcd(n,k))/a(n/gcd(n,k)) = n. (End)
a(n) = Sum_{d|n, e|n} gcd(d, e)*mobius(n/d)*mobius(n/e) (the sum is a multiplicative function of n by Tóth, and takes the value p^e - p^(e-1) for n = p^e, a prime power). - Peter Bala, Jan 22 2024
Sum_{n >= 1} phi(n)*x^n/(1 + x^n) = x + 3*x^3 + 5*x^5 + 7*x^7 + ... = Sum_{n >= 1} phi(2*n-1)*x^(2*n-1)/(1 - x^(4*n-2)). For the first equality see Pólya and Szegő, problem 71, p. 126. - Peter Bala, Feb 29 2024
Conjecture: a(n) = lim_{k->oo} (n^(k + 1))/A000203(n^k). - Velin Yanev, Dec 04 2024 [A000010(p) = p-1, A000203(p^k) = (p^(k+1)-1)/(p-1), so the conjecture is true if n is prime. - Vaclav Kotesovec, Dec 19 2024]
Comments