How to resolve the algorithm Mertens function step by step in the Modula-2 programming language

Published on 12 May 2024 09:40 PM
#Modula-2

How to resolve the algorithm Mertens function step by step in the Modula-2 programming language

Table of Contents

Problem Statement

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.

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

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Mertens function step by step in the Modula-2 programming language

Source code in the modula-2 programming language

MODULE Mertens;
FROM InOut IMPORT WriteString, WriteInt, WriteCard, WriteLn;

CONST Max = 1000;
VAR n, k, x, y, zero, cross: CARDINAL;
    M: ARRAY [1..Max] OF INTEGER;

BEGIN
    M[1] := 1;
    FOR n := 2 TO Max DO
        M[n] := 1;
        FOR k := 2 TO n DO
            M[n] := M[n] - M[n DIV k];
        END;
    END;

    WriteString("The first 99 Mertens numbers are:");
    WriteLn();
    FOR y := 0 TO 90 BY 10 DO
        FOR x := 0 TO 9 DO
            IF x+y=0 THEN WriteString("   ");
            ELSE WriteInt(M[x+y], 3);
            END;
        END;
        WriteLn();
    END;

    zero := 0;
    cross := 0;
    FOR n := 2 TO Max DO
        IF M[n] = 0 THEN
            zero := zero + 1;
            IF M[n-1] # 0 THEN
                cross := cross + 1;
            END;
        END;
    END;

    WriteString("M(n) is zero "); 
    WriteCard(zero,0); 
    WriteString(" times.");
    WriteLn();
    WriteString("M(n) crosses zero ");
    WriteCard(cross,0);
    WriteString(" times.");
    WriteLn();
END Mertens.

You may also check:How to resolve the algorithm Fast Fourier transform step by step in the Swift programming language
You may also check:How to resolve the algorithm Primality by trial division step by step in the UNIX Shell programming language
You may also check:How to resolve the algorithm Nth root step by step in the Lambdatalk programming language
You may also check:How to resolve the algorithm Factors of a Mersenne number step by step in the Fortran programming language
You may also check:How to resolve the algorithm Integer comparison step by step in the Clojure programming language