How to resolve the algorithm Meissel–Mertens constant step by step in the ALGOL 68 programming language

Published on 12 May 2024 09:40 PM
#Algol 68

How to resolve the algorithm Meissel–Mertens constant step by step in the ALGOL 68 programming language

Table of Contents

Problem Statement

Calculate Meissel–Mertens constant up to a precision your language can handle.

Analogous to Euler's constant, which is important in determining the sum of reciprocal natural numbers, Meissel-Mertens' constant is important in calculating the sum of reciprocal primes.

We consider the finite sum of reciprocal natural numbers: 1 + 1/2 + 1/3 + 1/4 + 1/5 ... 1/n this sum can be well approximated with: log(n) + E where E denotes Euler's constant: 0.57721... log(n) denotes the natural logarithm of n.

Now consider the finite sum of reciprocal primes: 1/2 + 1/3 + 1/5 + 1/7 + 1/11 ... 1/p this sum can be well approximated with: log( log(p) ) + M where M denotes Meissel-Mertens constant: 0.26149...

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Meissel–Mertens constant step by step in the ALGOL 68 programming language

Source code in the algol programming language

BEGIN # compute an approximation to the Meissel-Mertens constant             #
    # construct a sieve of odd primes                                        #
    [ 0 : 10 000 000 ]BOOL primes;
    BEGIN
        FOR i TO UPB primes DO primes[ i ] := TRUE  OD;
        INT ip := 1;
        FOR i WHILE i + ( ip +:= 2 ) <= UPB primes DO
            IF primes[ i ] THEN
                FOR s FROM i + ip BY ip TO UPB primes DO primes[ s ] := FALSE OD
            FI
        OD
    END;
    # sum the reciprocals of the primes                                      #
    INT       p count := 1;
    INT       last p  := 0;
    LONG REAL sum     := long ln( 0.5 ) + 0.5;
    INT       p       := 1;
    INT       p10     := 10;
    # Euler's constant from the wikipedia, truncated for LONG REAL           #
    LONG REAL eulers constant = 0.5772156649015328606 # 0651209008240243104215933593992 #;
    FOR i TO UPB primes DO
        p +:= 2;
        IF primes[ i ] THEN
            LONG REAL rp = 1 / LENG p;
            sum     +:= long ln( 1 - rp ) + rp;
            p count +:= 1;
            last p   := p;
            IF p count = p10 THEN
                print( ( "after ", whole( p count, -8 ), " primes, the approximation is: "
                       , fixed( sum + eulers constant, -14, 12 )
                       , ", last prime considered: ", whole( last p, 0 )
                       , newline
                       )
                     );
                p10 := IF p10 < 1 000 000 THEN p10 * 10 ELSE p10 + 1 000 000 FI
            FI
        FI   
    OD;
    print( ( "after ", whole( p count, -8 ), " primes, the approximation is: "
           , fixed( sum + eulers constant, -14, 12 )
           , ", last prime considered: ", whole( last p, 0 )
           , newline
           )
         )
END

You may also check:How to resolve the algorithm Dining philosophers step by step in the Julia programming language
You may also check:How to resolve the algorithm Hex words step by step in the Quackery programming language
You may also check:How to resolve the algorithm Align columns step by step in the PowerShell programming language
You may also check:How to resolve the algorithm Partition function P step by step in the C programming language
You may also check:How to resolve the algorithm Pointers and references step by step in the COBOL programming language