# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/
Search: id:a000010
Showing 1-1 of 1
%I A000010 M0299 N0111 #584 Dec 23 2024 17:48:21
%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,12,
%T A000010 28,8,30,16,20,16,24,12,36,18,24,16,40,12,42,20,24,22,46,16,42,20,32,
%U A000010 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_, 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_, Mar 31 2005
%C A000010 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 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_, 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_, Jan 25 2007
%C A000010 Number of automorphisms of the cyclic group of order n. - _Benoit Jubin_, Aug 09 2008
%C A000010 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 A000010 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 A000010 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 A000010 Sum_{n>=1} a(n)/n! = 1.954085357876006213144... This sum is referenced in Plouffe's inverter. - _Alexander R. Povolotsky_, Feb 02 2013 (see A336334. - _Hugo Pfoertner_, Jul 22 2020)
%C A000010 The order of the multiplicative group of units modulo n. - _Michael Somos_, Aug 27 2013
%C A000010 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 A000010 From _Eric Desbiaux_, Jan 01 2017: (Start)
%C A000010 a(n) equals the Ramanujan sum c_n(n) (last term on n-th row of triangle A054533).
%C A000010 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 A000010 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 A000010 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
%C A000010 Number of cyclic Latin squares of order n with the first row in ascending order. - _Eduard I. Vatutin_, Nov 01 2020
%C A000010 a(n) is the number of rational numbers p/q >= 0 (in lowest terms) such that p + q = n. - _Rémy Sigrist_, Jan 17 2021
%C A000010 From _Richard L. Ollerton_, May 08 2021: (Start)
%C A000010 Formulas for the numerous OEIS entries involving Dirichlet convolution of a(n) and some sequence h(n) can be derived using the following (n >= 1):
%C A000010 Sum_{d|n} phi(d)*h(n/d) = Sum_{k=1..n} h(gcd(n,k)) [see P. H. van der Kamp link] = Sum_{d|n} h(d)*phi(n/d) = Sum_{k=1..n} h(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). Similarly,
%C A000010 Sum_{d|n} phi(d)*h(d) = Sum_{k=1..n} h(n/gcd(n,k)) = Sum_{k=1..n} h(gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)).
%C A000010 More generally,
%C A000010 Sum_{d|n} h(d) = Sum_{k=1..n} h(gcd(n,k))/phi(n/gcd(n,k)) = Sum_{k=1..n} h(n/gcd(n,k))/phi(n/gcd(n,k)).
%C A000010 In particular, for sequences involving the Möbius transform:
%C A000010 Sum_{d|n} mu(d)*h(n/d) = Sum_{k=1..n} h(gcd(n,k))*mu(n/gcd(n,k))/phi(n/gcd(n,k)) = Sum_{k=1..n} h(n/gcd(n,k))*mu(gcd(n,k))/phi(n/gcd(n,k)), where mu = A008683.
%C A000010 Use of gcd(n,k)*lcm(n,k) = n*k and phi(gcd(n,k))*phi(lcm(n,k)) = phi(n)*phi(k) provide further variations. (End)
%C A000010 From _Richard L. Ollerton_, Nov 07 2021: (Start)
%C A000010 Formulas for products corresponding to the sums above may found using the substitution h(n) = log(f(n)) where f(n) > 0 (for example, cf. formulas for the sum A018804 and product A067911 of gcd(n,k)):
%C A000010 Product_{d|n} f(n/d)^phi(d) = Product_{k=1..n} f(gcd(n,k)) = Product_{d|n} f(d)^phi(n/d) = Product_{k=1..n} f(n/gcd(n,k))^(phi(gcd(n,k))/phi(n/gcd(n,k))),
%C A000010 Product_{d|n} f(d)^phi(d) = Product_{k=1..n} f(n/gcd(n,k)) = Product_{k=1..n} f(gcd(n,k))^(phi(gcd(n,k))/phi(n/gcd(n,k))),
%C A000010 Product_{d|n} f(d) = Product_{k=1..n} f(gcd(n,k))^(1/phi(n/gcd(n,k))) = Product_{k=1..n} f(n/gcd(n,k))^(1/phi(n/gcd(n,k))),
%C A000010 Product_{d|n} f(n/d)^mu(d) = Product_{k=1..n} f(gcd(n,k))^(mu(n/gcd(n,k))/phi(n/gcd(n,k))) = Product_{k=1..n} f(n/gcd(n,k))^(mu(gcd(n,k))/phi(n/gcd(n,k))), where mu = A008683. (End)
%C A000010 a(n+1) is the number of binary words with exactly n distinct subsequences (when n > 0). - _Radoslaw Zak_, Nov 29 2021
%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 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 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 J.-M. De Koninck & A. Mercier, 1001 Problèmes en Théorie Classique des Nombres, Ellipses, Paris, 2004, Problème 529, pp. 71-257.
%D A000010 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 A000010 S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 115-119.
%D A000010 Carl Friedrich Gauss, "Disquisitiones Arithmeticae", Yale University Press, 1965; see p. 21.
%D A000010 Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Math., 2n-d ed.; Addison-Wesley, 1994, p. 137.
%D A000010 R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section B36.
%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 Peter Hilton and Jean Pedersen, A Mathematical Tapestry, Demonstrating the Beautiful Unity of Mathematics, Cambridge University Press, pages 261-264, the Coach theorem.
%D A000010 Jean-Marie Monier, Analyse, Exercices corrigés, 2ème année MP, Dunod, 1997, Exercice 3.2.21 pp. 281-294.
%D A000010 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.
%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, Table of n, phi(n) for n = 1..100000 (first 10000 terms from N. J. A. Sloane)
%H A000010 Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, Tenth Printing, 1972.
%H A000010 Dario A. Alpern, Factorization using the Elliptic Curve Method (along with sigma_0, sigma_1 and phi functions)
%H A000010 Joerg Arndt, Matters Computational (The Fxtbook), section 39.7, pp. 776-778.
%H A000010 F. Bayart, Indicateur d'Euler (in French).
%H A000010 Alexander Bogomolny, Euler Function and Theorem.
%H A000010 Chris K. Caldwell, The Prime Glossary, Euler's phi function
%H A000010 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]
%H A000010 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.
%H A000010 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]
%H A000010 Kevin Ford, The number of solutions of phi(x)=m, arXiv:math/9907204 [math.NT], 1999.
%H A000010 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 A000010 H. Fripertinger, The Euler phi function.
%H A000010 Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seqs., Vol. 6, 2003.
%H A000010 E. Pérez Herrero, Totient Carnival partitions, Psychedelic Geometry Blogspot.
%H A000010 Peter H. van der Kamp, On the Fourier transform of the greatest common divisor, arXiv:1201.3139 [math.NT]
%H A000010 M. Lal and P. Gillard, Table of Euler's phi function, n < 10^5, Math. Comp., 23 (1969), 682-683.
%H A000010 Derrick N. Lehmer, Review of Dickson's History of the Theory of Numbers, Bull. Amer. Math. Soc., 26 (1919), 125-132.
%H A000010 Peter Luschny, Sequences related to Euler's totient function.
%H A000010 R. J. Mathar, Graphical representation among sequences closely related to this one (cf. N. J. A. Sloane, "Families of Essentially Identical Sequences").
%H A000010 Mathematics Stack Exchange, Is the Euler phi function bounded below? (2013).
%H A000010 Mathforum, Proving phi(m) Is Even.
%H A000010 Keith Matthews, Factorizing n and calculating phi(n), omega(n), d(n), sigma(n) and mu(n).
%H A000010 Graeme McRae, Euler's Totient Function.
%H A000010 François Nicolas, A simple, polynomial-time algorithm for the matrix torsion problem, arXiv:0806.2068 [cs.DM], 2009.
%H A000010 Matthew Parker, The first 5 million terms (7-Zip compressed file).
%H A000010 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).
%H A000010 Primefan, Euler's Totient Function Values For n=1 to 500, with Divisor Lists.
%H A000010 Marko Riedel, Combinatorics and number theory page.
%H A000010 J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), no. 1, 64-94.
%H A000010 K. Schneider, Euler phi-function, PlanetMath.org.
%H A000010 Wacław F. Sierpiński, Euler's Totient Function And The Theorem Of Euler.
%H A000010 N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
%H A000010 N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 14.
%H A000010 Ulrich Sondermann, Euler's Totient Function.
%H A000010 William A. Stein, Phi is a Multiplicative Function
%H A000010 Pinthira Tangsupphathawat, Takao Komatsu and Vichian Laohakosol, Minimal Polynomials of Algebraic Cosine Values, II, J. Int. Seq., Vol. 21 (2018), Article 18.9.5.
%H A000010 László Tóth, Multiplicative arithmetic functions of several variables: a survey, arXiv preprint arXiv:1310.7053 [math.NT], 2013.
%H A000010 G. Villemin, Totient d'Euler.
%H A000010 K. W. Wegner, Values of phi(x) = n for n from 2 through 1978, mimeographed manuscript, no date. [Annotated scanned copy]
%H A000010 Eric Weisstein's World of Mathematics, Modulo Multiplication Group.
%H A000010 Eric Weisstein's World of Mathematics, Moebius Transform.
%H A000010 Eric Weisstein's World of Mathematics, Totient Function.
%H A000010 Wikipedia, Euler's totient function.
%H A000010 Wikipedia, Multiplicative group of integers modulo n.
%H A000010 Wikipedia, Ramanujan's sum
%H A000010 Wolfram Research, First 50 values of phi(n).
%H A000010 Gang Xiao, Numerical Calculator, To display phi(n) operate on "eulerphi(n)".
%H A000010 Index entries for "core" sequences
%H A000010 Index to divisibility sequences
%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, i.e., the Moebius transform of the natural numbers; mu() = Moebius function A008683().
%F A000010 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 A000010 Multiplicative with a(p^e) = (p - 1)*p^(e-1). - _David W. Wilson_, Aug 01 2001
%F A000010 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 A000010 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 A000010 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 A000010 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 A000010 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
%F A000010 From _Enrique Pérez Herrero_, Sep 07 2010: (Start)
%F A000010 a(n) = Sum_{i=1..n} floor(sigma_k(i*n)/sigma_k(i)*sigma_k(n)), where sigma_2 is A001157.
%F A000010 a(n) = Sum_{i=1..n} floor(tau_k(i*n)/tau_k(i)*tau_k(n)), where tau_3 is A007425.
%F A000010 a(n) = Sum_{i=1..n} floor(rad(i*n)/rad(i)*rad(n)), where rad is A007947. (End)
%F A000010 a(n) = A173557(n)*A003557(n). - _R. J. Mathar_, Mar 30 2011
%F A000010 a(n) = A096396(n) + A096397(n). - _Reinhard Zumkeller_, Mar 24 2012
%F A000010 phi(p*n) = phi(n)*(floor(((n + p - 1) mod p)/(p - 1)) + p - 1), for primes p. - _Gary Detlefs_, Apr 21 2012
%F A000010 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 A000010 G.f.: Sum_{n>=1} mu(n)*x^n/(1 - x^n)^2, where mu(n) = A008683(n). - _Mamuka Jibladze_, Apr 05 2015
%F A000010 a(n) = n - cototient(n) = n - A051953(n). - _Omar E. Pol_, May 14 2016
%F A000010 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 A000010 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 A000010 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 A000010 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
%F A000010 a(n) = Sum_{d|n} A007431(d). - _Steven Foster Clark_, May 29 2019
%F A000010 G.f. A(x) satisfies: A(x) = x/(1 - x)^2 - Sum_{k>=2} A(x^k). - _Ilya Gutkovskiy_, Sep 06 2019
%F A000010 a(n) >= sqrt(n/2) (Nicolas). - _Hugo Pfoertner_, Jun 01 2020
%F A000010 a(n) > n/(exp(gamma)*log(log(n)) + 5/(2*log(log(n)))), except for n=223092870 (Rosser, Schoenfeld). - _Hugo Pfoertner_, Jun 02 2020
%F A000010 From _Bernard Schott_, Nov 28 2020: (Start)
%F A000010 Sum_{m=1..n} 1/a(m) = A028415(n)/A048049(n) -> oo when n->oo.
%F A000010 Sum_{n >= 1} 1/a(n)^2 = A109695.
%F A000010 Sum_{n >= 1} 1/a(n)^3 = A335818.
%F A000010 Sum_{n >= 1} 1/a(n)^k is convergent iff k > 1.
%F A000010 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]
%F A000010 a(n) = 2*A023896(n)/n, n > 1. - _Richard R. Forberg_, Feb 03 2021
%F A000010 From _Richard L. Ollerton_, May 09 2021: (Start)
%F A000010 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.
%F A000010 For n > 1, Sum_{k=1..n} a(gcd(n,k))*mu(rad(gcd(n,k)))*rad(gcd(n,k))/gcd(n,k) = 0.
%F A000010 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.
%F A000010 Sum_{k=1..n} a(gcd(n,k))/a(n/gcd(n,k)) = n. (End)
%F A000010 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
%F A000010 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
%F A000010 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]
%e A000010 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 A000010 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
%e A000010 From _Eduard I. Vatutin_, Nov 01 2020: (Start)
%e A000010 The a(5)=4 cyclic Latin squares with the first row in ascending order are:
%e A000010 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4
%e A000010 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3
%e A000010 2 3 4 0 1 4 0 1 2 3 1 2 3 4 0 3 4 0 1 2
%e A000010 3 4 0 1 2 1 2 3 4 0 4 0 1 2 3 2 3 4 0 1
%e A000010 4 0 1 2 3 3 4 0 1 2 2 3 4 0 1 1 2 3 4 0
%e A000010 (End)
%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
%p A000010 # Alternative without library function:
%p A000010 A000010List := proc(N) local i, j, phi;
%p A000010 phi := Array([seq(i, i = 1 .. N+1)]);
%p A000010 for i from 2 to N + 1 do
%p A000010 if phi[i] = i then
%p A000010 for j from i by i to N + 1 do
%p A000010 phi[j] := phi[j] - iquo(phi[j], i) od
%p A000010 fi od;
%p A000010 return phi end:
%p A000010 A000010List(68); # _Peter Luschny_, Sep 03 2023
%t A000010 Array[EulerPhi, 70]
%o A000010 (Axiom) [eulerPhi(n) for n in 1..100]
%o A000010 (Magma) [ EulerPhi(n) : n in [1..100] ]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006
%o A000010 (PARI) {a(n) = if( n==0, 0, eulerphi(n))}; /* _Michael Somos_, Feb 05 2011 */
%o A000010 (Sage) def A000010(n): return euler_phi(n) # _Jaap Spies_, Jan 07 2007
%o A000010 (Sage) [euler_phi(n) for n in range(1, 70)] # _Zerinvary Lajos_, Jun 06 2009
%o A000010 (Maxima) makelist(totient(n),n,0,1000); /* _Emanuele Munarini_, Mar 26 2011 */
%o A000010 (Haskell) a n = length (filter (==1) (map (gcd n) [1..n])) -- _Allan C. Wechsler_, Dec 29 2014
%o A000010 (Python)
%o A000010 from sympy.ntheory import totient
%o A000010 print([totient(i) for i in range(1, 70)]) # _Indranil Ghosh_, Mar 17 2017
%o A000010 (Python) # Note also the implementation in A365339.
%o A000010 (Julia) # Computes the first N terms of the sequence.
%o A000010 function A000010List(N)
%o A000010 phi = [i for i in 1:N + 1]
%o A000010 for i in 2:N + 1
%o A000010 if phi[i] == i
%o A000010 for j in i:i:N + 1
%o A000010 phi[j] -= div(phi[j], i)
%o A000010 end end end
%o A000010 return phi end
%o A000010 println(A000010List(68)) # _Peter Luschny_, Sep 03 2023
%Y A000010 Cf. A002088 (partial sums), A008683, A003434 (steps to reach 1), A007755, A049108, A002202 (values), A011755 (Sum k*phi(k)).
%Y A000010 Cf. also A005277 (nontotient numbers). 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)), this sequence (J_1), A007434 (J_2), A059376 (J_3), A059377 (J_4), A059378 (J_5).
%Y A000010 Cf. A054521, A023022, A054525.
%Y A000010 Row sums of triangles A134540, A127448, A143239, A143353 and A143276.
%Y A000010 Equals right and left borders of triangle A159937. - _Gary W. Adamson_, Apr 26 2009
%Y A000010 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 A000010 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).
%Y A000010 Cf. A003558, A135303.
%Y A000010 Cf. A152455, A080737.
%Y A000010 Cf. A076479.
%Y A000010 Cf. A023900 (Dirichlet inverse of phi), A306633 (Dgf at s=3).
%K A000010 easy,core,nonn,mult,nice,hear
%O A000010 1,3
%A A000010 _N. J. A. Sloane_
# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE