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

1, 0, -1, -1, -2, -1, -2, -2, -2, -1, -2, -2, -3, -2, -1, -1, -2, -2, -3, -3, -2, -1, -2, -2, -2, -1, -1, -1, -2, -3, -4, -4, -3, -2, -1, -1, -2, -1, 0, 0, -1, -2, -3, -3, -3, -2, -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

Offset: 1

Author

N. J. A. Sloane

Keywords

• sign
• easy
• nice

Comments

Partial sums of the Moebius function A008683.

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

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

All integers appear infinitely often in this sequence. - Charles R Greathouse IV, Aug 06 2012

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

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

Examples

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

References

• E. Landau, Vorlesungen über Zahlentheorie, Chelsea, NY, Vol. 2, p. 157.
• D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No. 105, National Research Council, Washington, DC, 1941, pp. 7-10.
• F. Mertens, "Über eine zahlentheoretische Funktion", Akademie Wissenschaftlicher Wien Mathematik-Naturlich Kleine Sitzungsber, IIa 106, (1897), p. 761-830.
• D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section VI.1.
• Biswajyoti Saha and Ayyadurai Sankaranarayanan, On estimates of the Mertens function, International Journal of Number Theory, Vol. 15, No. 02 (2019), pp. 327-337.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• J. von zur Gathen and J. Gerhard, Modern Computer Algebra, Cambridge, 1999, see p. 482.

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• Michel Balazard and Anne De Roton, Sur un critère de Baez-Duarte pour l'hypothèse de Riemann, International Journal of Number TheoryVol. 06, No. 04, pp. 883-903 (2010). arXiv preprint (2008). arXiv:0812.1689 [math.NT]
• B. Boncompagni, Selected values of the Mertens function.
• O. Bordelles, Some Explicit Estimates for the Mobius Function , J. Int. Seq. 18 (2015), 15.11.1.
• G. J. Chaitin, Thoughts on the Riemann hypothesis, arXiv:math/0306042 [math.HO], 2003.
• J. B. Conrey, The Riemann Hypothesis, Notices Amer. Math. Soc., 50 (No. 3, March 2003), 341-353. See p. 347.
• Marc Deléglise and Joël Rivat, Computing the summation of the Mobius function, Experiment. Math. 5:4 (1996), pp. 291-295.
• F. Dress, Fonction sommatoire de la fonction de Moebius. 1. Majorations expérimentales, Experiment. Math. , Volume 2, Issue 2 (1993), 89-98.
• F. Dress and M. El Marraki, Fonction sommatoire de la fonction de Moebius. 2. Majorations asymptotiques élémentaires, Experiment. Math., Volume 2, Issue 2 (1993), 99-112.
• M. El-Marraki, Fonction sommatoire de la fonction mu de Möbius, 3. Majorations asymptotiques effectives fortes, Journal de théorie des nombres de Bordeaux, Tome 7 (1995) no. 2 , p. 407-433.
• Brady Haran, Holly Krieger, and Pete McPartlan, A Prime Surprise (Mertens Conjecture), Numberphile video (2019).
• Harald A. Helfgott and Lola Thompson, Summing mu(n): a faster elementary algorithm, arXiv:2101.08773 [math.NT], 2021.
• Greg Hurst, Computations of the Mertens function and improved bounds on the Mertens conjecture, arXiv:1610.08551 [math.NT], 2016-2017.
• MathOverflow, Is Mertens function negatively biased?, posted May 28, 2012.
• MathOverflow, Approximations to the Mertens function, posted Jul 08 2015.
• Nathan Ng, The distribution of the summatory function of the Möbius function, Proc. London Math. Soc. (3) 89 (2004), no. 2, 361-389; arXiv:math/0310381 [math.NT], 2003.
• A. M. Odlyzko and H. J. J. te Riele, Disproof of the Mertens conjecture, J. reine angew. Math., 357 (1985), pp. 138-160.
• Lowell Schoenfeld, An improved estimate for the summatory function of the Möbius function, Acta Arithmetica 15:3 (1969), pp. 221-233.
• Kannan Soundararajan, Partial sums of the Möbius function, Journal für die reine und angewandte Mathematik, Vol. 631 (2009), pp. 141-152. arXiv:0705.0723 [math.NT], 2007-2008.
• Robert Daublebsky 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.
• Robert Daublebsky von Sterneck, Bemerkung über die Summierung einiger zahlen-theoretischen Functionen, Monatshefte für Mathematik und Physik 9(1) (1898), 43-45. [He proves the inequality |a(n)| <= (n/9) + 8.]
• Paul Tarau, Towards a generic view of primality through multiset decompositions of natural numbers, Theoretical Computer Science, Volume 537, Jun 05 2014, Pages 105-124.
• 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.
• G. Villemin's Almanac of Numbers, Nombres de Moebius et de Mertens.
• Eric Weisstein's World of Mathematics, Mertens Function
• Eric Weisstein's World of Mathematics, Redheffer Matrix.
• Wikipedia, Mertens function.
• H. S. Wilf, A Greeting; and a view of Riemann's Hypothesis, Amer. Math. Monthly, 94:1 (1987), 3-6.

Crossrefs

Cf. A008683, A059571, A084237, A209802.

First column of A134541.

First column of A179287.

Programs

Haskell

import Data.List (genericIndex)
a002321 n = genericIndex a002321_list (n-1)
a002321_list = scanl1 (+) a008683_list
-- Reinhard Zumkeller, Jul 14 2014, Dec 26 2012

Magma

[&+[MoebiusMu(k): k in [1..n]]: n in [1..81]]; // Bruno Berselli, Jul 12 2021

Maple

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

Mathematica

Rest[ FoldList[ #1+#2&, 0, Array[ MoebiusMu, 100 ] ] ]
Accumulate[Array[MoebiusMu,100]] (* Harvey P. Dale, May 11 2011 *)

PARI

a(n) = sum( k=1, n, moebius(k))

PARI

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

PARI

a(n)=my(s); forsquarefree(k=1,n, s+=moebius(k)); s \\ Charles R Greathouse IV, Jan 08 2018

Python

from sympy import mobius
def M(n): return sum(mobius(k) for k in range(1,n + 1))
print([M(n) for n in range(1, 151)]) # Indranil Ghosh, Mar 18 2017

Python

from functools import lru_cache
@lru_cache(maxsize=None)
def A002321(n):
    if n == 0:
        return 0
    c, j = n, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*A002321(k1)
        j, k1 = j2, n//j2
    return j-c # Chai Wah Wu, Mar 30 2021

Formula

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

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

a(n)+2 = A192763(n,1) for n>1, and A192763(1,k) for k>1 (conjecture). - Mats Granvik, Jul 10 2011

Sum_{k = 1..n} a(floor(n/k)) = 1. - David W. Wilson, Feb 27 2012

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

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

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

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