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


 
program Mertens_function;
 
{$APPTYPE CONSOLE}
 
uses
  System.SysUtils;
 
type
  TMertens = record
    merts: TArray<Integer>;
    zeros, crosses: Integer;
    class function Mertens(_to: Integer): TMertens; static;
  end;
 
{ TMertens }
 
class function TMertens.Mertens(_to: Integer): TMertens;
var
  sum, zeros, crosses: Integer;
begin
  if _to < 1 then
    _to := 1;
 
  sum := 0;
  zeros := 0;
  crosses := 0;
 
  SetLength(Result.merts, _to + 1);
  var primes := [2];
  for var i := 1 to _to do
  begin
    var j := i;
    var cp := 0;
    var spf := false;
    for var p in primes do
    begin
      if p > j then
        Break;
      if j mod p = 0 then
      begin
        j := j div p;
        inc(cp);
      end;
 
      if j mod p = 0 then
      begin
        spf := true;
        Break;
      end;
    end;
    if (cp = 0) and (i > 2) then
    begin
      cp := 1;
      SetLength(primes, Length(primes) + 1);
      primes[High(primes)] := i;
    end;
 
    if not spf then
    begin
      if cp mod 2 = 0 then
        inc(sum)
      else
        dec(sum);
    end;
 
    Result.merts[i] := sum;
    if sum = 0 then
    begin
      inc(zeros);
      if (i > 1) and (Result.merts[i - 1] <> 0) then
        inc(crosses);
    end;
  end;
  Result.zeros := zeros;
  Result.crosses := crosses;
end;
 
begin
  var m := TMertens.mertens(1000);
  writeln('Mertens sequence - First 199 terms:');
  for var i := 0 to 199 do
  begin
    if i = 0 then
    begin
      write('    ');
      Continue;
    end;
    if i mod 20 = 0 then
      writeln;
    write(format(' %3d', [m.merts[i]]));
  end;
  writeln(#10#10'Equals zero ', m.zeros, ' times between 1 and 1000');
  writeln(#10'Crosses zero ', m.crosses, ' times between 1 and 1000');
  {$IFNDEF UNIX} readln; {$ENDIF}
end.