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

### 4 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 = +*(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]
```
3. Daniel said

Here’s a solution in Python, seemingly requiring excessive computation relative to @matthew’s sieve approach above.

```import itertools

def moebius(n):
last_factor = -1
parity = 1
x = 2
while x * x <= n:
if n % x == 0:
if x == last_factor:
return 0
parity *= -1
last_factor = x
n //= x
else:
x += 1 + (x & 1)
return 0 if n == last_factor else -parity

def merten():
return itertools.accumulate((moebius(x) for x in itertools.count(2)), initial=1)

print(list(itertools.islice((x for x in merten()), 20)))
```

Output:

```[1, 0, -1, -1, -2, -1, -2, -2, -2, -1, -2, -2, -3, -2, -1, -1, -2, -2, -3, -3]
```
4. matthew said

Similar to finding primes with the sieve of Eratosthenes compared with checking all numbers with trial division.