How to resolve the algorithm Mertens function step by step in the Cowgol programming language

Published on 12 May 2024 09:40 PM
#Cowgol

How to resolve the algorithm Mertens function step by step in the Cowgol 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 Cowgol programming language

Source code in the cowgol programming language

include "cowgol.coh";

const MAX := 1000;

# Table output
sub printtab(n: int8) is
    if n<0 then 
        print_char('-');
        n := -n;
    else 
        print_char(' ');
    end if;
    print_char(n as uint8 + '0');
    print_char(' ');
end sub;
    
# Generate Merten numbers
var M: int8[MAX+1];
M[0] := 0;
M[1] := 1;

var n: @indexof M := 2;
while n < @sizeof M loop
    M[n] := 1;
    var k: @indexof M := 2;
    while k <= n loop
        M[n] := M[n] - M[n/k];
        k := k + 1;
    end loop;
    n := n + 1;
end loop;

# Find zeroes and crossings
var zero: uint8 := 0;
var cross: uint8 := 0;
n := 1;
while n < @sizeof M loop
    if M[n] == 0 then
        zero := zero + 1;
        if M[n-1] != 0 then
            cross := cross + 1;
        end if;
    end if;
    n := n + 1;
end loop;

# Print table
print("The first 99 Mertens numbers are:\n");
print("   ");
n := 1;
var col: uint8 := 9;
while n < 100 loop
    printtab(M[n]);
    col := col - 1;
    if col == 0 then    
        print_nl();
        col := 10;
    end if;
    n := n + 1;
end loop;

print("M(n) is zero "); print_i8(zero); print(" times\n");
print("M(n) crosses zero "); print_i8(cross); print(" times\n");

You may also check:How to resolve the algorithm Executable library step by step in the PicoLisp programming language
You may also check:How to resolve the algorithm Binary digits step by step in the Nim programming language
You may also check:How to resolve the algorithm Dragon curve step by step in the ALGOL 68 programming language
You may also check:How to resolve the algorithm Natural sorting step by step in the J programming language
You may also check:How to resolve the algorithm Non-decimal radices/Convert step by step in the Mathematica/Wolfram Language programming language