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

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



Task

 Write a routine (function, procedure, whatever) to find the Mertens number for any positive integer x.
 Use that routine to find and display here, on this page, at least the first 99 terms in a grid layout. (Not just one long line or column of numbers.)
 Use that routine to find and display here, on this page, the number of times the Mertens function sequence is equal to zero in the range M(1) through M(1000).
 Use that routine to find and display here, on this page, the number of times the Mertens function sequence crosses zero in the range M(1) through M(1000). (Crossing defined as this term equal to zero but preceding term not.)


See also

 Wikipedia: Mertens function
 Wikipedia: Möbius function
 OEIS: A002321 - Mertens's function
 OEIS: A028442 - Numbers n such that Mertens's function M(n) is zero
 Numberphile - Mertens Conjecture
 Stackexchange: compute the mertens function

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



Related tasks

 Möbius function


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;