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.
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, -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, 0, -1, 1, 0, 0, 1, -1, -1, 0, 1, -1, -1, 0, -1, 1, 0, 0, 1, -1
Offset: 1
Examples
G.f. = x - x^2 - x^3 - x^5 + x^6 - x^7 + x^10 - x^11 - x^13 + x^14 + x^15 + ...
References
- T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 24.
- L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 161, #16.
- G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, Cambridge, University Press, 1940, pp. 64-65.
- G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, th. 262 and 287.
- 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
- G. Pólya and G. Szegő, Problems and Theorems in Analysis Volume II. Springer_Verlag 1976.
- James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 98-99.
Links
- Daniel Forgues, Table of n, a(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, p. 826.
- All Angles, What is the Moebius function?, video, 2024.
- Joerg Arndt, Matters Computational (The Fxtbook), pp. 705-707.
- Yu Hin (Gary) Au, Decompositions of Unit Hypercubes and the Reversion of a Generalized Möbius Series, arXiv:2205.03680 [math.CO], 2022.
- Olivier Bordellès, Some Explicit Estimates for the Mobius Function , J. Int. Seq. 18 (2015) 15.11.1
- G. J. Chaitin, Thoughts on the Riemann hypothesis arXiv:math/0306042 [math.HO], 2003.
- Michael Coons and Peter Borwein, Transcendence of Power Series for Some Number Theoretic Functions, arXiv:0806.1563 [math.NT], 2008.
- Marc Deléglise and Joël Rivat, Computing the summation of the Mobius function, Experiment. Math. 5:4 (1996), pp. 291-295.
- Tom Edgar, Posets and Möbius Inversion, slides, (2008).
- Mats Granvik, Inverse of a triangular matrix using determinants, Inverse of a triangular matrix using matrix multiplication, Inverse of a triangular matrix as a binomial series, The ordinary generating function for the Mobius function.
- Keith Matthews, Factorizing n and calculating phi(n),omega(n),d(n),sigma(n) and mu(n).
- A. F. Möbius, Über eine besondere Art von Umkehrung der Reihen. Journal für die reine und angewandte Mathematik 9 (1832), 105-123.
- Ed Pegg Jr., The Mobius function (and squarefree numbers).
- Anders Björner and Richard P. Stanley, A combinatorial miscellany.
- Paul Tarau, Emulating Primality with Multiset Representations of Natural Numbers, in Theoretical Aspects Of Computing, ICTAC 2011, Lecture Notes in Computer Science, 2011, Volume 6916/2011, 218-238.
- Paul Tarau, Towards a generic view of primality through multiset decompositions of natural numbers, Theoretical Computer Science, Volume 537, Jun 05 2014, pp. 105-124.
- Gerard Villemin's Almanac of Numbers, Nombres de Moebius et de Mertens.
- Eric Weisstein's World of Mathematics, Moebius Function.
- Eric Weisstein's World of Mathematics, Redheffer Matrix.
- Wikipedia, Moebius function.
- Index entries for "core" sequences
- Index entries for sequences computed from exponents in factorization of n
Crossrefs
Programs
-
Axiom
[moebiusMu(n) for n in 1..100]
-
Haskell
import Math.NumberTheory.Primes.Factorisation (factorise) a008683 = mu . snd . unzip . factorise where mu [] = 1; mu (1:es) = - mu es; mu (_:es) = 0 -- Reinhard Zumkeller, Dec 13 2015, Oct 09 2013
-
Haskell
a008683 1 = 1 a008683 n = - sum [a008683 d | d <- [1..(n-1)], n `mod` d == 0] -- Harry Richman, Jun 13 2025
-
Magma
[ MoebiusMu(n) : n in [1..100]];
-
Maple
with(numtheory): A008683 := n->mobius(n); with(numtheory): [ seq(mobius(n), n=1..100) ]; # Note that older versions of Maple define mobius(0) to be -1. # This is unwise! Moebius(0) is better left undefined. with(numtheory): mu:= proc(n::posint) option remember; `if`(n=1, 1, -add(mu(d), d=divisors(n) minus {n})) end: seq(mu(n), n=1..100); # Alois P. Heinz, Aug 13 2008
-
Mathematica
Array[ MoebiusMu, 100] (* Second program: *) m = 100; A[_] = 0; Do[A[x_] = x - Sum[A[x^k], {k, 2, m}] + O[x]^m // Normal, {m}]; CoefficientList[A[x]/x, x] (* Jean-François Alcover, Oct 20 2019, after Ilya Gutkovskiy *) -
Maxima
A008683(n):=moebius(n)$ makelist(A008683(n),n,1,30); /* Martin Ettl, Oct 24 2012 */
-
PARI
a=n->if(n<1,0,moebius(n));
-
PARI
{a(n) = if( n<1, 0, direuler( p=2, n, 1 - X)[n])}; -
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
-
Python
from sympy import mobius print([mobius(i) for i in range(1, 101)]) # Indranil Ghosh, Mar 18 2017
-
Sage
@cached_function def mu(n): if n < 2: return n return -sum(mu(d) for d in divisors(n)[:-1]) # Changing the sign of the sum gives the number of ordered factorizations of n A074206. print([mu(n) for n in (1..96)]) # Peter Luschny, Dec 26 2016
Formula
Sum_{d|n} mu(d) = 1 if n = 1 else 0.
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.
In particular, Sum_{n > 0} mu(n)/n = 0. - Franklin T. Adams-Watters, Jun 20 2014
phi(n) = Sum_{d|n} mu(d)*n/d.
Multiplicative with a(p^e) = -1 if e = 1; 0 if e > 1. - David W. Wilson, Aug 01 2001
abs(a(n)) = Sum_{d|n} 2^A001221(d)*a(n/d). - Benoit Cloitre, Apr 05 2002
Sum_{d|n} (-1)^(n/d)*mobius(d) = 0 for n > 2. - Emeric Deutsch, Jan 28 2005
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
Dirichlet generating function for the absolute value: zeta(s)/zeta(2s). - Franklin T. Adams-Watters, Sep 11 2005
mu(n) = A129360(n) * (1, -1, 0, 0, 0, ...). - Gary W. Adamson, Apr 17 2007
mu(n) = -Sum_{d < n, d|n} mu(d) if n > 1 and mu(1) = 1. - Alois P. Heinz, Aug 13 2008
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
Product_{n >= 1} (1-x^n)^(-a(n)/n) = exp(x) (product form of the exponential function). - Joerg Arndt, May 13 2011
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
mu(n) = Sum_{k=1..n} A191898(n,k)*exp(-i*2*Pi*k/n)/n. (conjecture). - Mats Granvik, Nov 20 2011
Sum_{k=1..n} a(k)*floor(n/k) = 1 for n >= 1. - Peter Luschny, Feb 10 2012
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
Multiplicative with a(p^e) = binomial(1, e) * (-1)^e. - Enrique Pérez Herrero, Jan 19 2013
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
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
a(n) = Kronecker delta of A001221(n) and A001222(n) (which is A008966) multiplied by A008836(n). - Eric Desbiaux, Mar 15 2017
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
From Peter Bala, Mar 15 2019: (Start)
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.
Sum_{n >= 1} (-1)^(n+1)*mu(n)*x^n/(1 - x^n) = x + 2*(x^2 + x^4 + x^8 + x^16 + ...).
Sum_{n >= 1} (-1)^(n+1)*mu(n)*x^n/(1 + x^n) = x - 2*(x^4 + x^8 + x^16 + x^32 + ...).
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).
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.
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)
G.f. A(x) satisfies: A(x) = x - Sum_{k>=2} A(x^k). - Ilya Gutkovskiy, May 11 2019
a(n) = sign(A023900(n)) * [A007947(n) = n] where [] is the Iverson bracket. - I. V. Serov, May 15 2019
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
Comments