How to resolve the algorithm Sphenic numbers step by step in the ALGOL 68 programming language

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

How to resolve the algorithm Sphenic numbers step by step in the ALGOL 68 programming language

Table of Contents

Problem Statement

A sphenic number is a positive integer that is the product of three distinct prime numbers. More technically it's a square-free 3-almost prime (see Related tasks below). For the purposes of this task, a sphenic triplet is a group of three sphenic numbers which are consecutive. Note that sphenic quadruplets are not possible because every fourth consecutive positive integer is divisible by 4 (= 2 x 2) and its prime factors would not therefore be distinct. 30 (= 2 x 3 x 5) is a sphenic number and is also clearly the first one. [1309, 1310, 1311] is a sphenic triplet because 1309 (= 7 x 11 x 17), 1310 (= 2 x 5 x 31) and 1311 (= 3 x 19 x 23) are 3 consecutive sphenic numbers. Calculate and show here:

  1. All sphenic numbers less than 1,000.
  2. All sphenic triplets less than 10,000.
  3. How many sphenic numbers are there less than 1 million?
  4. How many sphenic triplets are there less than 1 million?
  5. What is the 200,000th sphenic number and its 3 prime factors?
  6. What is the 5,000th sphenic triplet? Hint: you only need to consider sphenic numbers less than 1 million to answer 5. and 6.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sphenic numbers step by step in the ALGOL 68 programming language

Source code in the algol programming language

BEGIN # find some Sphenic numbers - numbers that are the product of three     #
      # distinct primes                                                       #
    PR read "primes.incl.A68" PR                    # include prime utilities #
    INT max sphenic   = 1 000 000;          # maximum number we will consider #
    INT max prime     = max sphenic OVER ( 2 * 3 );    # maximum prime needed #
    []BOOL prime      = PRIMESIEVE max prime;
    # construct a list of the primes up to the maximum prime to consider      #
    []INT  prime list = EXTRACTPRIMESUPTO max prime FROMPRIMESIEVE prime;
    # form a sieve of Sphenic numbers                                         #
    [ 1 : max sphenic ]BOOL sphenic;
    FOR i TO UPB sphenic DO sphenic[ i ] := FALSE OD;
    INT cube root max = ENTIER exp( ln( max sphenic ) / 3 );
    FOR i WHILE INT p1 = prime list[ i ];
                p1 < cube root max
    DO
        FOR j FROM i + 1 WHILE INT p2   = prime list[ j ];
                               INT p1p2 = p1 * p2;
                               ( p1p2 * p2 ) < max sphenic
        DO
            INT max p3 = max sphenic OVER p1p2;
            FOR k FROM j + 1 TO UPB prime list WHILE INT p3 = prime list[ k ];
                                                     p3 <= max p3
            DO
                sphenic[ p1p2 * p3 ] := TRUE
            OD
        OD
    OD;
    # show the Sphenic numbers up to 1 000 and triplets to 10 000             #
    print( ( "Sphenic numbers up to 1 000:", newline ) );
    INT s count := 0;
    FOR i TO 1 000 DO
        IF sphenic[ i ] THEN
            print( ( whole( i, -5 ) ) );
            IF ( s count +:= 1 ) MOD 15 = 0 THEN print( ( newline ) ) FI
        FI
    OD;
    print( ( newline ) );
    print( ( "Sphenic triplets up to 10 000:", newline ) );
    INT t count := 0;
    FOR i TO 10 000 - 2 DO
        IF sphenic[ i ] AND sphenic[ i + 1 ] AND sphenic[ i + 2 ] THEN
            print( ( "  (", whole( i,     -4 )
                   , ", ",  whole( i + 1, -4 )
                   , ", ",  whole( i + 2, -4 )
                   , ")"
                   )
                 );
            IF ( t count +:= 1 ) MOD 3 = 0 THEN print( ( newline ) ) FI
        FI
    OD;
    # count the Sphenic numbers and Sphenic triplets and find specific        #
    # Sphenic numbers and triplets                                            #
    s count := t count := 0;
    INT s200k := 0;
    INT t5k   := 0;
    FOR i TO UPB sphenic - 2 DO
        IF sphenic[ i ] THEN
            s count +:= 1;
            IF s count = 200 000 THEN
                # found the 200 000th Sphenic number                          #
                s200k := i
            FI;
            IF sphenic[ i + 1 ] AND sphenic[ i + 2 ] THEN
                t count +:= 1;
                IF t count = 5 000 THEN
                    # found the 5 000th Sphenic triplet                       #
                    t5k := i
                FI
            FI
        FI
    OD;
    FOR i FROM UPB sphenic - 1 TO UPB sphenic DO
        IF sphenic[ i ] THEN
            s count +:= 1
        FI
    OD;
    print( ( newline ) );
    print( ( "Number of Sphenic numbers  up to 1 000 000: ", whole( s count, -8 ), newline ) );
    print( ( "Number of Sphenic triplets up to 1 000 000: ", whole( t count, -8 ), newline ) );
    print( ( "The 200 000th Sphenic number:  ", whole( s200k, 0 ) ) );
    # factorise the 200 000th Sphenic number                                  #
    INT f count := 0;
    FOR i WHILE f count < 3 DO
        INT p = prime list[ i ];
        IF s200k MOD p = 0 THEN
            print( ( IF ( f count +:= 1 ) = 1 THEN ": " ELSE " * " FI
                   , whole( p, 0 )
                   )
                 )
        FI
    OD;
    print( ( newline ) );
    print( ( "The   5 000th Sphenic triplet: "
           , whole( t5k, 0 ), ", ", whole( t5k + 1, 0 ), ", ", whole( t5k + 2, 0 )
           , newline
           )
         )
END

You may also check:How to resolve the algorithm N'th step by step in the Java programming language
You may also check:How to resolve the algorithm Binary search step by step in the GAP programming language
You may also check:How to resolve the algorithm History variables step by step in the Go programming language
You may also check:How to resolve the algorithm Hello world/Text step by step in the Nutt programming language
You may also check:How to resolve the algorithm Five weekends step by step in the Ada programming language