How to resolve the algorithm Euclid-Mullin sequence step by step in the AWK programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Euclid-Mullin sequence step by step in the AWK programming language

Table of Contents

Problem Statement

The Euclid–Mullin sequence is an infinite sequence of distinct prime numbers, in which each element is the least prime factor of one plus the product of all earlier elements. The first element is usually assumed to be 2. So the second element is : (2) + 1 = 3 and the third element is : (2 x 3) + 1 = 7 as this is prime. Although intermingled with smaller elements, the sequence can produce very large elements quite quickly and only the first 51 have been computed at the time of writing. Compute and show here the first 16 elements of the sequence or, if your language does not support arbitrary precision arithmetic, as many as you can. Compute the next 11 elements of the sequence. OEIS sequence A000945

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Euclid-Mullin sequence step by step in the AWK programming language

Source code in the awk programming language

# syntax: GAWK -f EUCLID-MULLIN_SEQUENCE.AWK
# converted from FreeBASIC
BEGIN {
    limit = 7 # we'll stop here
    arr[0] = 2
    printf("%s ",arr[0])
    for (i=1; i<=limit; i++) {
      k = 3
      while (1) {
        em = 1
        for (j=0; j<=i-1; j++) {
          em = (em * arr[j]) % k
        }
        em = (em + 1) % k
        if (em == 0) {
          arr[i] = k
          printf("%s ",arr[i])
          break
        }
        k += 2
      }
    }
    printf("\n")
    exit(0)
}


# find elements of the Euclid-Mullin sequence: starting from 2,
# the next element is the smallest prime factor of 1 + the product
# of the previous elements
BEGIN {
    printf( "2" );
    product = 2;
    for( i = 2; i <= 8; i ++ )
    {
        nextV = product + 1;
        # find the first prime factor of nextV
        p = 3;
        found = 0;
        while( p * p <= nextV && ! ( found = nextV % p == 0 ) )
        {
            p += 2;
        }
        if( found )
        {
            nextV = p;
        }
        printf( " %d", nextV );
        product *= nextV
    }
}


  

You may also check:How to resolve the algorithm Ray-casting algorithm step by step in the Python programming language
You may also check:How to resolve the algorithm Check that file exists step by step in the zkl programming language
You may also check:How to resolve the algorithm Unix/ls step by step in the J programming language
You may also check:How to resolve the algorithm Stern-Brocot sequence step by step in the Java programming language
You may also check:How to resolve the algorithm Last letter-first letter step by step in the Rust programming language