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

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: