## Mertens’ Conjecture

### January 24, 2020

We begin with a function to compute Moebius(n). Our `factors` function uses a 2,3,5-wheel; you can use something more complex if you are ambitious:

```(define (factors n)
(let ((wheel (vector 1 2 2 4 2 4 2 4 6 2 6)))
(let loop ((n n) (f 2) (w 0) (fs (list)))
(if (< n (* f f)) (reverse (cons n fs))
(if (zero? (modulo n f))
(loop (/ n f) f w (cons f fs))
(loop n (+ f (vector-ref wheel w))
(if (= w 10) 3 (+ w 1)) fs))))))```

```(define (moebius n)
; (-1)^k if n has k factors,
; or 0 if any factors duplicated
(if (< n 1) (error 'moebius "must be positive")
(if (= n 1) 1
(let loop ((m 1) (f 0) (fs (factors n)))
(if (null? fs) m
(if (= f (car fs)) 0
(loop (- m) (car fs) (cdr fs))))))))```

Then the Mertens function is simple:

```(define (mertens n)
(do ((k 1 (+ k 1))
(m 0 (+ m (moebius k))))
((< n k) m)))```

Here are some of the OEIS sequences:

```(define (a008683 n) ; moebius function
(map moebius (range 1 (+ n 1))))

> (a008683 25)
(1 -1 -1 0 -1 1 -1 0 0 1 -1 0 -1 1 1 0 -1 0 -1 0 1 1 -1 0 0)```
```(define (a002321 n) ; mertens function
(map mertens (range 1 (+ n 1))))

> (a002321 20)
(1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3)```
```(define (a028442 n)
; numbers k such that mertens(k) == 0
(let loop ((k 1) (M 0) (ks (list)))
(if (< n k) (reverse ks)
(let* ((m (moebius k)) (M (+ M m)))
(if (zero? M)
(loop (+ k 1) M (cons k ks))
(loop (+ k 1) M ks))))))

> (a028442 200)
(2 39 40 58 65 93 101 145 149 150 159 160 163 164 166)```
```(define (a100306 n)
; numbers k such that moebius(k) == mertens(k)
(let loop ((k 1) (M 0) (ks (list)))
(if (< n k) (reverse ks)
(let* ((m (moebius k)) (M (+ M m)))
(if (= m M)
(loop (+ k 1) M (cons k ks))
(loop (+ k 1) M ks))))))

> (a100306 200)
(1 3 40 41 59 66 94 102 146 150 151 160 161 164 165 167)```

You can run the program at https://ideone.com/eYYkdG.

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.