cp's OEIS Frontend

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

%I A002321 M0102 N0038 #251 Feb 16 2025 08:32:25
%S A002321 1,0,-1,-1,-2,-1,-2,-2,-2,-1,-2,-2,-3,-2,-1,-1,-2,-2,-3,-3,-2,-1,-2,
%T A002321 -2,-2,-1,-1,-1,-2,-3,-4,-4,-3,-2,-1,-1,-2,-1,0,0,-1,-2,-3,-3,-3,-2,
%U A002321 -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 A002321 Mertens's function: Sum_{k=1..n} mu(k), where mu is the Moebius function A008683.
%C A002321 Partial sums of the Moebius function A008683.
%C A002321 Also determinant of n X n (0,1) matrix defined by A(i,j)=1 if j=1 or i divides j.
%C A002321 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 A002321 All integers appear infinitely often in this sequence. - _Charles R Greathouse IV_, Aug 06 2012
%C A002321 Soundararajan proves that, on the Riemann Hypothesis, a(n) << sqrt(n) exp(sqrt(log n)*(log log n)^14), sharpening the well-known equivalence. - _Charles R Greathouse IV_, Jul 17 2015
%C A002321 Balazard & De Roton improve this (on the Riemann Hypothesis) to a(n) << sqrt(n) exp(sqrt(log n)*(log log n)^k) for any k > 5/2, where the implied constant in the Vinogradov symbol depends on k. Saha & Sankaranarayanan reduce the exponent to 5/4 on additional hypotheses. - _Charles R Greathouse IV_, Feb 02 2023
%D A002321 E. Landau, Vorlesungen über Zahlentheorie, Chelsea, NY, Vol. 2, p. 157.
%D A002321 D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No. 105, National Research Council, Washington, DC, 1941, pp. 7-10.
%D A002321 F. Mertens, "Über eine zahlentheoretische Funktion", Akademie Wissenschaftlicher Wien Mathematik-Naturlich Kleine Sitzungsber, IIa 106, (1897), p. 761-830.
%D A002321 D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section VI.1.
%D A002321 Biswajyoti Saha and Ayyadurai Sankaranarayanan, On estimates of the Mertens function, International Journal of Number Theory, Vol. 15, No. 02 (2019), pp. 327-337.
%D A002321 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A002321 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A002321 J. von zur Gathen and J. Gerhard, Modern Computer Algebra, Cambridge, 1999, see p. 482.
%H A002321 T. D. Noe, <a href="/A002321/b002321.txt">Table of n, a(n) for n = 1..10000</a>
%H A002321 Michel Balazard and Anne De Roton, <a href="https://arxiv.org/abs/0812.1689">Sur un critère de Baez-Duarte pour l'hypothèse de Riemann</a>, International Journal of Number TheoryVol. 06, No. 04, pp. 883-903 (2010). arXiv preprint (2008). arXiv:0812.1689 [math.NT]
%H A002321 B. Boncompagni, <a href="http://mertens.redgolpe.com">Selected values of the Mertens function</a>.
%H A002321 O. Bordelles, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Bordelles2/bordelles21.html">Some Explicit Estimates for the Mobius Function </a>, J. Int. Seq. 18 (2015), 15.11.1.
%H A002321 G. J. Chaitin, <a href="https://arxiv.org/abs/math/0306042">Thoughts on the Riemann hypothesis</a>, arXiv:math/0306042 [math.HO], 2003.
%H A002321 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 A002321 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 A002321 F. Dress, <a href="https://projecteuclid.org/euclid.em/1048516214">Fonction sommatoire de la fonction de Moebius. 1. Majorations expérimentales</a>, Experiment. Math. , Volume 2, Issue 2 (1993), 89-98.
%H A002321 F. Dress and M. El Marraki, <a href="https://projecteuclid.org/euclid.em/1048516215">Fonction sommatoire de la fonction de Moebius. 2. Majorations asymptotiques élémentaires</a>, Experiment. Math., Volume 2, Issue 2 (1993), 99-112.
%H A002321 M. El-Marraki, <a href="http://www.numdam.org/item?id=JTNB_1995__7_2_407_0">Fonction sommatoire de la fonction mu de Möbius, 3. Majorations asymptotiques effectives fortes</a>, Journal de théorie des nombres de Bordeaux, Tome 7 (1995) no. 2 , p. 407-433.
%H A002321 Brady Haran, Holly Krieger, and Pete McPartlan, <a href="https://www.youtube.com/watch?v=uvMGZb0Suyc">A Prime Surprise (Mertens Conjecture)</a>, Numberphile video (2019).
%H A002321 Harald A. Helfgott and Lola Thompson, <a href="https://arxiv.org/abs/2101.08773">Summing mu(n): a faster elementary algorithm</a>, arXiv:2101.08773 [math.NT], 2021.
%H A002321 Greg Hurst, <a href="https://arxiv.org/abs/1610.08551">Computations of the Mertens function and improved bounds on the Mertens conjecture</a>, arXiv:1610.08551 [math.NT], 2016-2017.
%H A002321 MathOverflow, <a href="http://mathoverflow.net/questions/98174">Is Mertens function negatively biased?</a>, posted May 28, 2012.
%H A002321 MathOverflow, <a href="http://mathoverflow.net/questions/211095">Approximations to the Mertens function</a>, posted Jul 08 2015.
%H A002321 Nathan Ng, <a href="https://arxiv.org/abs/math/0310381">The distribution of the summatory function of the Möbius function</a>, Proc. London Math. Soc. (3) 89 (2004), no. 2, 361-389; arXiv:math/0310381 [math.NT], 2003.
%H A002321 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 A002321 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 A002321 Kannan Soundararajan, <a href="http://arxiv.org/abs/0705.0723">Partial sums of the Möbius function</a>, Journal für die reine und angewandte Mathematik, Vol. 631 (2009), pp. 141-152. arXiv:0705.0723 [math.NT], 2007-2008.
%H A002321 Robert Daublebsky von Sterneck, <a href="https://www.zobodat.at/pdf/SBAWW_106_2a_0835-1024.pdf">Empirische Untersuchung ueber den Verlauf der zahlentheoretischer Function sigma(n) = Sum_{x=1..n} mu(x) im Intervalle von 0 bis 150 000</a>, Sitzungsbericht der Kaiserlichen Akademie der Wissenschaften Wien, Mathematisch-Naturwissenschaftlichen Klasse, 2a, v. 106, 1897, 835-1024.
%H A002321 Robert Daublebsky von Sterneck, <a href="https://doi.org/10.1007/BF01707854">Bemerkung über die Summierung einiger zahlen-theoretischen Functionen</a>, Monatshefte für Mathematik und Physik 9(1) (1898), 43-45. [He proves the inequality |a(n)| <= (n/9) + 8.]
%H A002321 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 A002321 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 A002321 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 A002321 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MertensFunction.html">Mertens Function</a>
%H A002321 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/RedhefferMatrix.html">Redheffer Matrix</a>.
%H A002321 Wikipedia, <a href="http://en.wikipedia.org/wiki/Mertens_function">Mertens function</a>.
%H A002321 H. S. Wilf, <a href="https://www.jstor.org/stable/2323497">A Greeting; and a view of Riemann's Hypothesis</a>, Amer. Math. Monthly, 94:1 (1987), 3-6.
%F A002321 Assuming the Riemann hypothesis, a(n) = O(x^(1/2 + eps)) for every eps > 0 (Littlewood - see Landau p. 161).
%F A002321 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 and Sep 23 2010
%F A002321 a(n)+2 = A192763(n,1) for n>1, and A192763(1,k) for k>1 (conjecture). - _Mats Granvik_, Jul 10 2011
%F A002321 Sum_{k = 1..n} a(floor(n/k)) = 1. - _David W. Wilson_, Feb 27 2012
%F A002321 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 A002321 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 A002321 Schoenfeld proves that |a(n)| < 5.3*n/(log n)^(10/9) for n > 1. - _Charles R Greathouse IV_, Jan 17 2018
%F A002321 G.f. A(x) satisfies: A(x) = (1/(1 - x)) * (x - Sum_{k>=2} (1 - x^k) * A(x^k)). - _Ilya Gutkovskiy_, Aug 11 2021
%e A002321 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 A002321 with(numtheory); A002321 := n->add(mobius(k),k=1..n);
%t A002321 Rest[ FoldList[ #1+#2&, 0, Array[ MoebiusMu, 100 ] ] ]
%t A002321 Accumulate[Array[MoebiusMu,100]] (* _Harvey P. Dale_, May 11 2011 *)
%o A002321 (PARI) a(n) = sum( k=1, n, moebius(k))
%o A002321 (PARI) a(n) = if( n<1, 0, matdet( matrix(n, n, i, j, j==1 || 0==j%i)))
%o A002321 (PARI) a(n)=my(s); forsquarefree(k=1,n, s+=moebius(k)); s \\ _Charles R Greathouse IV_, Jan 08 2018
%o A002321 (Haskell)
%o A002321 import Data.List (genericIndex)
%o A002321 a002321 n = genericIndex a002321_list (n-1)
%o A002321 a002321_list = scanl1 (+) a008683_list
%o A002321 -- _Reinhard Zumkeller_, Jul 14 2014, Dec 26 2012
%o A002321 (Python)
%o A002321 from sympy import mobius
%o A002321 def M(n): return sum(mobius(k) for k in range(1,n + 1))
%o A002321 print([M(n) for n in range(1, 151)]) # _Indranil Ghosh_, Mar 18 2017
%o A002321 (Python)
%o A002321 from functools import lru_cache
%o A002321 @lru_cache(maxsize=None)
%o A002321 def A002321(n):
%o A002321     if n == 0:
%o A002321         return 0
%o A002321     c, j = n, 2
%o A002321     k1 = n//j
%o A002321     while k1 > 1:
%o A002321         j2 = n//k1 + 1
%o A002321         c += (j2-j)*A002321(k1)
%o A002321         j, k1 = j2, n//j2
%o A002321     return j-c # _Chai Wah Wu_, Mar 30 2021
%o A002321 (Magma) [&+[MoebiusMu(k): k in [1..n]]: n in [1..81]]; // _Bruno Berselli_, Jul 12 2021
%Y A002321 Cf. A008683, A059571, A084237, A209802.
%Y A002321 First column of A134541.
%Y A002321 First column of A179287.
%K A002321 sign,easy,nice
%O A002321 1,5
%A A002321 _N. J. A. Sloane_