login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008683 Moebius (or Mobius) function mu(n). mu(1) = 1; mu(n) = (-1)^k if n is the product of k different primes; otherwise mu(n) = 0. 435
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Moebius inversion: f(n) = Sum_{ d divides n } g(d) for all n <=> g(n) = Sum_{ d divides 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

See last sentence of abstract of Coons and Borwein: We give a new proof of Fatou's theorem: if an algebraic function has a power series expansion with bounded integer coefficients, then it must be a rational function. This result is applied to show that for any non-trivial completely multiplicative function from N to {-1,1), the series sum_{n=1 to infinity} f(n)z^n is transcendental over {Z}[z]; in particular, sum_{n=1 to infinity} lambda(n)z^n is transcendental, where lambda is Liouville's function. The transcendence of sum_{n=1 to infinity} mu(n)z^n is also proved. - Jonathan Vos Post, Jun 11 2008

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

Conjecture: a(n) = determinant of Redheffer matrix A143104 where T(n,n)=0. Verified for 50 first 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*A176890, B=A*A, C=B*B, D=C*C and so on, then the leftmost column in the last matrix converges to the Moebius function. - Mats Granvik, Gary W. Adamson, Apr 28 2010

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

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 57-th Dimension, 250 Milestones in the History of Mathematics", Sterling Publishing, 2009, p. 226. - Gary W. Adamson, Aug 13 2009

C. A. Pickover, The Math Book, Sterling, NY, 2009; see p. 226.

LINKS

N. J. A. Sloane and Daniel Forgues, Table of n, a(n) for n = 1..100000 (first 10000 terms from N. J. A. Sloane)

M. Abramowitz and I. 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

G. J. Chaitin, Thoughts on the Riemann hypothesis arXiv:math/0306042

Michael Coons and Peter Borwein, Transcendence of Power Series for Some Number Theoretic Functions, arXiv:0806.1563

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

K. Matthews, Factorizing n and calculating phi(n),omega(n),d(n),sigma(n) and mu(n)

Ed Pegg Jr., The Mobius function (and squarefree numbers)

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

P. Tarau, Towards a generic view of primality through multiset decompositions of natural numbers, Theoretical Computer Science, Volume 537, 5 June 2014, Pages 105-124.

G. Villemin's Almanac of Numbers, Nombres de Moebius et de Mertens

Eric Weisstein's World of Mathematics, Moebius Function

E. W. Weisstein, Redheffer Matrix.

Wikipedia, Moebius function

Index entries for "core" sequences

FORMULA

sum( d divides 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(mu(n)/n, n>=1) = 0. - Franklin T. Adams-Watters, Jun 20 2014

phi(n) = sum( d divides 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 divides n, 2^A001221(d)*a(n/d) ). - Benoit Cloitre, Apr 05 2002

sum(d divides 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 * (1, -1, 0, 0, 0,...). - Gary W. Adamson, Apr 17 2007

mu(n) = -sum( d<n,d divides n, mu(d) ) if n>1 and mu(1) = 1. - Alois P. Heinz, Aug 13 2008

a(n) = A174725-A174726. - 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) = 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 from i = 1 to k-1 of T(n-i,k-1)) - (sum from i = 1 to k-1 of T(n-i,k)). - Mats Granvik, Jun 12 2010

prod(n>=1, (1-x^n)^(-a(n)/n)) = exp(x) (product form of the exponential function). [Joerg Arndt, May 13 2011]

a(n) = sum(exp(2*pi*I*k/n), k=1..n and gcd(k,n)=1), 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)^(k=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

MAPLE

with(numtheory): A008683 := n->mobius(n);

with(numtheory): [ seq(mobius(n), n=1..100) ];

# Note that Maple defines 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, 0 ]

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

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

(Haskell)

a008683 = mu . a124010_row

   where mu [] = 1; mu (1:es) = - mu es; mu (_:es) = 0

-- Reinhard Zumkeller, Oct 09 2013

(Sage)

print [moebius(n) for n in (1..100)] # Peter Luschny, Nov 06 2014

CROSSREFS

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.

Sequence in context: A174600 A075437 A130047 * A008966 A080323 A157657

Adjacent sequences:  A008680 A008681 A008682 * A008684 A008685 A008686

KEYWORD

core,sign,easy,mult,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

Title of the Pickover reference changed by Robert G. Wilson v, Aug 24 2009

Removed (my) 12th formula - Mats Granvik

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified December 20 07:03 EST 2014. Contains 252241 sequences.