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


% Generate Mertens numbers up to a given limit
mertens = proc (limit: int) returns (array[int])
    M: array[int] := array[int]$fill(1,limit,0)
    M[1] := 1
    for n: int in int$from_to(2,limit) do
        M[n] := 1
        for k: int in int$from_to(2,n) do
            M[n] := M[n] - M[n/k]
        end
    end
    return (M)
end mertens
 
start_up = proc ()
    max = 1000
 
    po: stream := stream$primary_output()
    M: array[int] := mertens(max)
 
    stream$putl(po, "The first 99 Mertens numbers are:")
    for y: int in int$from_to_by(0,90,10) do
        for x: int in int$from_to(0,9) do
            stream$putright(po, int$unparse(M[x+y]), 3)
            except when bounds:
                stream$putright(po, "", 3)
            end
        end
        stream$putl(po, "")
    end
 
    eqz: int := 0
    crossz: int := 0
    for i: int in int$from_to(2,max) do
        if M[i]=0 then
            eqz := eqz + 1
            if M[i-1]~=0 then crossz := crossz + 1 end
        end
    end
 
    stream$putl(po, "M(N) is zero " || int$unparse(eqz) || " times.")
    stream$putl(po, "M(N) crosses zero " || int$unparse(crossz) || " times.")
end start_up