Mertens’ Conjecture

January 24, 2020

Dr Holly Krieger discussed Mertens’ Conjecture on Numberphile yesterday:

Mertens’ Conjecture: The absolute value of the Mertens function M(n), computed as the sum for k from 1 to n of the Moebius function μ(k), is less than the square root of n. The Moebius function μ(n) is (-1)^k, where k is the number of prime factors of n, but 0 if n has any repeated prime factors.

The conjecture has been proved false, though no counter-examples are known. You can read more about Mertens’ Conjecture at MathWorld or Wikipedia.

Your task is to write a program to compute Mertens’ function M(n) and use it to explore some of the sequences at OEIS. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

2 Responses to “Mertens’ Conjecture”

  1. matthew said

    I’d have thought using some sort of sieve would be better for this.

  2. matthew said

    For example:

    import sympy
    import itertools
    
    def mobius(N):
        primes = sympy.primerange(2,N)
        a = [0]+[1]*(N-1)
        for p in primes:
            for i in range(p,N,p):
                a[i] = -a[i]
            for i in range(p*p,N,p*p):
                a[i] = 0
        return a
    
    def mertens(N): return itertools.accumulate(mobius(N))
    
    print(list(mobius(20)))
    # [0, 1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1]
    print(list(mertens(20)))
    # [0, 1, 0, -1, -1, -2, -1, -2, -2, -2, -1, -2, -2, -3, -2, -1, -1, -2, -2, -3]
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: