How to resolve the algorithm Earliest difference between prime gaps step by step in the ALGOL 68 programming language

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

How to resolve the algorithm Earliest difference between prime gaps step by step in the ALGOL 68 programming language

Table of Contents

Problem Statement

When calculating prime numbers > 2, the difference between adjacent primes is always an even number. This difference, also referred to as the gap, varies in an random pattern; at least, no pattern has ever been discovered, and it is strongly conjectured that no pattern exists. However, it is also conjectured that between some two adjacent primes will be a gap corresponding to every positive even integer.

This task involves locating the minimal primes corresponding to those gaps. Though every gap value exists, they don't seem to come in any particular order. For example, this table shows the gaps and minimum starting value primes for 2 through 30:

For the purposes of this task, considering only primes greater than 2, consider prime gaps that differ by exactly two to be adjacent.

For each order of magnitude m from 10¹ through 10⁶:

For an m of 10¹; The start value of gap 2 is 3, the start value of gap 4 is 7, the difference is 7 - 3 or 4. 4 < 10¹ so keep going. The start value of gap 4 is 7, the start value of gap 6 is 23, the difference is 23 - 7, or 16. 16 > 10¹ so this the earliest adjacent gap difference > 10¹.

Note: the earliest value found for each order of magnitude may not be unique, in fact, is not unique; also, with the gaps in ascending order, the minimal starting values are not strictly ascending.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Earliest difference between prime gaps step by step in the ALGOL 68 programming language

Source code in the algol programming language

BEGIN # find the differences between primes for each value of the gap        #
      # the prime and the next                                               #
    PR read "primes.incl.a68" PR           # include prime utilities         #
    INT max prime     = 2 000 000;         # maximum prime we will consider  #
    []BOOL prime = PRIMESIEVE max prime;   # sieve the primes to max prime   #
    [ 1 : max prime OVER 2 ]INT start prime; # index of the first prime with #
                                             # gap of subscript / 2          #
    # find the prime gaps                                                    #
    FOR i TO UPB start prime DO start prime[ i ] := 0 OD;
    INT prev prime := 3;
    FOR i FROM 5 BY 2 TO UPB prime DO
        IF prime[ i ] THEN
            INT gap = ( i - prev prime ) OVER 2;
            IF start prime[ gap ] = 0 THEN
                start prime[ gap ] := prev prime
            FI;
            prev prime := i
        FI
    OD;

    # to reiterate the task: we must find the earliest start primes where    #
    # the distance betweeen the gaps is 10, 100, 1000, 10 000 etc.           #
    # The distance is the distance between the start prime with gap g and    #
    # start prime with the a gap of g + 2, e.g. 3 has a gap of 2 as the next #
    # prime is 5, 7 has a gap of 4 as the next prime is 11, so the distance  #
    # is: 7 - 3 = 4                                                          #

    # shows a prime gap                                                      #
    PROC show gap = ( INT start pos )VOID:
         print( ( whole( start prime[ start pos ], 0 )
                , "(", whole( start pos * 2, 0 ),")"
                , whole( start prime[ start pos ] + ( start pos * 2 ), 0 )
                )
              ); 
    # shows a prime gap distance                                             #
    PROC show distance = ( INT gap, pos )VOID:
         BEGIN
            print( ( "First distance > ", whole( gap, 0 )
                   , " betweeen prime gaps:", newline
                   , "    ", whole( ABS ( start prime[ pos + 1 ] - start prime[ pos ] ), 0 )
                   , " between "
                   )
                 );
            show gap( pos );
            print( " and " );
            show gap( pos + 1 );
            print( ( newline ) )
         END # show distance # ;
    INT g10 := 0, g100 := 0, gt := 0, g10t := 0, g100t := 0, gm := 0;
    FOR i TO UPB start prime - 1 DO
        IF start prime[ i ] /= 0 AND start prime[ i + 1 ] /= 0 THEN
            INT  distance = ABS ( start prime[ i + 1 ] - start prime[ i ] );
            IF   distance > 10
            THEN
                 IF g10   = 0 THEN g10    := i FI
            FI;
            IF   distance > 100
            THEN
                 IF g100  = 0 THEN g100  := i FI
            FI;
            IF   distance > 1 000
            THEN
                 IF gt    = 0 THEN gt    := i FI
            FI;
            IF   distance > 10 000
            THEN
                 IF g10t  = 0 THEN g10t  := i FI
            FI;
            IF   distance > 100 000
            THEN
                 IF g100t = 0 THEN g100t := i FI
            FI;
            IF   distance > 1 000 000
            THEN
                 IF gm    = 0 THEN gm     := i FI
            FI
        FI
    OD;
    show distance(        10, g10   );
    show distance(       100, g100  );
    show distance(     1 000, gt    );
    show distance(    10 000, g10t  );
    show distance(   100 000, g100t );
    show distance( 1 000 000, gm    )
END

You may also check:How to resolve the algorithm Hostname step by step in the Maple programming language
You may also check:How to resolve the algorithm Angle difference between two bearings step by step in the Swift programming language
You may also check:How to resolve the algorithm Last Friday of each month step by step in the TUSCRIPT programming language
You may also check:How to resolve the algorithm Hello world/Text step by step in the GML programming language
You may also check:How to resolve the algorithm Probabilistic choice step by step in the J programming language