%I M0102 N0038 #250 May 20 2024 11:04:34
%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 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(n) exp(sqrt(log n)*(log log n)^14), sharpening the well-known equivalence. - _Charles R Greathouse IV_, Jul 17 2015
%C 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 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 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 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 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 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 B. Boncompagni, <a href="http://mertens.redgolpe.com">Selected values of the Mertens function</a>.
%H 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 G. J. Chaitin, <a href="https://arxiv.org/abs/math/0306042">Thoughts on the Riemann hypothesis</a>, arXiv:math/0306042 [math.HO], 2003.
%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="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 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 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 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 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 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 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="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 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>, Journal für die reine und angewandte Mathematik, Vol. 631 (2009), pp. 141-152. arXiv:0705.0723 [math.NT], 2007-2008.
%H 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 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 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>.
%H 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 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 and Sep 23 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
%F 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 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 *)
%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 range(1,n + 1))
%o print([M(n) for n in range(1, 151)]) # _Indranil Ghosh_, Mar 18 2017
%o (Python)
%o from functools import lru_cache
%o @lru_cache(maxsize=None)
%o def A002321(n):
%o if n == 0:
%o return 0
%o c, j = n, 2
%o k1 = n//j
%o while k1 > 1:
%o j2 = n//k1 + 1
%o c += (j2-j)*A002321(k1)
%o j, k1 = j2, n//j2
%o return j-c # _Chai Wah Wu_, Mar 30 2021
%o (Magma) [&+[MoebiusMu(k): k in [1..n]]: n in [1..81]]; // _Bruno Berselli_, Jul 12 2021
%Y Cf. A008683, A059571, A084237, A209802.
%Y First column of A134541.
%Y First column of A179287.
%K sign,easy,nice
%O 1,5
%A _N. J. A. Sloane_