1,1

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.

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).

A008683 = A140579^(-1) * A140664. - Gary W. Adamson, May 20 2008

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

Equals row sums of triangle A144735 (the square of triangle A054533). - Gary W. Adamson, Sep 20 2008

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

From Mats Granvik, Dec 06 2008: (Start)

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.

"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)

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

Convolved with A152902 = A000027, the natural numbers. - Gary W. Adamson, Dec 14 2008

[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

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

Equals row sums of triangle A176918. - Gary W. Adamson, Apr 29 2010

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

From Richard L. Ollerton, May 08 2021: (Start)

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):

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.

Use of gcd(n,k)*lcm(n,k) = n*k provides further variations. (End)

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

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

N. J. A. Sloane and 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.

Joerg Arndt, Matters Computational (The Fxtbook), pp.705-707

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, Pages 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

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.

a(n) = A091219(A091202(n)).

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) = A174725(n) - A174726(n). - Mats Granvik, Mar 28 2010

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

a(n) = A132971(A156552(n)). - Antti Karttunen, May 30 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

G.f. = x - x^2 - x^3 - x^5 + x^6 - x^7 + x^10 - x^11 - x^13 + x^14 + x^15 + ...

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

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 *)

(AXIOM) [moebiusMu(n) for n in 1..100]

(MAGMA) [ MoebiusMu(n) : n in [1..100]];

(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

(Maxima) A008683(n):=moebius(n)$ makelist(A008683(n), n, 1, 30); /* Martin Ettl, Oct 24 2012 */

(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

(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

(Python)

from sympy import mobius

print([mobius(i) for i in range(1, 101)])  # Indranil Ghosh, Mar 18 2017

Variants of a(n) are A178536, A181434, A181435.

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.

Sequence in context: A130047 A293233 A302050 * A008966 A080323 A157657

Adjacent sequences:  A008680 A008681 A008682 * A008684 A008685 A008686

core,sign,easy,mult,nice

N. J. A. Sloane

approved