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

From Rosetta Code
Task
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.


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


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


Related tasks



C[edit]

#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++[edit]

#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[edit]

Works with: Factor version 0.99 2020-01-23
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
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[edit]

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, psum
dim as integer num_zeroes = 0, num_cross = 0
dim as string outstr
 
M(1) = 1
for 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 if
next n
 
print using "There are ### zeroes in the range 1 to 1000."; num_zeroes
print using "There are ### crossings in the range 1 to 1000."; num_cross
print "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 if
next 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[edit]

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

Haskell[edit]

import           Data.List.Split          (chunksOf)
import qualified Data.MemoCombinators as Memo
import Math.NumberTheory.Primes (unPrime, factorise)
import Text.Printf (printf)
 
moebius :: Integer -> Int
moebius = product . fmap m . factorise
where
m (p, e)
| unPrime p == 0 = 0
| e == 1 = -1
| otherwise = 0
 
mertens :: Integer -> Int
mertens = Memo.integral (\n -> sum $ fmap moebius [1..n])
 
countZeros :: [Integer] -> Int
countZeros = length . filter ((==0) . mertens)
 
crossesZero :: [Integer] -> Int
crossesZero = 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[edit]

 
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[edit]

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)).")
end
end
 
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[edit]

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 -1
var
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 sufficient
var
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[edit]

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[edit]

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 res
end function
sequence s = {" ."}
for i=1 to 143 do s = append(s,sprintf("%3d",Mertens(i))) end for
puts(1,join_by(s,1,12," "))
 
integer prev = 1, zeroes = 0, crosses = 0
for n=2 to 1000 do
integer m = Mertens(n)
if m=0 then
zeroes += 1
crosses += prev!=0
end if
prev = m
end for
printf(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[edit]

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[edit]

(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, 30100 -> $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[edit]

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, HI
if eqZ>0 then call Franz 1,-eqZ
if xZ>0 then call Franz -1, xZ
exit /*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 say
zeros= 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[edit]

Built-in:

say mertens(123456789)   #=> 1170
say 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)
}

Task:

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[edit]

Library: Wren-fmt
Library: Wren-math
import "/fmt" for Fmt
import "/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 directly
var count = 0
var 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 = 0
var 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[edit]

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