|
|
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.
|
|
1465
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
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).
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
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
[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
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
|
|
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 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.
|
|
LINKS
|
|
|
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.
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
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
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
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
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
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) = 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
|
|
EXAMPLE
|
G.f. = x - x^2 - x^3 - x^5 + x^6 - x^7 + x^10 - x^11 - x^13 + x^14 + x^15 + ...
|
|
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:
|
|
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}];
|
|
PROG
|
(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
(Haskell)
import Math.NumberTheory.Primes.Factorisation (factorise)
a008683 = mu . snd . unzip . factorise where
mu [] = 1; mu (1:es) = - mu es; mu (_:es) = 0
(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.
(Python)
from sympy import mobius
print([mobius(i) for i in range(1, 101)]) # Indranil Ghosh, Mar 18 2017
|
|
CROSSREFS
|
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.
|
|
KEYWORD
|
core,sign,easy,mult,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|