A000010 - OEIS

%I M0299 N0111 #584 Dec 23 2024 17:48:21

%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 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 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 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

%C Number of cyclic Latin squares of order n with the first row in ascending order. - _Eduard I. Vatutin_, Nov 01 2020

%C 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 From _Richard L. Ollerton_, May 08 2021: (Start)

%C 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 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 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 More generally,

%C 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 In particular, for sequences involving the Möbius transform:

%C 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 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 From _Richard L. Ollerton_, Nov 07 2021: (Start)

%C 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 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 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 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 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 a(n+1) is the number of binary words with exactly n distinct subsequences (when n > 0). - _Radoslaw Zak_, Nov 29 2021

%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 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 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, "Disquisitiones 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 R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section B36.

%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 Jean-Marie Monier, Analyse, Exercices corrigés, 2ème année MP, Dunod, 1997, Exercice 3.2.21 pp. 281-294.

%D 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 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 Milton Abramowitz and Irene A. Stegun, eds., <a href="https://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards Applied Math. Series 55, Tenth Printing, 1972.

%H Dario A. Alpern, <a href="https://www.alpertron.com.ar/ECM.HTM">Factorization using the Elliptic Curve Method (along with sigma_0, sigma_1 and phi functions)</a>

%H Joerg Arndt, <a href="https://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 39.7, pp. 776-778.

%H F. Bayart, <a href="https://www.bibmath.net/dico/index.php?action=affiche&amp;quoi=./i/indicateureuler.html">Indicateur d'Euler</a> (in French).

%H Alexander Bogomolny, <a href="https://www.cut-the-knot.org/blue/Euler.shtml">Euler Function and Theorem</a>.

%H Chris K. Caldwell, The Prime Glossary, <a href="https://t5k.org/glossary/page.php?sort=EulersPhi">Euler's phi function</a>

%H Robert 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="https://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 Erdős, 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 Kevin Ford, <a href="https://arxiv.org/abs/math/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="https://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="https://web.archive.org/web/20150910232858/http://www.uni-graz.at/~fripert/fga/k1euler.html">The Euler phi function</a>.

%H Daniele A. Gewurz and Francesca Merola, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL6/Gewurz/gewurz5.html">Sequences realized as Parker vectors of oligomorphic permutation groups</a>, J. Integer Seqs., Vol. 6, 2003.

%H E. Pérez Herrero, <a href="https://psychedelic-geometry.blogspot.com/2010/07/totient-carnival.html">Totient Carnival partitions</a>, Psychedelic Geometry Blogspot.

%H Peter H. van der Kamp, <a href="https://arxiv.org/abs/1201.3139">On the Fourier transform of the greatest common divisor</a>, arXiv:1201.3139 [math.NT]

%H M. Lal and P. Gillard, <a href="https://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 Derrick N. Lehmer, <a href="https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society-new-series/volume-26/issue-3/Dicksons-History-of-the-Theory-of-Numbers/bams/1183425137.full">Review of Dickson's History of the Theory of Numbers</a>, Bull. Amer. Math. Soc., 26 (1919), 125-132.

%H Peter Luschny, <a href="https://oeis.org/wiki/User:Peter_Luschny/EulerTotient">Sequences related to Euler's totient function</a>.

%H R. J. Mathar, <a href="/A000010/a000010_2.pdf">Graphical representation among sequences closely related to this one</a> (cf. N. J. A. Sloane, "Families of Essentially Identical Sequences").

%H Mathematics Stack Exchange, <a href="https://math.stackexchange.com/questions/301837/is-the-euler-phi-function-bounded-below">Is the Euler phi function bounded below?</a> (2013).

%H Mathforum, <a href="http://mathforum.org/library/drmath/view/51541.html">Proving phi(m) Is Even</a>.

%H Keith 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="https://web.archive.org/web/20130508193928/http://2000clicks.com/MathHelp/NumberFactorsTotientFunction.aspx">Euler's Totient Function</a>.

%H François Nicolas, <a href="https://arxiv.org/abs/0806.2068">A simple, polynomial-time algorithm for the matrix torsion problem</a>, arXiv:0806.2068 [cs.DM], 2009.

%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="https://www.math.dartmouth.edu/~carlp/uupaper7.pdf">Variant of a theorem of Erdős on the sum-of-proper-divisors function</a>, Math. Comp., to appear (2014).

%H Primefan, <a href="https://primefan.tripod.com/Phi500.html">Euler's Totient Function Values For n=1 to 500, with Divisor Lists</a>.

%H Marko Riedel, <a href="https://web.archive.org/web/20170406154901/http://www.mathematik.uni-stuttgart.de/~riedelmo/combnumth.html">Combinatorics and number theory page</a>.

%H J. Barkley Rosser and Lowell Schoenfeld, <a href="https://dx.doi.org/10.1215/ijm/1255631807">Approximate formulas for some functions of prime numbers</a>, Illinois J. Math. 6 (1962), no. 1, 64-94.

%H K. Schneider, <a href="https://planetmath.org/eulerphifunction">Euler phi-function</a>, PlanetMath.org.

%H Wacław F. 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 N. J. A. Sloane, <a href="/A115004/a115004.txt">Families of Essentially Identical Sequences</a>, Mar 24 2021 (Includes this sequence)

%H N. J. A. Sloane, <a href="https://arxiv.org/abs/2301.03149">"A Handbook of Integer Sequences" Fifty Years Later</a>, arXiv:2301.03149 [math.NT], 2023, p. 14.

%H Ulrich Sondermann, <a href="https://web.archive.org/web/20110823215228/http://home.earthlink.net/~usondermann/eulertot.html">Euler's Totient Function</a>.

%H William A. Stein, <a href="https://wstein.org/edu/Fall2001/124/lectures/lecture6/html/node3.html">Phi is a Multiplicative Function</a>

%H Pinthira Tangsupphathawat, Takao Komatsu and Vichian Laohakosol, <a href="https://www.emis.de/journals/JIS/VOL21/Laohakosol/lao8.html">Minimal Polynomials of Algebraic Cosine Values, II</a>, J. Int. Seq., Vol. 21 (2018), Article 18.9.5.

%H László Tóth, <a href="http://arxiv.org/abs/1310.7053">Multiplicative arithmetic functions of several variables: a survey</a>, arXiv preprint arXiv:1310.7053 [math.NT], 2013.

%H G. Villemin, <a href="http://villemin.gerard.free.fr/Wwwgvmm/Nombre/TotEuler.htm">Totient d'Euler</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 Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ModuloMultiplicationGroup.html">Modulo Multiplication Group</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MoebiusTransform.html">Moebius Transform</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TotientFunction.html">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 Wikipedia, <a href="http://en.wikipedia.org/wiki/Ramanujan&#39;s_sum">Ramanujan's sum</a>

%H Wolfram Research, <a href="http://functions.wolfram.com/NumberTheoryFunctions/EulerPhi/03/02">First 50 values of phi(n)</a>.

%H Gang Xiao, Numerical Calculator, <a href="https://wims.univ-cotedazur.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) = n - #{1 <= i <= n : k(n, i) = 0}. - _Benoit Cloitre_, Aug 06 2004 [Corrected by _Jianing Song_, Sep 25 2018]

%F 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 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 a(n) = A096396(n) + A096397(n). - _Reinhard Zumkeller_, Mar 24 2012

%F phi(p*n) = phi(n)*(floor(((n + p - 1) mod p)/(p - 1)) + p - 1), for primes p. - _Gary Detlefs_, Apr 21 2012

%F 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 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

%F 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 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 a(n) = Sum_{d|n} A007431(d). - _Steven Foster Clark_, May 29 2019

%F G.f. A(x) satisfies: A(x) = x/(1 - x)^2 - Sum_{k>=2} A(x^k). - _Ilya Gutkovskiy_, Sep 06 2019

%F a(n) >= sqrt(n/2) (Nicolas). - _Hugo Pfoertner_, Jun 01 2020

%F 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 From _Bernard Schott_, Nov 28 2020: (Start)

%F Sum_{m=1..n} 1/a(m) = A028415(n)/A048049(n) -> oo when n->oo.

%F Sum_{n >= 1} 1/a(n)^2 = A109695.

%F Sum_{n >= 1} 1/a(n)^3 = A335818.

%F Sum_{n >= 1} 1/a(n)^k is convergent iff k > 1.

%F 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 a(n) = 2*A023896(n)/n, n > 1. - _Richard R. Forberg_, Feb 03 2021

%F From _Richard L. Ollerton_, May 09 2021: (Start)

%F 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 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 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 Sum_{k=1..n} a(gcd(n,k))/a(n/gcd(n,k)) = n. (End)

%F 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 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 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 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

%e From _Eduard I. Vatutin_, Nov 01 2020: (Start)

%e The a(5)=4 cyclic Latin squares with the first row in ascending order are:

%e   0 1 2 3 4   0 1 2 3 4   0 1 2 3 4   0 1 2 3 4

%e   1 2 3 4 0   2 3 4 0 1   3 4 0 1 2   4 0 1 2 3

%e   2 3 4 0 1   4 0 1 2 3   1 2 3 4 0   3 4 0 1 2

%e   3 4 0 1 2   1 2 3 4 0   4 0 1 2 3   2 3 4 0 1

%e   4 0 1 2 3   3 4 0 1 2   2 3 4 0 1   1 2 3 4 0

%e (End)

%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

%p # Alternative without library function:

%p A000010List := proc(N) local i, j, phi;

%p     phi := Array([seq(i, i = 1 .. N+1)]);

%p     for i from 2 to N + 1 do

%p         if phi[i] = i then

%p             for j from i by i to N + 1 do

%p                 phi[j] := phi[j] - iquo(phi[j], i) od

%p         fi od;

%p return phi end:

%p A000010List(68);  # _Peter Luschny_, Sep 03 2023

%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) def A000010(n): return euler_phi(n) # _Jaap Spies_, Jan 07 2007

%o (Sage) [euler_phi(n) for n in range(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 range(1, 70)])  # _Indranil Ghosh_, Mar 17 2017

%o (Python) # Note also the implementation in A365339.

%o (Julia) # Computes the first N terms of the sequence.

%o function A000010List(N)

%o     phi = [i for i in 1:N + 1]

%o     for i in 2:N + 1

%o         if phi[i] == i

%o             for j in i:i:N + 1

%o                 phi[j] -= div(phi[j], i)

%o     end end end

%o return phi end

%o println(A000010List(68))  # _Peter Luschny_, Sep 03 2023

%Y Cf. A002088 (partial sums), A008683, A003434 (steps to reach 1), A007755, A049108, A002202 (values), A011755 (Sum k*phi(k)).

%Y Cf. also 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)), this sequence (J_1), A007434 (J_2), A059376 (J_3), A059377 (J_4), A059378 (J_5).

%Y Cf. A054521, A023022, A054525.

%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 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 Cf. A003558, A135303.

%Y Cf. A152455, A080737.

%Y Cf. A076479.

%Y Cf. A023900 (Dirichlet inverse of phi), A306633 (Dgf at s=3).

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

%O 1,3

%A _N. J. A. Sloane_