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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002321 Mertens's function: Sum_{k=1..n} mu(k), where mu is the Moebius function A008683.
(Formerly M0102 N0038)
107

%I M0102 N0038

%S 1,0,-1,-1,-2,-1,-2,-2,-2,-1,-2,-2,-3,-2,-1,-1,-2,-2,-3,-3,-2,-1,-2,

%T -2,-2,-1,-1,-1,-2,-3,-4,-4,-3,-2,-1,-1,-2,-1,0,0,-1,-2,-3,-3,-3,-2,

%U -3,-3,-3,-3,-2,-2,-3,-3,-2,-2,-1,0,-1,-1,-2,-1,-1,-1,0,-1,-2,-2,-1,-2,-3,-3,-4,-3,-3,-3,-2,-3,-4,-4,-4

%N Mertens's function: Sum_{k=1..n} mu(k), where mu is the Moebius function A008683.

%C Partial sums of the Moebius function A008683.

%C Also determinant of n X n (0,1) matrix defined by A(i,j)=1 if j=1 or i divides j.

%C Equals row sums of triangle A152901. - _Gary W. Adamson_, Dec 14 2008

%C The first positive value of Mertens's function for n > 1 is for n = 94. The graph seems to show a negative bias for the Mertens function which is eerily similar to the Chebyshev bias (described in A156749 and A156709). The purported bias seems to be empirically approximated to - (6 / Pi^2) * (sqrt(n) / 4) (by looking at the graph) (see MathOverflow link, May 28 2012) where 6 / Pi^2 = 1 / zeta(2) is the asymptotic density of squarefree numbers (the squareful numbers having Moebius mu of 0). This would be a growth pattern akin to the Chebyshev bias. - _Daniel Forgues_, Jan 23 2011

%C All integers appear infinitely often in this sequence. - _Charles R Greathouse IV_, Aug 06 2012

%C Soundararajan proves that, on the Riemann Hypothesis, a(n) << sqrt(x) exp(sqrt(log x)*(log log x)^14), sharpening the well-known equivalence. - _Charles R Greathouse IV_, Jul 17 2015

%D E. Landau, Vorlesungen über Zahlentheorie, Chelsea, NY, Vol. 2, p. 157.

%D D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No. 105, National Research Council, Washington, DC, 1941, pp. 7-10.

%D F. Mertens, "Über eine zahlentheoretische Funktion", Akademie Wissenschaftlicher Wien Mathematik-Naturlich Kleine Sitzungsber, IIa 106, (1897), p. 761-830.

%D D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section VI.1.

%D N. C. Ng, The summatory function of the Mobius function, Abstracts Amer. Math. Soc., 25 (No. 2, 2002), p. 339, #975-11-316.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D R. D. von Sterneck, Empirische Untersuchung ueber den Verlauf der zahlentheoretischer Function sigma(n) = Sum_{x=1..n} mu(x) im Intervalle von 0 bis 150 000, Sitzungsbericht der Kaiserlichen Akademie der Wissenschaften Wien, Mathematisch-Naturwissenschaftlichen Klasse, 2a, v. 106, 1897, 835-1024.

%D J. von zur Gathen and J. Gerhard, Modern Computer Algebra, Cambridge, 1999, see p. 482.

%H T. D. Noe, <a href="/A002321/b002321.txt">Table of n, a(n) for n = 1..10000</a>

%H B. Boncompagni, <a href="http://mertens.redgolpe.com">Selected values of the Mertens function</a>

%H G. J. Chaitin, <a href="http://arXiv.org/abs/math.HO/0306042"> [math/0306042] Thoughts on the Riemann hypothesis</a>

%H J. B. Conrey, <a href="http://www.ams.org/notices/200303/fea-conrey-web.pdf">The Riemann Hypothesis</a>, Notices Amer. Math. Soc., 50 (No. 3, March 2003), 341-353. See p. 347.

%H Marc Deléglise and Joël Rivat, <a href="http://projecteuclid.org/euclid.em/1047565447">Computing the summation of the Mobius function</a>, Experiment. Math. 5:4 (1996), pp. 291-295.

%H F. Dress, <a href="http://www.emis.de/journals/EM/expmath/volumes/2/2.html">Fonction sommatoire de la fonction de Moebius. 1. Majorations experimentales</a>.

%H F. Dress, <a href="http://www.emis.de/journals/EM/expmath/volumes/2/2.html">Fonction sommatoire de la fonction de Moebius. 2. Majorations asymptotiques elementaires</a>.

%H M. El-Marraki, <a href="http://www.emis.de/journals/JTNB/1995-2/jtnb7-2_english.html#jourelec">Fonction sommatoire de la fonction mu de Moebius</a>

%H MathOverflow, <a href="http://mathoverflow.net/questions/98174">Is Mertens function negatively biased?</a>, posted May 28, 2012

%H MathOverflow, <a href="http://mathoverflow.net/questions/211095">Approximations to the Mertens function</a>, posted Jul 08 2015

%H Nathan Ng, <a href="http://arxiv.org/abs/math/0310381v1">The distribution of the summatory function of the Möbius function</a>, arXiv:math/0310381 [math.NT], 2003.

%H A. M. Odlyzko and H. J. J. te Riele, <a href="http://www.dtc.umn.edu/~odlyzko/doc/zeta.html">Disproof of the Mertens conjecture</a>, J. reine angew. Math., 357 (1985), pp. 138-160.

%H Lowell Schoenfeld, <a href="https://eudml.org/doc/204893">An improved estimate for the summatory function of the Möbius function</a>, Acta Arithmetica 15:3 (1969), pp. 221-233.

%H Kannan Soundararajan, <a href="http://arxiv.org/abs/0705.0723">Partial sums of the Möbius function</a>, arXiv:0705.0723 [math.NT], 2007-2008.

%H Paul Tarau, <a href="http://dx.doi.org/10.1016/j.tcs.2014.04.025">Towards a generic view of primality through multiset decompositions of natural numbers</a>, Theoretical Computer Science, Volume 537, Jun 05 2014, Pages 105-124.

%H Paul Tarau, <a href="http://dx.doi.org/10.1007/978-3-642-23283-1_15">Emulating Primality with Multiset Representations of Natural Numbers</a>, in Theoretical Aspects Of Computing, ICTAC 2011, Lecture Notes in Computer Science, 2011, Volume 6916/2011, 218-238

%H G. Villemin's Almanac of Numbers, <a href="http://villemin.gerard.free.fr/TABLES/aaaFArit/MobiusMe.htm">Nombres de Moebius et de Mertens</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MertensFunction.html">Mertens Function</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RedhefferMatrix.html">Redheffer Matrix</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Mertens_function">Mertens function</a>

%F Assuming the Riemann hypothesis, a(n) = O(x^(1/2 + eps)) for every eps > 0 (Littlewood - see Landau p. 161).

%F Lambert series: Sum_{n >= 1} a(n)*(x^n/(1-x^n)-x^(n+1)/(1-x^(n+1))) = x and -1/x. - _Mats Granvik_, Sep 09 2010

%F a(n)+2 = A192763(n,1) for n>1, and A192763(1,k) for k>1 (conjecture). - _Mats Granvik_, Jul 10 2011

%F Sum_{k = 1..n} a(floor(n/k)) = 1. - _David W. Wilson_, Feb 27 2012

%F a(n) = Sum_{k = 1..n} tau_{-2}(k) * floor(n/k), where tau_{-2} is A007427. - _Enrique Pérez Herrero_, Jan 23 2013

%F a(n) = Sum_{k=1..A002088(n)} exp(2*Pi*i*A038566(k)/A038567(k-1)) where i is the imaginary unit. - _Eric Desbiaux_, Jul 31 2014

%F Schoenfeld proves that |a(n)| < 5.3*n/(log n)^(10/9) for n > 1. - _Charles R Greathouse IV_, Jan 17 2018

%e G.f. = x - x^3 - x^4 - 2*x^5 - x^6 - 2*x^7 - 2*x^8 - 2*x^9 - x^10 - 2*x^11 - 2*x^12 - ...

%p with(numtheory); A002321 := n->add(mobius(k),k=1..n);

%t Rest[ FoldList[ #1+#2&, 0, Array[ MoebiusMu, 100 ] ] ]

%t Accumulate[Array[MoebiusMu,100]] (* _Harvey P. Dale_, May 11 2011 *)

%t (* Conjectured recurrence (two combined recurrences): *)

%t t[n_, k_] := t[n, k] = If[And[n == 1, k == 1], 3, If[Or[And[n == 1, k == 2], And[n == 2, k == 1]], 2, If[n == 1, (-t[n, k - 1] - Sum[t[i, k], {i, 2, k - 1}])/(k + 1) + t[n, k - 1], If[k == 1, (-t[n - 1, k] - Sum[t[n, i], {i, 2, n - 1}])/(n + 1) + t[n - 1, k], If[n >= k, -Sum[t[n - i, k], {i, 1, k - 1}], -Sum[t[k - i, n], {i, 1, n - 1}]]]]]];

%t nn = 81;

%t MatrixForm[Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}]];

%t Table[t[1, k], {k, 1, nn}] - 2 (* _Mats Granvik_, Jul 10, 2011 *)

%o (PARI) a(n) = sum( k=1, n, moebius(k))

%o (PARI) a(n) = if( n<1, 0, matdet( matrix(n, n, i, j, j==1 || 0==j%i)))

%o (PARI) a(n)=my(s); forsquarefree(k=1,n, s+=moebius(k)); s \\ _Charles R Greathouse IV_, Jan 08 2018

%o (Haskell)

%o import Data.List (genericIndex)

%o a002321 n = genericIndex a002321_list (n-1)

%o a002321_list = scanl1 (+) a008683_list

%o -- _Reinhard Zumkeller_, Jul 14 2014, Dec 26 2012

%o (Python)

%o from sympy import mobius

%o def M(n): return sum([mobius(k) for k in xrange(1,n + 1)])

%o print [M(n) for n in xrange(1, 151)] # _Indranil Ghosh_, Mar 18 2017

%Y Cf. A008683, A059571, A152901, A209802.

%Y First column of A134541.

%Y First column of A179287.

%K sign,easy,nice

%O 1,5

%A _N. J. A. Sloane_

%E Cross reference (Aug 28 2010) deleted by _Mats Granvik_, Sep 11 2010

%E -1/x added to Lambert series by _Mats Granvik_, Sep 23 2010

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

License Agreements, Terms of Use, Privacy Policy .

Last modified February 24 12:59 EST 2018. Contains 299623 sequences. (Running on oeis4.)