|
| |
|
|
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.
|
|
391
|
|
|
|
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). [From 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 O. Granvik, Jul 25 2008
Contribution 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. [From Gary W. Adamson, Dec 14 2008]
Contribution from Gary W. Adamson, Aug 13 2009: (Start)
[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". (End)
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. [From Mats Granvik, Gary W. Adamson, Apr 28 2010]
Equals row sums of triangle A176918 [From 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...[From Mats Granvik, Gary W. Adamson, Dec 06 2010]
|
|
|
REFERENCES
|
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, Tenth Printing, 1972, p. 826.
T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 24.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 161, #16.
Deleglise, Marc and Rivat, Joel, Computing the summation of the Mobius function. Experiment. Math. 5 (1996), no. 4, 291-295.
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. [From Gary W. Adamson, Aug 13 2009]
C. A. Pickover, The Math Book, Sterling, NY, 2009; see p. 226.
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, DOI: 10.1007/978-3-642-23283-1_15; http://www.springerlink.com/content/x0044261g7004717/.
|
|
|
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 [alternative scanned copy].
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, 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
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
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.
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. [From 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)). [From 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*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 */
|
|
|
CROSSREFS
|
Cf. A000010, A001221, A008966, A007423, A080847, A002321 (partial sums), A069158, A055615, A129360, A140579, A140664, A140254, A143104, A152902, A206706.
Variants of a(n) are: A178536, A181434, A181435.
Cf. A063524, A007427, A007428.
Sequence in context: A075437 A130047 A157657 * A008966 A080323 A069158
Adjacent sequences: A008680 A008681 A008682 * A008684 A008685 A008686
|
|
|
KEYWORD
|
core,sign,easy,mult,nice
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
I changed the title of the Pickover reference Robert G. Wilson v, Aug 24 2009
Replaced a geocities.com URL - R. J. Mathar, Oct 30 2009
Removed (my) 12th formula - Mats Granvik
|
|
|
STATUS
|
approved
|
| |
|
|
