I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Mertens function

Mertens function
You are encouraged to solve this task according to the task description, using any language you may know.

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.

• 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.)

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

## C

`#include <stdio.h>#include <stdlib.h> int* mertens_numbers(int max) {    int* m = malloc((max + 1) * sizeof(int));    if (m == NULL)        return m;    m[1] = 1;    for (int n = 2; n <= max; ++n) {        m[n] = 1;        for (int k = 2; k <= n; ++k)            m[n] -= m[n/k];    }    return m;} int main() {    const int max = 1000;    int* mertens = mertens_numbers(max);    if (mertens == NULL) {        fprintf(stderr, "Out of memory\n");        return 1;    }    printf("First 199 Mertens numbers:\n");    const int count = 200;    for (int i = 0, column = 0; i < count; ++i) {        if (column > 0)            printf(" ");        if (i == 0)            printf("  ");        else            printf("%2d", mertens[i]);        ++column;        if (column == 20) {            printf("\n");            column = 0;        }    }    int zero = 0, cross = 0, previous = 0;    for (int i = 1; i <= max; ++i) {        int m = mertens[i];        if (m == 0) {            ++zero;            if (previous != 0)                ++cross;        }        previous = m;    }    free(mertens);    printf("M(n) is zero %d times for 1 <= n <= %d.\n", zero, max);    printf("M(n) crosses zero %d times for 1 <= n <= %d.\n", cross, max);    return 0;}`
Output:
```First 199 Mertens numbers:
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
M(n) is zero 92 times for 1 <= n <= 1000.
M(n) crosses zero 59 times for 1 <= n <= 1000.
```

## C++

`#include <iomanip>#include <iostream>#include <map> class mertens_calculator {public:    int mertens_number(int);private:    std::map<int, int> cache_;}; int mertens_calculator::mertens_number(int n) {    auto i = cache_.find(n);    if (i != cache_.end())        return i->second;    int m = 1;    for (int k = 2; k <= n; ++k)        m -= mertens_number(n/k);    cache_.emplace(n, m);    return m;} void print_mertens_numbers(mertens_calculator& mc, int count) {    int column = 0;    for (int i = 0; i < count; ++i) {        if (column > 0)            std::cout << ' ';        if (i == 0)            std::cout << "  ";        else            std::cout << std::setw(2) << mc.mertens_number(i);        ++column;        if (column == 20) {            std::cout << '\n';            column = 0;        }    }} int main() {    mertens_calculator mc;    std::cout << "First 199 Mertens numbers:\n";    print_mertens_numbers(mc, 200);    int zero = 0, cross = 0, previous = 0;    for (int i = 1; i <= 1000; ++i) {        int m = mc.mertens_number(i);        if (m == 0) {            ++zero;            if (previous != 0)                ++cross;        }        previous = m;    }    std::cout << "M(n) is zero " << zero << " times for 1 <= n <= 1000.\n";    std::cout << "M(n) crosses zero " << cross << " times for 1 <= n <= 1000.\n";    return 0;}`
Output:
```First 199 Mertens numbers:
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
M(n) is zero 92 times for 1 <= n <= 1000.
M(n) crosses zero 59 times for 1 <= n <= 1000.
```

## Factor

Works with: Factor version 0.99 2020-01-23
`USING: formatting grouping io kernel math math.extrasmath.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:" print199 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`
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.
```

## FreeBASIC

`function padto( i as ubyte, j as integer ) as string    return wspace(i-len(str(j)))+str(j)end function dim as integer M( 1 to 1000 ), n, col, k, psumdim as integer num_zeroes = 0, num_cross = 0dim as string outstr M(1) = 1for n = 2 to 1000    psum = 0    for k = 2 to n        psum += M(int(n/k))    next k    M(n) = 1 - psum    if M(n) = 0 then        num_zeroes += 1        if M(n-1)<>0 then            num_cross += 1        end if    end ifnext n print using "There are ### zeroes in the range 1 to 1000."; num_zeroesprint using "There are ### crossings in the range 1 to 1000."; num_crossprint "The first 100 Mertens numbers are: " for n=1 to 100    outstr += padto(3, M(n))+"  "    if n mod 10 = 0 then        print outstr        outstr = ""    end ifnext n`
Output:
```There are  92 zeroes in the range 1 to 1000.
There are  59 crossings in the range 1 to 1000.
The first 100 Mertens numbers are:
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
```

## 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")}`
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
```

`import           Data.List.Split          (chunksOf)import qualified Data.MemoCombinators  as Memoimport           Math.NumberTheory.Primes (unPrime, factorise)import           Text.Printf              (printf) moebius :: Integer -> Intmoebius = product . fmap m . factorise  where    m (p, e)      | unPrime p == 0 = 0      | e == 1 = -1      | otherwise = 0 mertens :: Integer -> Intmertens = Memo.integral (\n -> sum \$ fmap moebius [1..n]) countZeros :: [Integer] -> IntcountZeros = length . filter ((==0) . mertens) crossesZero :: [Integer] -> IntcrossesZero = length . go . fmap mertens  where    go (x:y:xs)       | y == 0 && x /= 0 = y : go (y:xs)      | otherwise        = go (y:xs)    go _ = [] main :: IO ()main = do  printf "The first 99 terms for M(1..99):\n\n   "  mapM_ (printf "%3d" . mertens) [1..9] >> printf "\n"  mapM_ (\row -> mapM_ (printf "%3d" . mertens) row >> printf "\n") \$ chunksOf 10 [10..99]  printf "\nM(n) is zero %d times for 1 <= n <= 1000.\n" \$ countZeros [1..1000]  printf "M(n) crosses zero %d times for 1 <= n <= 1000.\n" \$ crossesZero [1..1000]`
Output:
```The first 99 terms for M(1..99):

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) is zero 92 times for 1 <= n <= 1000.
M(n) crosses zero 59 times for 1 <= n <= 1000.```

## Java

` public class MertensFunction {     public static void main(String[] args) {        System.out.printf("First 199 terms of the merten function are as follows:%n    ");        for ( int n = 1 ; n < 200 ; n++ ) {            System.out.printf("%2d  ", mertenFunction(n));            if ( (n+1) % 20 == 0 ) {                System.out.printf("%n");            }        }         for ( int exponent = 3 ; exponent<= 8 ; exponent++ ) {            int zeroCount = 0;            int zeroCrossingCount = 0;            int positiveCount = 0;            int negativeCount = 0;            int mSum = 0;            int mMin = Integer.MAX_VALUE;            int mMinIndex = 0;            int mMax = Integer.MIN_VALUE;            int mMaxIndex = 0;            int nMax = (int) Math.pow(10, exponent);            for ( int n = 1 ; n <= nMax ; n++ ) {                int m = mertenFunction(n);                mSum += m;                if ( m < mMin ) {                    mMin = m;                    mMinIndex = n;                }                if ( m > mMax ) {                    mMax = m;                    mMaxIndex = n;                }                if ( m > 0 ) {                    positiveCount++;                }                if ( m < 0 ) {                    negativeCount++;                }                if ( m == 0 ) {                    zeroCount++;                }                if ( m == 0 && mertenFunction(n - 1) != 0 ) {                    zeroCrossingCount++;                }            }            System.out.printf("%nFor M(x) with x from 1 to %,d%n", nMax);                    System.out.printf("The maximum of M(x) is M(%,d) = %,d.%n", mMaxIndex, mMax);            System.out.printf("The minimum of M(x) is M(%,d) = %,d.%n", mMinIndex, mMin);            System.out.printf("The sum of M(x) is %,d.%n", mSum);            System.out.printf("The count of positive M(x) is %,d, count of negative M(x) is %,d.%n", positiveCount, negativeCount);            System.out.printf("M(x) has %,d zeroes in the interval.%n", zeroCount);            System.out.printf("M(x) has %,d crossings in the interval.%n", zeroCrossingCount);        }    }     private static int MU_MAX = 100_000_000;    private static int[] MU = null;    private static int[] MERTEN = null;     //  Compute mobius and merten function via sieve    private static int mertenFunction(int n) {        if ( MERTEN != null ) {            return MERTEN[n];        }         //  Populate array        MU = new int[MU_MAX+1];        MERTEN = new int[MU_MAX+1];        MERTEN[1] = 1;        int sqrt = (int) Math.sqrt(MU_MAX);        for ( int i = 0 ; i < MU_MAX ; i++ ) {            MU[i] = 1;        }         for ( int i = 2 ; i <= sqrt ; i++ ) {            if ( MU[i] == 1 ) {                //  for each factor found, swap + and -                for ( int j = i ; j <= MU_MAX ; j += i ) {                    MU[j] *= -i;                }                //  square factor = 0                for ( int j = i*i ; j <= MU_MAX ; j += i*i ) {                    MU[j] = 0;                }            }        }         int sum = 1;        for ( int i = 2 ; i <= MU_MAX ; i++ ) {            if ( MU[i] == i ) {                MU[i] = 1;            }            else if ( MU[i] == -i ) {                MU[i] = -1;            }            else if ( MU[i] < 0 ) {                MU[i] = 1;                           }            else if ( MU[i] > 0 ) {                MU[i] = -1;            }            sum += MU[i];            MERTEN[i] = sum;        }        return MERTEN[n];    } } `
Output:
```First 199 terms of the merten function are as follows:
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

For M(x) with x from 1 to 1,000
The maximum of M(x) is M(586) = 7.
The minimum of M(x) is M(665) = -12.
The sum of M(x) is -1,572.
The count of positive M(x) is 254, count of negative M(x) is 654.
M(x) has 92 zeroes in the interval.
M(x) has 59 crossings in the interval.

For M(x) with x from 1 to 10,000
The maximum of M(x) is M(8,511) = 35.
The minimum of M(x) is M(9,861) = -43.
The sum of M(x) is -20,409.
The count of positive M(x) is 3,965, count of negative M(x) is 5,629.
M(x) has 406 zeroes in the interval.
M(x) has 256 crossings in the interval.

For M(x) with x from 1 to 100,000
The maximum of M(x) is M(48,433) = 96.
The minimum of M(x) is M(96,014) = -132.
The sum of M(x) is -516,879.
The count of positive M(x) is 47,830, count of negative M(x) is 50,621.
M(x) has 1,549 zeroes in the interval.
M(x) has 949 crossings in the interval.

For M(x) with x from 1 to 1,000,000
The maximum of M(x) is M(992,998) = 311.
The minimum of M(x) is M(926,265) = -368.
The sum of M(x) is -14,244,200.
The count of positive M(x) is 472,963, count of negative M(x) is 521,676.
M(x) has 5,361 zeroes in the interval.
M(x) has 3,269 crossings in the interval.

For M(x) with x from 1 to 10,000,000
The maximum of M(x) is M(9,993,034) = 1,143.
The minimum of M(x) is M(7,109,110) = -1,078.
The sum of M(x) is -194,680,528.
The count of positive M(x) is 4,938,188, count of negative M(x) is 5,049,266.
M(x) has 12,546 zeroes in the interval.
M(x) has 7,646 crossings in the interval.

For M(x) with x from 1 to 100,000,000
The maximum of M(x) is M(92,418,127) = 3,290.
The minimum of M(x) is M(76,015,339) = -3,448.
The sum of M(x) is -608,757,258.
The count of positive M(x) is 54,659,906, count of negative M(x) is 45,298,186.
M(x) has 41,908 zeroes in the interval.
M(x) has 25,525 crossings in the interval.
```

## Julia

The OEIS A002321 reference suggests the Mertens function has a negative bias, which it does below 1 million, but this bias seems to switch to a positive bias by 1 billion. There may simply be large swings in the bias overall, which get larger and longer as the sequence continues.

`using Primes, Formatting function moebius(n::Integer)    @assert n > 0    m(p, e) = p == 0 ? 0 : e == 1 ? -1 : 0    return 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 function maximinM(N)    z, cros, lastM, maxi, maxM, mini, minM, sumM, pos, neg = 0, 0, 0, 0, 0, 0, 0, 0, 0, 0    for i in 1:N        m = μ(i) + lastM        if m == 0 && lastM != 0            cros += 1        end        sumM += m        lastM = m        if m > maxM            maxi = i            maxM = m        elseif m < minM            mini = i            minM = m        end        if m > 0            pos += 1        elseif m < 0            neg += 1        else            z += 1        end    end    println("\nFor M(x) with x from 1 to \$(format(N, commas=true)):")    println("The maximum of M(x) is M(\$(format(maxi, commas=true)) = \$maxM.")    println("The minimum of M(x) is M(\$(format(mini, commas=true))) = \$minM.")    println("The sum of M(x) is \$(format(sumM, commas=true)).")    println("The count of positive M(x) is \$(format(pos, commas=true)), count of negative M(x) is \$(format(neg, commas=true)).")    println("M(x) has \$(format(z, commas=true)) zeroes in the interval.")    println("M(x) has \$(format(cros, commas=true)) crossings in the interval.")    diff = pos - neg    if diff > 0        println("Positive M(x) exceed negative ones by \$(format(diff, commas=true)).")    else        println("Negative M(x) exceed positive ones by \$(format(-diff, commas=true)).")    endend foreach(maximinM, (1000, 1_000_000, 1_000_000_000)) `
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

For M(x) with x from 1 to 1,000:
The maximum of M(x) is M(586 = 7.
The minimum of M(x) is M(665) = -12.
The sum of M(x) is -1,572.
The count of positive M(x) is 254, count of negative M(x) is 654.
M(x) has 92 zeroes in the interval.
M(x) has 59 crossings in the interval.
Negative M(x) exceed positive ones by 400.

For M(x) with x from 1 to 1,000,000:
The maximum of M(x) is M(992,998 = 311.
The minimum of M(x) is M(926,265) = -368.
The sum of M(x) is -14,244,200.
The count of positive M(x) is 472,963, count of negative M(x) is 521,676.
M(x) has 5,361 zeroes in the interval.
M(x) has 3,269 crossings in the interval.
Negative M(x) exceed positive ones by 48,713.

For M(x) with x from 1 to 1,000,000,000:
The maximum of M(x) is M(903,087,703 = 10246.
The minimum of M(x) is M(456,877,618) = -8565.
The sum of M(x) is 510,495,361,261.
The count of positive M(x) is 510,200,302, count of negative M(x) is 489,658,577.
M(x) has 141,121 zeroes in the interval.
M(x) has 85,652 crossings in the interval.
Positive M(x) exceed negative ones by 20,541,725.
```

## Pascal

Works with: Free Pascal

Nearly the same as Square-free_integers#Pascal Instead here marking all multiples, starting at factor 2, of a prime by incrementing the factor count.
runtime ~log(n)*n

`program Merten;{\$IFDEF FPC}  {\$MODE DELPHI}  {\$Optimization ON,ALL}{\$ELSE}   {\$APPTYPE CONSOLE}{\$ENDIF}uses  sysutils;const  BigLimit = 10*1000*1000*1000;//1e10 type  tSieveElement = Int8;  tpSieve = pInt8;  tMoebVal = array[-1..1] of Int64;var  MertensValues : array[-40000..50500] of NativeInt;  primes : array of byte;  sieve : array of tSieveElement; procedure CompactPrimes;//searching for needed primes//last primes are marked with -1var  pSieve : tpSieve;  i,lmt,dp:NativeInt;Begin  setlength(Primes,74500);//suffices for primes to calc square upto 1e12  //extract difference of primes  i := 2;  lmt := 0;  dp := 2;  pSieve :=@sieve[0];  repeat    IF pSieve[i]= 0 then    Begin      //mark for Moebius      pSieve[i]:= -1;      primes[lmt] := dp;      dp := 0;      inc(lmt);    end;    inc(dp);    inc(i);  until i*i >BigLimit;  setlength(Primes,lmt+1);   repeat    IF pSieve[i]= 0 then      //mark for Moebius      pSieve[i]:= -1;    inc(i);  until i >BigLimit;end; procedure SieveSquares;//mark all powers >=2 of prime  => all powers = 2 is sufficientvar  pSieve : tpSieve;  i,sq,k,prime : NativeInt;Begin  pSieve := @sieve[0];  prime := 0;  For i := 0 to High(primes) do  Begin    prime := prime+primes[i];    sq := prime*prime;    k := sq;    if sq > BigLimit then      break;    repeat      pSieve[k] := 0;      inc(k,sq);    until k> BigLimit;  end;end; procedure initPrimes;var  pSieve : tpSieve;  fakt,  sieveprime : NativeUint;begin  pSieve := @sieve[0];  sieveprime := 2;  repeat    if pSieve[sieveprime]=0 then    begin      fakt := sieveprime+sieveprime;      while fakt <=BigLimit do      Begin        //count divisors        inc(pSieve[fakt]);        inc(fakt,sieveprime);      end;    end;    inc(sieveprime);  until sieveprime>BigLimit DIV 2;  //Möbius of 1  pSieve[1] := 1;   //convert to Moebius  For fakt := 2 to BigLimit do  Begin    sieveprime := pSieve[fakt];    IF sieveprime<>0 then      pSieve[fakt] := 1-(2*(sieveprime AND 1)) ;  end;  CompactPrimes;  SieveSquares;end; procedure OutMerten10(Lmt,ZeroCross:NativeInt;Const MoebVal:tMoebVal);var  i,j: NativeInt;Begin  Writeln(lmt:11,MoebVal[-1]:11,MoebVal[1]:11,MoebVal[-1]+MoebVal[1]:11,  MoebVal[-1]-MoebVal[1]:7,MoebVal[0]:11);  i:= low(MertensValues);  while MertensValues[i] = 0 do    inc(i);  j:= High(MertensValues);  while MertensValues[j] = 0 do    dec(j);  write('Merten min ',i:6,' max ',j:6,' zero''s ',MertensValues[0]:8);  writeln(' zeroCross ',ZeroCross);  writeln;end; procedure Count_x10;var  MoebCount: tMoebVal;  pSieve : tpSieve;  i,lmt,Merten,Moebius,LastMert,ZeroCross: NativeInt;begin  writeln('[1 to limit]');  Writeln('Limit        Moeb. odd   Moeb.even  sqr-free Merten     Zero''s');   pSieve := @sieve[0];  For i := -1 to 1 do    MoebCount[i]:=0;  ZeroCross := 0;  LastMert :=1;  Merten :=0;  lmt := 10;  i := 1;  repeat    while i <= lmt do    Begin      Moebius := pSieve[i];      inc(MoebCount[Moebius]);      inc(Merten,Moebius);      inc(MertensValues[Merten]);//MoebCount[1]-MoebCount[-1]]);      inc(ZeroCross,ORD( (Merten = 0) AND (LastMert <> 0)));      LastMert := Merten;      inc(i);    end;    OutMerten10(Lmt,ZeroCross,MoebCount);     IF lmt >= BigLimit then      BREAK;    lmt := lmt*10;    IF lmt >BigLimit then      lmt := BigLimit;  until false;  writeln;end; procedure OutMerten(lmt:NativeInt);var  i,k,m : NativeInt;Begin  iF lmt> BigLimit then    lmt := BigLimit;  writeln('Mertens numbers from 1 to ',lmt);  k := 9;  write('':3);  m := 0;  For i := 1 to lmt do  Begin    inc(m,sieve[i]);    write(m:3);    dec(k);    IF k = 0 then    Begin      writeln;      k := 10;    end;  end;  writeln;end; procedure OutMoebius(lmt:NativeInt);var  i,k : NativeInt;Begin  iF lmt> BigLimit then    lmt := BigLimit;  writeln('Möbius numbers from 1 to ',lmt);  k := 19;  write('':3);  For i := 1 to lmt do  Begin    write(sieve[i]:3);    dec(k);    IF k = 0 then    Begin      writeln;      k := 20;    end;  end;  writeln;end; Begin  setlength(sieve,BigLimit+1);  InitPrimes;  SieveSquares;  Count_x10;  OutMoebius(199);  OutMerten(99);  setlength(primes,0);  setlength(sieve,0);end.`
Output:
```[1 to limit]
Limit        Moeb. odd   Moeb.even  sqr-free Merten     Zero's
10          4          3          7      1          3
Merten min     -2 max      1 zero's        1 zeroCross 1

100         30         31         61     -1         39
Merten min     -4 max      2 zero's        6 zeroCross 5

1000        303        305        608     -2        392
Merten min    -12 max      7 zero's       92 zeroCross 59

10000       3053       3030       6083     23       3917
Merten min    -43 max     35 zero's      406 zeroCross 256

100000      30421      30373      60794     48      39206
Merten min   -132 max     96 zero's     1549 zeroCross 949

1000000     303857     304069     607926   -212     392074
Merten min   -368 max    311 zero's     5361 zeroCross 3269

10000000    3039127    3040164    6079291  -1037    3920709
Merten min  -1078 max   1143 zero's    12546 zeroCross 7646

100000000   30395383   30397311   60792694  -1928   39207306
Merten min  -3448 max   3290 zero's    41908 zeroCross 25525

1000000000  303963673  303963451  607927124    222  392072876
Merten min  -8565 max  10246 zero's   141121 zeroCross 85652

10000000000 3039652332 3039618610 6079270942  33722 3920729058
Merten min -35517 max  50286 zero's   431822 zeroCross 262605

Möbius numbers from 1 to 199
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  1  0  0 -1 -1 -1  0  1  1  1  0 -1  1  1
0 -1 -1 -1  0  0  1 -1  0  0  0  1  0 -1  0  1  0  1  1 -1
0 -1  1  0  0  1 -1 -1  0  1 -1 -1  0 -1  1  0  0  1 -1 -1
0  0  1 -1  0  1  1  1  0 -1  0  1  0  1  1  1  0 -1  0  0
0 -1 -1 -1  0 -1  1 -1  0 -1 -1  1  0 -1 -1  1  0  0  1  1
0  0  1  1  0  0  0 -1  0  1 -1 -1  0  1  1  0  0 -1 -1 -1
0  1  1  1  0  1  1  0  0 -1  0 -1  0  0 -1  1  0 -1  1  1
0  1  0 -1  0 -1  1 -1  0  0 -1  0  0 -1 -1  0  0  1  1 -1
0 -1 -1  1  0  1 -1  1  0  0 -1 -1  0 -1  1 -1  0 -1  0 -1

Mertens numbers from 1 to 99
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

real    3m54,249s = 234s //BigLimit = 100*1000*1000;takes 2.017s```

## Perl

`use utf8;use strict;use warnings;use feature 'say';use List::Util 'uniq'; sub prime_factors {    my (\$n, \$d, @factors) = (shift, 1);    while (\$n > 1 and \$d++) {        \$n /= \$d, push @factors, \$d until \$n % \$d;    }    @factors} sub μ {    my @p = prime_factors(shift);    @p == uniq(@p) ? 0 == @p%2 ? 1 : -1 : 0} sub progressive_sum {    my @sum = shift @_;    push @sum, \$sum[-1] + \$_ for @_;    @sum} my(\$upto, \$show, @möebius) = (1000, 199, ());push @möebius, μ(\$_) for 1..\$upto;my @mertens = progressive_sum @möebius; say "Mertens sequence - First \$show terms:\n" .    (' 'x4 . sprintf "@{['%4d' x \$show]}", @mertens[0..\$show-1]) =~ s/((.){80})/\$1\n/gr .    sprintf("\nEquals zero %3d times between 1 and \$upto", scalar grep { ! \$_ } @mertens) .    sprintf "\nCrosses zero%3d times between 1 and \$upto", scalar grep { ! \$mertens[\$_-1] and \$mertens[\$_] } 1 .. @mertens;`
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```

## Phix

Based on the stackexchange link, short and sweet but not very fast: 1.4s just for the first 1000...

`function Mertens(integer n)    integer res = 1    for k=2 to n do        res -= Mertens(floor(n/k))    end for    return resend functionsequence s = {"  ."}for i=1 to 143 do s = append(s,sprintf("%3d",Mertens(i))) end forputs(1,join_by(s,1,12," ")) integer prev = 1, zeroes = 0, crosses = 0for n=2 to 1000 do    integer m = Mertens(n)    if m=0 then        zeroes += 1        crosses += prev!=0     end if    prev = mend forprintf(1,"\nMertens[1..1000] equals zero %d times and crosses zero %d times\n",{zeroes,crosses})`
Output:

Matches the wp table:

```  .   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

Mertens[1..1000] equals zero 92 times and crosses zero 59 times
```

## Prolog

Works with: SWI Prolog
`:- dynamic mertens_number_cache/2. mertens_number(1, 1):- !.mertens_number(N, M):-    mertens_number_cache(N, M),    !.mertens_number(N, M):-    N >= 2,    mertens_number(N, 2, M, 0),    assertz(mertens_number_cache(N, M)). mertens_number(N, N, M, M):- !.mertens_number(N, K, M, S):-    N1 is N // K,    mertens_number(N1, M1),    K1 is K + 1,    S1 is S - M1,    mertens_number(N, K1, M, S1). print_mertens_numbers(Count):-    print_mertens_numbers(Count, 0). print_mertens_numbers(Count, Count):-!.print_mertens_numbers(Count, N):-    (N == 0 ->        write('   ')        ;        mertens_number(N, M),        writef('%3r', [M])    ),    N1 is N + 1,    Column is N1 mod 20,    (N > 0, Column == 0 ->        nl        ;        true    ),    print_mertens_numbers(Count, N1). count_zeros(From, To, Z, C):-    count_zeros(From, To, Z, C, 0, 0, 0). count_zeros(From, To, Z, C, Z, C, _):-    From > To,    !.count_zeros(From, To, Z, C, Z1, C1, P):-    mertens_number(From, M),    (M == 0 -> Z2 is Z1 + 1 ; Z2 = Z1),    (M == 0, P \= 0 -> C2 is C1 + 1 ; C2 = C1),    Next is From + 1,    count_zeros(Next, To, Z, C, Z2, C2, M). main:-    writeln('First 199 Mertens numbers:'),    print_mertens_numbers(200),    count_zeros(1, 1000, Z, C),    writef('M(n) is zero %t times for 1 <= n <= 1000.\n', [Z]),    writef('M(n) crosses zero %t times for 1 <= n <= 1000.\n', [C]).`
Output:
```First 199 Mertens numbers:
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
M(n) is zero 92 times for 1 <= n <= 1000.
M(n) crosses zero 59 times for 1 <= n <= 1000.
```

## Raku

(formerly Perl 6)

Works with: Rakudo version 2019.11

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

`use Prime::Factor; sub μ (Int \n) {    return 0 if n %% 4 or n %% 9 or n %% 25 or n %% 49 or n %% 121;    my @p = prime-factors(n);    +@p == +@p.unique ?? +@p %% 2 ?? 1 !! -1 !! 0} my @mertens = lazy [\+] flat '', 1, (2..*).hyper.map: -> \n { μ(n) }; put "Mertens sequence - First 199 terms:\n",    @mertens[^200]».fmt('%3s').batch(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\n\nFirst Mertens equal to:"; for 10, 20, 30 … 100 -> \$threshold {    printf "%4d: M(%d)\n", -\$threshold, @mertens.first: * == -\$threshold, :k;    printf "%4d: M(%d)\n",  \$threshold, @mertens.first: * ==  \$threshold, :k;}`
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

First Mertens equal to:
-10: M(659)
10: M(1393)
-20: M(2791)
20: M(3277)
-30: M(9717)
30: M(8503)
-40: M(9831)
40: M(11770)
-50: M(24018)
50: M(19119)
-60: M(24105)
60: M(31841)
-70: M(24170)
70: M(31962)
-80: M(42789)
80: M(48202)
-90: M(59026)
90: M(48405)
-100: M(59426)
100: M(114717)```

## REXX

Programming note:   This REXX version supports the specifying of the low and high values to be generated,
as well as the "group" size for the grid   (it can be specified as   1   which will show a vertical list).

A null value will be shown as a bullet (•) when showing the Möbius and/or Mertens value of for zero   (which can be changed easily).

The above "feature" was added to make the grid to be aligned with other solutions.

`/*REXX pgm computes & shows a value grid of the Mertens function for a range of integers*//*───────────────────────────────────────────────{function is named after Franz Mertens}*/parse arg LO HI grp eqZ xZ .                     /*obtain optional arguments from the CL*/if  LO=='' |  LO==","  then  LO=    0            /*Not specified?  Then use the default.*/if  HI=='' |  HI==","  then  HI=  199            /* "      "         "   "   "     "    */if grp=='' | grp==","  then grp=   20            /* "      "         "   "   "     "    */if eqZ=='' | eqZ==","  then eqZ= 1000            /* "      "         "   "   "     "    */if  xZ=='' |  xZ==","  then  xZ= 1000            /* "      "         "   "   "     "    */!.=.;                        M.= !.              /*initialize two arrays for memoization*/hihi= max(HI, eqZ, xZ)                           /*find max of all ranges.     ________ */call genP                                        /*generate primes up to max  √  HIHI   */               call Franz LO, HIif eqZ>0  then call Franz 1,-eqZif  xZ>0  then call Franz -1, xZexit                                             /*stick a fork in it,  we're all done. *//*──────────────────────────────────────────────────────────────────────────────────────*/Franz: parse arg a 1 oa,b 1 ob;  @Mertens=' The Mertens sequence from 'a= abs(a);   b= abs(b);    grid= oa>=0 & ob>=0   /*semaphore used to show a grid title. */if grid  then say center(@Mertens LO " ──► " HI" ", max(50, grp*3), '═')    /*show title*/         else sayzeros= 0                                         /*# of  0's found for Mertens function.*/Xzero= 0                                         /*number of times that zero was crossed*/prev=\$=                                               /*\$  holds output grid of GRP numbers. */   do j=a  to b;     _= Mertens(j)               /*process some numbers from  LO ──► HI.*/   if _==0  then zeros= zeros + 1                /*Is Zero?  Then bump the zeros counter*/   if _==0  then if prev\==0 then Xzero= Xzero+1 /*prev ¬=0?   "   "    "  Xzero    "   */   prev= _   if grid  then \$= \$ right(_, 2)                /*build grid if A & B are non─negative.*/   if words(\$)==grp  then do;  say substr(\$, 2);  \$=     /*show grid if fully populated,*/                          end                            /*  and nullify it for more #s.*/   end   /*j*/                                   /*for small grids, using wordCnt is OK.*/ if \$\==''  then say substr(\$, 2)                 /*handle any residual numbers not shown*/if oa<0  then say @Mertens   a    " to "    b   ' has crossed zero '    Xzero    " times."if ob<0  then say @Mertens   a    " to "    b   ' has '                 zeros    " zeros."return/*──────────────────────────────────────────────────────────────────────────────────────*/Mertens: procedure expose @. !. M.;  parse arg n /*obtain a integer to be tested for mu.*/         if M.n\==.  then return M.n             /*was computed before?  Then return it.*/         if n<1      then return '∙'             /*handle special cases of non─positive#*/         m= 0                                    /*the sum of all the  MU's  (so far).  */              do k=1  for n;   m= m + mobius(k)  /*sum the  MU's  up to  N.             */              end   /*k*/                        /* [↑] mobius function uses memoization*/         M.n= m;          return m               /*return the sum of all the  MU's.     *//*──────────────────────────────────────────────────────────────────────────────────────*/mobius: procedure expose @. !.; parse arg x 1 ox /*obtain a integer to be tested for mu.*/        if !.x\==.  then return !.x              /*X computed before?  Return that value*/        if x<1      then return '∙'              /*handle special case of non-positive #*/        #= 0                                     /*start with a  mu  value of zero.     */             do k=1;  p= @.k                     /*get the  Kth  (pre─generated)  prime.*/             if p>x  then leave                  /*prime (P)   > X?    Then we're done. */             if p*p>x  then do;   #= #+1;  leave /*prime (P**2 > X?    Bump # and leave.*/                            end             if x//p==0  then do; #= #+1         /*X divisible by P?   Bump mu number.  */                                  x= x % p       /*                    Divide by prime. */                                  if x//p==0  then return 0  /*X÷by P?  Then return zero*/                              end             end   /*k*/                         /*#  (below) is almost always small, <9*/        !.ox=  -1 ** #;        return !.ox       /*raise -1 to the mu power, memoize it.*//*──────────────────────────────────────────────────────────────────────────────────────*/genP: @.1=2;  @.2=3; @.3=5; @.4=7; @.5=11; @.6= 13; nP=6 /*assign low primes; # primes. */       do lim=nP  until lim*lim>=hihi;  end      /*only keep primes up to the sqrt(HI). */       do [email protected].nP+4  by 2  to hihi                /*only find odd primes from here on.   */       if j// 3==0  then iterate                 /*is J divisible by  #3  Then not prime*/       parse var j '' -1 _;if _==5  then iterate /*Is last digit a "5"?     "   "    "  */       if j// 7==0  then iterate                 /*is J divisible by  7?    "   "    "  */       if j//11==0  then iterate                 /* " "     "      " 11?    "   "    "  */       if j//13==0  then iterate                 /*is "     "      " 13?    "   "    "  */          do k=7  while k*k<=j                   /*divide by some generated odd primes. */          if j // @.k==0  then iterate j         /*Is J divisible by  P?  Then not prime*/          end   /*k*/                            /* [↓]  a prime  (J)  has been found.  */       nP= nP+1;  if nP<=HI  then @.nP=j         /*bump prime count; assign prime to  @.*/       end      /*j*/;            return`
output   when using the default inputs:

Output note:   note the use of a bullet (•) to signify that a "null" is being shown (for the 0th entry).

```══════════ The Mertens sequence from  0  ──►  199 ══════════
∙  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

The Mertens sequence from  1  to  1000  has  92  zeros.

The Mertens sequence from  1  to  1000  has crossed zero  59  times.
```

## Sidef

Built-in:

`say mertens(123456789)   #=> 1170say mertens(1234567890)  #=> 9163`

Algorithm for computing M(n) in sublinear time:

`func mertens(n) is cached {     var lookup_size    = (2 * n.iroot(3)**2)    var mertens_lookup = [0]     for k in (1..lookup_size) {        mertens_lookup[k] = (mertens_lookup[k-1] + k.moebius)    }     static cache = Hash()     func (n) {         if (n <= lookup_size) {            return mertens_lookup[n]        }         if (cache.has(n)) {            return cache{n}        }         var M = 1        var s = n.isqrt         for k in (2 .. floor(n/(s+1))) {            M -= __FUNC__(floor(n/k))        }         for k in (1..s) {            M -= (mertens_lookup[k] * (floor(n/k) - floor(n/(k+1))))        }         cache{n} = M    }(n)}`

`with (200) {|n|    say "Mertens function in the range 1..#{n}:"    (1..n).map { mertens(_) }.slices(20).each {|line|        say line.map{ "%2s" % _ }.join(' ')    }} with (1000) {|n|    say "\nIn the range 1..#{n}, there are:"    say (1..n->count_by { mertens(_)==0 }, " zeros")    say (1..n->count_by { mertens(_)==0 && mertens(_-1)!=0 }, " zero crossings")}`
Output:
```Mertens function in the range 1..200:
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 -8

In the range 1..1000, there are:
92 zeros
59 zero crossings
```

## Wren

Library: Wren-fmt
Library: Wren-math
`import "/fmt" for Fmtimport "/math" for Int var isSquareFree = Fn.new { |n|    var i = 2    while (i * i <= n) {        if (n%(i*i) == 0) return false        i = (i > 2) ? i + 2 : i + 1    }    return true} var mu = Fn.new { |n|    if (n < 1) Fiber.abort("Argument must be a positive integer")    if (n == 1) return 1    var sqFree = isSquareFree.call(n)    var factors = Int.primeFactors(n)    if (sqFree && factors.count % 2 == 0) return 1    if (sqFree) return -1    return 0} var M = Fn.new { |x| (1..x).reduce { |sum, n| sum + mu.call(n) } } System.print("The first 199 Mertens numbers are:")for (i in 0..9) {    for (j in 0..19) {        if (i == 0 && j == 0) {            System.write("    ")        } else {            System.write("%(Fmt.dm(3, M.call(i*20 + j))) ")        }    }    System.print()} // use the recurrence relationship for the last 2 parts rather than calling M directlyvar count = 0var mertens = M.call(1)for (i in 2..1000) {    mertens = mertens + mu.call(i)    if (mertens == 0) count = count + 1}System.print("\nThe Mertens function is zero %(count) times in the range [1, 1000].") count = 0var prev = M.call(1)for (i in 2..1000) {    var next = prev + mu.call(i)    if (next == 0 && prev != 0) count = count + 1    prev = next}System.print("\nThe Mertens function crosses zero %(count) times in the range [1, 1000].")`
Output:
```The first 199 Mertens numbers are:
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

The Mertens function is zero 92 times in the range [1, 1000].

The Mertens function crosses zero 59 times in the range [1, 1000].
```

## zkl

`fcn mertensW(n){   [1..].tweak(fcn(n,pm){      pm.incN(mobius(n));      pm.value   }.fp1(Ref(0)))}fcn mobius(n){   pf:=primeFactors(n);   sq:=pf.filter1('wrap(f){ (n % (f*f))==0 });  // False if square free   if(sq==False){ if(pf.len().isEven) 1 else -1 }   else 0}fcn primeFactors(n){  // Return a list of prime factors of n   acc:=fcn(n,k,acc,maxD){  // k is 2,3,5,7,9,... not optimum      if(n==1 or k>maxD) acc.close();      else{	 q,r:=n.divr(k);   // divr-->(quotient,remainder)	 if(r==0) return(self.fcn(q,k,acc.write(k),q.toFloat().sqrt()));	 return(self.fcn(n,k+1+k.isOdd,acc,maxD))  # both are tail recursion      }   }(n,2,Sink(List),n.toFloat().sqrt());   m:=acc.reduce('*,1);      // mulitply factors   if(n!=m) acc.append(n/m); // opps, missed last factor   else acc;}`
`mertensW().walk(199).pump(Console.println, T(Void.Read,19,False),	fcn{ vm.arglist.pump(String,"%3d".fmt) }); println("\nIn the first 1,000 terms of the Mertens sequence there are:");otm:=mertensW().pump(1_000,List);otm.reduce(fcn(s,m){ s + (m==0) },0) : println(_," zeros");otm.reduce(fcn(p,m,rs){ rs.incN(m==0 and p!=0); m }.fp2( s:=Ref(0) ));println(s.value," zero crossings");`
Output:
```  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
```