Mertens function

Mertens function is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

The Mertens function M(x) is the count of square-free integers up to x that have an even number of prime factors, minus the count of those that have an odd number.

It is an extension of the Möbius function. Given the Möbius function μ(n), the Mertens function M(x) is the sum of the Möbius numbers from n == 1 through n == x.

Task

• Write a routine (function, procedure, whatever) to find the Mertens number for any positive integer x.

• Use that routine to find and display here, on this page, at least the first 99 terms in a grid layout. (Not just one long line or column of numbers.)

• Use that routine to find and display here, on this page, the number of times the Mertens function sequence is equal to zero in the range M(1) through M(1000).

• Use that routine to find and display here, on this page, the number of times the Mertens function sequence crosses zero in the range M(1) through M(1000). (Crossing defined as this term equal to zero but preceding term not.)

See also

• Wikipedia: Mertens function

• Wikipedia: Möbius function

• OEIS: A002321 - Mertens's function

• OEIS: A028442 - Numbers n such that Mertens's function M(n) is zero

• Numberphile - Mertens Conjecture

• Stackexchange: compute the mertens function

This is not code golf. The stackexchange link is provided as an algorithm reference, not as a guide.

Related tasks

• Möbius function

Factor

Works with: Factor version 0.99 2020-01-23

<lang factor>USING: formatting grouping io kernel math math.extras math.ranges math.statistics prettyprint sequences ;

! Take the cumulative sum of the mobius sequence to avoid ! summing lower terms over and over.

mertens-upto ( n -- seq ) [1,b] [ mobius ] map cum-sum ;

"The first 199 terms of the Mertens sequence:" print 199 mertens-upto " " prefix 20 group [ [ "%3s" printf ] each nl ] each nl

"In the first 1,000 terms of the Mertens sequence there are:" print 1000 mertens-upto [ [ zero? ] count bl pprint bl "zeros." print ] [

   2 <clumps> [ first2 [ 0 = not ] [ zero? ] bi* and ] count bl
   pprint bl "zero crossings." print

] bi</lang>

Output:

The first 199 terms of the Mertens sequence:
     1  0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3
 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1  0
  0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1  0 -1
 -1 -2 -1 -1 -1  0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4
 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1  0  1  2  2  1  1  1
  1  0 -1 -2 -2 -3 -2 -3 -3 -4 -5 -4 -4 -5 -6 -5 -5 -5 -4 -3
 -3 -3 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -1 -1 -1 -2 -3 -4
 -4 -3 -2 -1 -1  0  1  1  1  0  0 -1 -1 -1 -2 -1 -1 -2 -1  0
  0  1  1  0  0 -1  0 -1 -1 -1 -2 -2 -2 -3 -4 -4 -4 -3 -2 -3
 -3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -4 -5 -5 -6 -5 -6 -6 -7 -7 -8

In the first 1,000 terms of the Mertens sequence there are:
 92 zeros.
 59 zero crossings.

Go

<lang go>package main

import "fmt"

func mertens(to int) ([]int, int, int) {

   if to < 1 {
       to = 1
   }
   merts := make([]int, to+1)
   primes := []int{2}
   var sum, zeros, crosses int
   for i := 1; i <= to; i++ {
       j := i
       cp := 0      // counts prime factors
       spf := false // true if there is a square prime factor
       for _, p := range primes {
           if p > j {
               break
           }
           if j%p == 0 {
               j /= p
               cp++
           }
           if j%p == 0 {
               spf = true
               break
           }
       }
       if cp == 0 && i > 2 {
           cp = 1
           primes = append(primes, i)
       }
       if !spf {
           if cp%2 == 0 {
               sum++
           } else {
               sum--
           }
       }
       merts[i] = sum
       if sum == 0 {
           zeros++
           if i > 1 && merts[i-1] != 0 {
               crosses++
           }
       }
   }
   return merts, zeros, crosses

}

func main() {

   merts, zeros, crosses := mertens(1000)
   fmt.Println("Mertens sequence - First 199 terms:")
   for i := 0; i < 200; i++ {
       if i == 0 {
           fmt.Print("    ")
           continue
       }
       if i%20 == 0 {
           fmt.Println()
       }
       fmt.Printf("  % d", merts[i])
   }
   fmt.Println("\n\nEquals zero", zeros, "times between 1 and 1000")
   fmt.Println("\nCrosses zero", crosses, "times between 1 and 1000")

}</lang>

Output:

Mertens sequence - First 199 terms:
       1   0  -1  -1  -2  -1  -2  -2  -2  -1  -2  -2  -3  -2  -1  -1  -2  -2  -3
  -3  -2  -1  -2  -2  -2  -1  -1  -1  -2  -3  -4  -4  -3  -2  -1  -1  -2  -1   0
   0  -1  -2  -3  -3  -3  -2  -3  -3  -3  -3  -2  -2  -3  -3  -2  -2  -1   0  -1
  -1  -2  -1  -1  -1   0  -1  -2  -2  -1  -2  -3  -3  -4  -3  -3  -3  -2  -3  -4
  -4  -4  -3  -4  -4  -3  -2  -1  -1  -2  -2  -1  -1   0   1   2   2   1   1   1
   1   0  -1  -2  -2  -3  -2  -3  -3  -4  -5  -4  -4  -5  -6  -5  -5  -5  -4  -3
  -3  -3  -2  -1  -1  -1  -1  -2  -2  -1  -2  -3  -3  -2  -1  -1  -1  -2  -3  -4
  -4  -3  -2  -1  -1   0   1   1   1   0   0  -1  -1  -1  -2  -1  -1  -2  -1   0
   0   1   1   0   0  -1   0  -1  -1  -1  -2  -2  -2  -3  -4  -4  -4  -3  -2  -3
  -3  -4  -5  -4  -4  -3  -4  -3  -3  -3  -4  -5  -5  -6  -5  -6  -6  -7  -7  -8

Equals zero 92 times between 1 and 1000

Crosses zero 59 times between 1 and 1000

Julia

<lang julia>using Primes

function moebius(n::Integer)

   @assert n > 0
   m(p, e) = p == 0 ? 0 : e == 1 ? -1 : 0
   reduce(*, m(p, e) for (p, e) in factor(n) if p  ≥ 0; init=1)

end μ(n) = moebius(n)

mertens(x) = sum(n -> μ(n), 1:x) M(x) = mertens(x)

print("First 99 terms of the Mertens function for positive integers:\n ") for n in 1:99

   print(lpad(M(n), 3), n % 10 == 9 ? "\n" : "")

end println("\nM(n) equals 0: ", sum(n -> M(n) == 0, 1:1000), " times from 1 to 100.") println("\nM(n) \"crosses\" 0: ",

   sum(n -> M(n) == 0 && M(n-1) != 0, 1:1000), " times from 1 to 1000.")

</lang>

Output:

First 99 terms of the Mertens function for positive integers:
     1  0 -1 -1 -2 -1 -2 -2 -2
 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3
 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2
 -3 -4 -4 -3 -2 -1 -1 -2 -1  0
  0 -1 -2 -3 -3 -3 -2 -3 -3 -3
 -3 -2 -2 -3 -3 -2 -2 -1  0 -1
 -1 -2 -1 -1 -1  0 -1 -2 -2 -1
 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4
 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2
 -2 -1 -1  0  1  2  2  1  1  1

M(n) equals 0: 92 times from 1 to 1000.

M(n) "crosses" 0: 59 times from 1 to 1000.

Perl 6

Works with: Rakudo version 2019.11

Mertens number is not defined for n == 0. Perl 6 arrays are indexed from 0 so store a blank value at position zero to keep x and M(x) aligned.

<lang perl6>use Prime::Factor;

sub μ (Int \n) {

   my @p = prime-factors(n);
   +@p == +Bag(@p).keys ?? +@p %% 2 ?? 1 !! -1 !! 0

}

my @mertens = lazy [\+] flat ' ', 1, (2..*).map: -> \n { μ(n) };

put "Mertens sequence - First 199 terms:\n",

   @mertens[^200]».fmt('%3s').rotor(20).join("\n"),
   "\n\nEquals zero ", +@mertens[1..1000].grep( !* ),
   ' times between 1 and 1000', "\n\nCrosses zero ",
   +@mertens[1..1000].kv.grep( {!$^v and @mertens[$^k]} ),
   ' times between 1 and 1000';</lang>

Output:

Mertens sequence - First 199 terms:
      1   0  -1  -1  -2  -1  -2  -2  -2  -1  -2  -2  -3  -2  -1  -1  -2  -2  -3
 -3  -2  -1  -2  -2  -2  -1  -1  -1  -2  -3  -4  -4  -3  -2  -1  -1  -2  -1   0
  0  -1  -2  -3  -3  -3  -2  -3  -3  -3  -3  -2  -2  -3  -3  -2  -2  -1   0  -1
 -1  -2  -1  -1  -1   0  -1  -2  -2  -1  -2  -3  -3  -4  -3  -3  -3  -2  -3  -4
 -4  -4  -3  -4  -4  -3  -2  -1  -1  -2  -2  -1  -1   0   1   2   2   1   1   1
  1   0  -1  -2  -2  -3  -2  -3  -3  -4  -5  -4  -4  -5  -6  -5  -5  -5  -4  -3
 -3  -3  -2  -1  -1  -1  -1  -2  -2  -1  -2  -3  -3  -2  -1  -1  -1  -2  -3  -4
 -4  -3  -2  -1  -1   0   1   1   1   0   0  -1  -1  -1  -2  -1  -1  -2  -1   0
  0   1   1   0   0  -1   0  -1  -1  -1  -2  -2  -2  -3  -4  -4  -4  -3  -2  -3
 -3  -4  -5  -4  -4  -3  -4  -3  -3  -3  -4  -5  -5  -6  -5  -6  -6  -7  -7  -8

Equals zero 92 times between 1 and 1000

Crosses zero 59 times between 1 and 1000