cp's OEIS Frontend

A008683 Möbius (or Moebius) function mu(n). mu(1) = 1; mu(n) = (-1)^k if n is the product of k different primes; otherwise mu(n) = 0.

%I A008683 #388 Aug 18 2025 12:13:03
%S A008683 1,-1,-1,0,-1,1,-1,0,0,1,-1,0,-1,1,1,0,-1,0,-1,0,1,1,-1,0,0,1,0,0,-1,
%T A008683 -1,-1,0,1,1,1,0,-1,1,1,0,-1,-1,-1,0,0,1,-1,0,0,0,1,0,-1,0,1,0,1,1,-1,
%U A008683 0,-1,1,0,0,1,-1,-1,0,1,-1,-1,0,-1,1,0,0,1,-1
%N A008683 Möbius (or Moebius) function mu(n). mu(1) = 1; mu(n) = (-1)^k if n is the product of k different primes; otherwise mu(n) = 0.
%C A008683 Moebius inversion: f(n) = Sum_{d|n} g(d) for all n <=> g(n) = Sum_{d|n} mu(d)*f(n/d) for all n.
%C A008683 a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24 = 2^3 * 3 and 375 = 3 * 5^3 both have prime signature (3, 1).
%C A008683 A008683 = A140579^(-1) * A140664. - _Gary W. Adamson_, May 20 2008
%C A008683 Coons & Borwein prove that Sum_{n>=1} mu(n) z^n is transcendental. - _Jonathan Vos Post_, Jun 11 2008; edited by _Charles R Greathouse IV_, Sep 06 2017
%C A008683 Equals row sums of triangle A144735 (the square of triangle A054533). - _Gary W. Adamson_, Sep 20 2008
%C A008683 Conjecture: a(n) is the determinant of Redheffer matrix A143104 where T(n, n) = 0. Verified for the first 50 terms. - _Mats Granvik_, Jul 25 2008
%C A008683 From _Mats Granvik_, Dec 06 2008: (Start)
%C A008683 The Editorial Office of the Journal of Number Theory kindly provided (via B. Conrey) the following proof of the conjecture: Let A be A143104 and B be A143104 where T(n, n) = 0.
%C A008683 "Suppose you expand det(B_n) along the bottom row. There is only a 1 in the first position and so the answer is (-1)^n times det(C_{n-1}) say, where C_{n-1} is the (n-1) by (n-1) matrix obtained from B_n by deleting the first column and the last row. Now the determinant of the Redheffer matrix is det(A_n) = M(n) where M(n) is the sum of mu(m) for 1 <= m <= n. Expanding det(A_n) along the bottom row, we see that det(A_n) = (-1)^n * det(C_{n-1}) + M(n-1). So we have det(B_n) = (-1)^n * det(C_{n-1}) = det(A_n) - M(n-1) = M(n) - M(n-1) = mu(n)." (End)
%C A008683 Conjecture: Consider the table A051731 and treat 1 as a divisor. Move the value in the lower right corner vertically to a divisor position in the transpose of the table and you will find that the determinant is the Moebius function. The number of permutation matrices that contribute to the Moebius function appears to be A074206. - _Mats Granvik_, Dec 08 2008
%C A008683 Convolved with A152902 = A000027, the natural numbers. - _Gary W. Adamson_, Dec 14 2008
%C A008683 [Pickover, p. 226]: "The probability that a number falls in the -1 mailbox turns out to be 3/Pi^2 - the same probability as for falling in the +1 mailbox". - _Gary W. Adamson_, Aug 13 2009
%C A008683 Let A = A176890 and B = A * A * ... * A, then the leftmost column in matrix B converges to the Moebius function. - _Mats Granvik_, _Gary W. Adamson_, Apr 28 2010 and May 28 2020
%C A008683 Equals row sums of triangle A176918. - _Gary W. Adamson_, Apr 29 2010
%C A008683 Calculate matrix powers: A175992^0 - A175992^1 + A175992^2 - A175992^3 + A175992^4 - ... Then the Mobius function is found in the first column. Compare this to the binomial series for (1+x)^-1 = 1 - x + x^2 - x^3 + x^4 - ... . - _Mats Granvik_, _Gary W. Adamson_, Dec 06 2010
%C A008683 From _Richard L. Ollerton_, May 08 2021: (Start)
%C A008683 Formulas for the numerous OEIS entries involving the Möbius transform (Dirichlet convolution of a(n) and some sequence h(n)) can be derived using the following (n >= 1):
%C A008683 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 phi = A000010.
%C A008683 Use of gcd(n,k)*lcm(n,k) = n*k provides further variations. (End)
%C A008683 Formulas for products corresponding to the sums above are also available for sequences f(n) > 0: 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))). - _Richard L. Ollerton_, Nov 08 2021
%D A008683 T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 24.
%D A008683 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 161, #16.
%D A008683 G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, Cambridge, University Press, 1940, pp. 64-65.
%D A008683 G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, th. 262 and 287.
%D A008683 Clifford A. Pickover, "The Math Book, from Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics", Sterling Publishing, 2009, p. 226. - _Gary W. Adamson_, Aug 13 2009
%D A008683 G. Pólya and G. Szegő, Problems and Theorems in Analysis Volume II. Springer_Verlag 1976.
%D A008683 James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 98-99.
%H A008683 Daniel Forgues, <a href="/A008683/b008683.txt">Table of n, a(n) for n = 1..100000</a> (first 10000 terms from N. J. A. Sloane)
%H A008683 Milton Abramowitz and Irene A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards Applied Math. Series 55, Tenth Printing, 1972, p. 826.
%H A008683 All Angles, <a href="https://www.youtube.com/watch?v=fGbJrY75LU8">What is the Moebius function?</a>, video, 2024.
%H A008683 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp. 705-707.
%H A008683 Yu Hin (Gary) Au, <a href="https://arxiv.org/abs/2205.03680">Decompositions of Unit Hypercubes and the Reversion of a Generalized Möbius Series</a>, arXiv:2205.03680 [math.CO], 2022.
%H A008683 Olivier Bordellès, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Bordelles2/bordelles21.html">Some Explicit Estimates for the Mobius Function </a>, J. Int. Seq. 18 (2015) 15.11.1
%H A008683 G. J. Chaitin, <a href="https://arxiv.org/abs/math/0306042">Thoughts on the Riemann hypothesis</a> arXiv:math/0306042 [math.HO], 2003.
%H A008683 Michael Coons and Peter Borwein, <a href="http://arxiv.org/abs/0806.1563">Transcendence of Power Series for Some Number Theoretic Functions</a>, arXiv:0806.1563 [math.NT], 2008.
%H A008683 Marc Deléglise and Joël Rivat, <a href="http://projecteuclid.org/euclid.em/1047565447">Computing the summation of the Mobius function</a>, Experiment. Math. 5:4 (1996), pp. 291-295.
%H A008683 Tom Edgar, <a href="http://www.plu.edu/~edgartj/">Posets and Möbius Inversion</a>, slides, (2008).
%H A008683 Mats Granvik, <a href="http://mobiusfunction.wordpress.com/2010/08/07/the-inverse-of-triangular-matrix-using-determinants/">Inverse of a triangular matrix using determinants</a>, <a href="http://mobiusfunction.wordpress.com/2010/08/07/the-inverse-of-a-triangular-matrix/">Inverse of a triangular matrix using matrix multiplication</a>, <a href="http://mobiusfunction.wordpress.com/2010/12/08/the-inverse-of-triangular-matrix-as-a-binomial-series/">Inverse of a triangular matrix as a binomial series</a>, <a href="http://mobiusfunction.wordpress.com/2011/03/08/the-ordinary-generating-function-for-the-mobius-function/">The ordinary generating function for the Mobius function</a>.
%H A008683 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 A008683 A. F. Möbius, <a href="http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002138654">Über eine besondere Art von Umkehrung der Reihen.</a> Journal für die reine und angewandte Mathematik 9 (1832), 105-123.
%H A008683 Ed Pegg Jr., <a href="https://www.mathpuzzle.com/MAA/02-Mobius%20Function/mathgames_11_03_03.html">The Mobius function (and squarefree numbers)</a>.
%H A008683 Anders Björner and Richard P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers/comb.pdf">A combinatorial miscellany</a>.
%H A008683 Paul Tarau, <a href="http://dx.doi.org/10.1007/978-3-642-23283-1_15">Emulating Primality with Multiset Representations of Natural Numbers</a>, in Theoretical Aspects Of Computing, ICTAC 2011, Lecture Notes in Computer Science, 2011, Volume 6916/2011, 218-238.
%H A008683 Paul Tarau, <a href="http://dx.doi.org/10.1016/j.tcs.2014.04.025">Towards a generic view of primality through multiset decompositions of natural numbers</a>, Theoretical Computer Science, Volume 537, Jun 05 2014, pp. 105-124.
%H A008683 Gerard Villemin's Almanac of Numbers, <a href="http://villemin.gerard.free.fr/TABLES/aaaFArit/MobiusMe.htm">Nombres de Moebius et de Mertens</a>.
%H A008683 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MoebiusFunction.html">Moebius Function</a>.
%H A008683 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/RedhefferMatrix.html">Redheffer Matrix</a>.
%H A008683 Wikipedia, <a href="http://en.wikipedia.org/wiki/Mobius_function">Moebius function</a>.
%H A008683 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H A008683 <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>
%F A008683 Sum_{d|n} mu(d) = 1 if n = 1 else 0.
%F A008683 Dirichlet generating function: Sum_{n >= 1} mu(n)/n^s = 1/zeta(s). Also Sum_{n >= 1} mu(n)*x^n/(1-x^n) = x.
%F A008683 In particular, Sum_{n > 0} mu(n)/n = 0. - _Franklin T. Adams-Watters_, Jun 20 2014
%F A008683 phi(n) = Sum_{d|n} mu(d)*n/d.
%F A008683 a(n) = A091219(A091202(n)).
%F A008683 Multiplicative with a(p^e) = -1 if e = 1; 0 if e > 1. - _David W. Wilson_, Aug 01 2001
%F A008683 abs(a(n)) = Sum_{d|n} 2^A001221(d)*a(n/d). - _Benoit Cloitre_, Apr 05 2002
%F A008683 Sum_{d|n} (-1)^(n/d)*mobius(d) = 0 for n > 2. - _Emeric Deutsch_, Jan 28 2005
%F A008683 a(n) = (-1)^omega(n) * 0^(bigomega(n) - omega(n)) for n > 0, where bigomega(n) and omega(n) are the numbers of prime factors of n with and without repetition (A001222, A001221, A046660). - _Reinhard Zumkeller_, Apr 05 2003
%F A008683 Dirichlet generating function for the absolute value: zeta(s)/zeta(2s). - _Franklin T. Adams-Watters_, Sep 11 2005
%F A008683 mu(n) = A129360(n) * (1, -1, 0, 0, 0, ...). - _Gary W. Adamson_, Apr 17 2007
%F A008683 mu(n) = -Sum_{d < n, d|n} mu(d) if n > 1 and mu(1) = 1. - _Alois P. Heinz_, Aug 13 2008
%F A008683 a(n) = A174725(n) - A174726(n). - _Mats Granvik_, Mar 28 2010
%F A008683 a(n) = first column in the matrix inverse of a triangular table with the definition: T(1, 1) = 1, n > 1: T(n, 1) is any number or sequence, k = 2: T(n, 2) = T(n, k-1) - T(n-1, k), k > 2 and n >= k: T(n,k) = (Sum_{i = 1..k-1} T(n-i, k-1)) - (Sum_{i = 1..k-1} T(n-i, k)). - _Mats Granvik_, Jun 12 2010
%F A008683 Product_{n >= 1} (1-x^n)^(-a(n)/n) = exp(x) (product form of the exponential function). - _Joerg Arndt_, May 13 2011
%F A008683 a(n) = Sum_{k=1..n, gcd(k,n)=1} exp(2*Pi*i*k/n), the sum over the primitive n-th roots of unity. See the Apostol reference, p. 48, Exercise 14 (b). - _Wolfdieter Lang_, Jun 13 2011
%F A008683 mu(n) = Sum_{k=1..n} A191898(n,k)*exp(-i*2*Pi*k/n)/n. (conjecture). - _Mats Granvik_, Nov 20 2011
%F A008683 Sum_{k=1..n} a(k)*floor(n/k) = 1 for n >= 1. - _Peter Luschny_, Feb 10 2012
%F A008683 a(n) = floor(omega(n)/bigomega(n))*(-1)^omega(n) = floor(A001221(n)/A001222(n))*(-1)^A001221(n). - _Enrique Pérez Herrero_, Apr 27 2012
%F A008683 Multiplicative with a(p^e) = binomial(1, e) * (-1)^e. - _Enrique Pérez Herrero_, Jan 19 2013
%F A008683 G.f. A(x) satisfies: x^2/A(x) = Sum_{n>=1} A( x^(2*n)/A(x)^n ). - _Paul D. Hanna_, Apr 19 2016
%F A008683 a(n) = -A008966(n)*A008836(n)/(-1)^A005361(n) = -floor(rad(n)/n)Lambda(n)/(-1)^tau(n/rad(n)). - _Anthony Browne_, May 17 2016
%F A008683 a(n) = Kronecker delta of A001221(n) and A001222(n) (which is A008966) multiplied by A008836(n). - _Eric Desbiaux_, Mar 15 2017
%F A008683 a(n) = A132971(A156552(n)). - _Antti Karttunen_, May 30 2017
%F A008683 Conjecture: a(n) = Sum_{k>=0} (-1)^(k-1)*binomial(A001222(n)-1, k)*binomial(A001221(n)-1+k, k), for n > 1. Verified for the first 100000 terms. - _Mats Granvik_, Sep 08 2018
%F A008683 From _Peter Bala_, Mar 15 2019: (Start)
%F A008683 Sum_{n >= 1} mu(n)*x^n/(1 + x^n) = x - 2*x^2. See, for example, Pólya and Szegő, Part V111, Chap. 1, No. 71.
%F A008683 Sum_{n >= 1} (-1)^(n+1)*mu(n)*x^n/(1 - x^n) = x + 2*(x^2 + x^4 + x^8 + x^16 + ...).
%F A008683 Sum_{n >= 1} (-1)^(n+1)*mu(n)*x^n/(1 + x^n) = x - 2*(x^4 + x^8 + x^16 + x^32 + ...).
%F A008683 Sum_{n >= 1} |mu(n)|*x^n/(1 - x^n) = Sum_{n >= 1} (2^w(n))*x^n, where w(n) is the number of different prime factors of n (Hardy and Wright, Chapter XVI, Theorem 264).
%F A008683 Sum_{n odd} |mu(n)|*x^n/(1 + x^(2*n)) = Sum_{n in S_1} (2^w_1(n))*x^n, where S_1 = {1, 5, 13, 17, 25, 29, ...} is the multiplicative semigroup of positive integers generated by 1 and the primes p = 1 (mod 4), and w_1(n) is the number of different prime factors p = 1 (mod 4) of n.
%F A008683 Sum_{n odd} (-1)^((n-1)/2)*mu(n)*x^n/(1 - x^(2*n)) = Sum_{n in S_3} (2^w_3(n))*x^n, where S_3 = {1, 3, 7, 9, 11, 19, 21, ...} is the multiplicative semigroup of positive integers generated by 1 and the primes p = 3 (mod 4), and where w_3(n) is the number of different prime factors p = 3 (mod 4) of n. (End)
%F A008683 G.f. A(x) satisfies: A(x) = x - Sum_{k>=2} A(x^k). - _Ilya Gutkovskiy_, May 11 2019
%F A008683 a(n) = sign(A023900(n)) * [A007947(n) = n] where [] is the Iverson bracket. - _I. V. Serov_, May 15 2019
%F A008683 a(n) = Sum_{k = 1..n} gcd(k, n)*a(gcd(k, n)) = Sum_{d divides n} a(d)*d*phi(n/d). - _Peter Bala_, Jan 16 2024
%e A008683 G.f. = x - x^2 - x^3 - x^5 + x^6 - x^7 + x^10 - x^11 - x^13 + x^14 + x^15 + ...
%p A008683 with(numtheory): A008683 := n->mobius(n);
%p A008683 with(numtheory): [ seq(mobius(n), n=1..100) ];
%p A008683 # Note that older versions of Maple define mobius(0) to be -1.
%p A008683 # This is unwise! Moebius(0) is better left undefined.
%p A008683 with(numtheory):
%p A008683 mu:= proc(n::posint) option remember; `if`(n=1, 1,
%p A008683        -add(mu(d), d=divisors(n) minus {n}))
%p A008683      end:
%p A008683 seq(mu(n), n=1..100);  # _Alois P. Heinz_, Aug 13 2008
%t A008683 Array[ MoebiusMu, 100]
%t A008683 (* Second program: *)
%t A008683 m = 100; A[_] = 0;
%t A008683 Do[A[x_] = x - Sum[A[x^k], {k, 2, m}] + O[x]^m // Normal, {m}];
%t A008683 CoefficientList[A[x]/x, x] (* _Jean-François Alcover_, Oct 20 2019, after _Ilya Gutkovskiy_ *)
%o A008683 (Axiom) [moebiusMu(n) for n in 1..100]
%o A008683 (Magma) [ MoebiusMu(n) : n in [1..100]];
%o A008683 (PARI) a=n->if(n<1,0,moebius(n));
%o A008683 (PARI) {a(n) = if( n<1, 0, direuler( p=2, n, 1 - X)[n])};
%o A008683 (PARI) list(n)=my(v=vector(n,i,1)); forprime(p=2, sqrtint(n), forstep(i=p, n, p, v[i]*=-1); forstep(i=p^2, n, p^2, v[i]=0)); forprime(p=sqrtint(n)+1, n, forstep(i=p, n, p, v[i]*=-1)); v \\ _Charles R Greathouse IV_, Apr 27 2012
%o A008683 (Maxima) A008683(n):=moebius(n)$ makelist(A008683(n),n,1,30); /* _Martin Ettl_, Oct 24 2012 */
%o A008683 (Haskell)
%o A008683 import Math.NumberTheory.Primes.Factorisation (factorise)
%o A008683 a008683 = mu . snd . unzip . factorise where
%o A008683 mu [] = 1; mu (1:es) = - mu es; mu (_:es) = 0
%o A008683 -- _Reinhard Zumkeller_, Dec 13 2015, Oct 09 2013
%o A008683 (Haskell)
%o A008683 a008683 1 = 1
%o A008683 a008683 n = - sum [a008683 d | d <- [1..(n-1)], n `mod` d == 0]
%o A008683 -- _Harry Richman_, Jun 13 2025
%o A008683 (Sage)
%o A008683 @cached_function
%o A008683 def mu(n):
%o A008683     if n < 2: return n
%o A008683     return -sum(mu(d) for d in divisors(n)[:-1])
%o A008683 # Changing the sign of the sum gives the number of ordered factorizations of n A074206.
%o A008683 print([mu(n) for n in (1..96)])  # _Peter Luschny_, Dec 26 2016
%o A008683 (Python)
%o A008683 from sympy import mobius
%o A008683 print([mobius(i) for i in range(1, 101)])  # _Indranil Ghosh_, Mar 18 2017
%Y A008683 Variants of a(n) are A178536, A181434, A181435.
%Y A008683 Cf. A000010, A001221, A008966, A007423, A080847, A002321 (partial sums), A069158, A055615, A129360, A140579, A140664, A140254, A143104, A152902, A206706, A063524, A007427, A007428, A124010, A073776, A074206, A132971, A156552.
%Y A008683 Cf. A059956 (Dgf at s=2), A088453 (Dgf at s=3), A215267 (Dgf at s=4), A343308 (Dgf at s=5).
%K A008683 core,sign,easy,mult,nice,changed
%O A008683 1,1
%A A008683 _N. J. A. Sloane_