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.
I’d have thought using some sort of sieve would be better for this.
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]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:
Similar to finding primes with the sieve of Eratosthenes compared with checking all numbers with trial division.