Peter
Peter Campbell Smith

Primorials and
Kronecker products

Weekly challenge 170 — 20 June 2022

Week 170: 20 Jun 2022

Task 1

Task — Primorial numbers

Write a script to generate first 10 Primorial Numbers. Primorial numbers are those formed by multiplying successive prime numbers.

Examples


Example 1:
P(0) = 1    (1)
P(1) = 2    (1×2)
P(2) = 6    (1×2×3)
P(3) = 30   (1×2×3×5)
P(4) = 210  (1×2×3×5×7)

Analysis

I am always amazed at the way mathematicians find a meaning or a use for obscure sequences and mathematical operations. And here's another one: primorial P(n) is defined as the product of the first n prime numbers. That is true whether or not you accept 1 as the first prime, but apparently P(0) is 1 which neatly sidesteps that argument.

It's easy to see that successive primorials increase fast. We are asked to generate the first 10, and P(9) is already over 223 million, and after that we are quickly into BigInt territory.

As this is a relatively simple task I chose to generate the primes rather than using a module and my algorithm looks like this:

  • Set k = 1
  • Loop j from 2 until we've found P(9)
  • ... Next j if j is divisible by any prime we've found so far
  • ... So j is prime, save it
  • ... k = k * j, and k is the next primorial

I'm sure someone will come with a one-liner for this, but as always I tend to prioritise lucidity over brevity.

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2022-06-20
# PWC 170 task 1

use v5.28;
use strict;
use warnings;
use utf8;
binmode(STDOUT, ':utf8');

my (@primes, $j, $p, @pm, $k, $explain);

@primes = ();
$p = 1;
$pm[0] = 1;
$explain = '';
say qq[P(0) = 1];

OUTER: for $j (2 .. 99999) {
    for $k (@primes) {
        next OUTER if $j % $k == 0;   # $j is not prime if divisible by a smaller prime
    }
    
    # found a prime, create next primorial
    push @primes, $j;
    $pm[$p] = $pm[$p - 1] * $j;
    $explain .= qq[$j × ];
    printf("P(%d) = %d (%s)\n", $p, $pm[$p], substr($explain, 0, -3));
    $p ++;
    exit if $p == 10;
}

Output


P(0) = 1
P(1) = 2 (2)
P(2) = 6 (2 × 3)
P(3) = 30 (2 × 3 × 5)
P(4) = 210 (2 × 3 × 5 × 7)
P(5) = 2310 (2 × 3 × 5 × 7 × 11)
P(6) = 30030 (2 × 3 × 5 × 7 × 11 × 13)
P(7) = 510510 (2 × 3 × 5 × 7 × 11 × 13 × 17)
P(8) = 9699690 (2 × 3 × 5 × 7 × 11 × 13 × 17 × 19)
P(9) = 223092870 (2 × 3 × 5 × 7 × 11 × 13 × 17 × 19 × 23)

 

Any content of this website which has been created by Peter Campbell Smith is in the public domain