Perl Weekly Challenge 12 – Euclid Numbers

This week’s Perl Weekly Challenge, problem 1, reads:

The numbers formed by adding one to the products of the smallest primes are called the Euclid Numbers (see wiki). Write a script that finds the smallest Euclid Number that is not prime. This challenge was proposed by Laurent Rosenfeld.

The first Euclid numbers are 3, 7, and 31.   These are computed as follows:

We’ll take the first three prime numbers – 2, 3, and 5.

The corresponding Euclid number is the prime number multiplied by all the smaller prime numbers, with 1 added to it.

So the first one, 3, is just 2 (nothing to multiply it against) plus 1.

The second one is 3 * 2 plus 1, or 7.

The third one is 5 * 3 *2 + 1, which is 31.

How do you do this in code?

We can do this in two steps.

Step 1 – Find the Euclid Numbers

my $product = 1;
my $euclids = (2..∞).grep(*.is-prime).map( { ($product *= $_).succ } );

Let’s break that down.  Ignoring line 1 for now, we generate a sequence on line 2. This sequence is lazily evaluated – we don’t actually compute every euclid number, as you might expect if you’re used to most programming languages. But to understand this, we need to break it down a bit more.

First we start with (2..∞) – a sequence of numbers from two to infinity (if you have a distaste for non-ASCII characters, you can use (2..*) or (2..Inf) to represent essentially the same thing).  But it doesn’t create an array infinitely long, it creates a sequence, only computing the next number when something asks for it.

Next, we figure out the prime numbers, because Euclid numbers involve multiplying all the prime numbers up to a prime number.  We use a “grep” to do that. This, like the Unix command of the same name, removes anything that fails to match the condition (in this case,a  check that it is prime).  This grep() method on a sequence also supports lazy evaluation.

Then we do a map – a map() is just a transform of an element.  We pass map() a code block, which it evaluates when necessary to retrieve an element.

Remember that line I told you to ignore?  Well, it just created a $product variable set to 1.  The map() first multiplies that variable by the current element ($_), so for the first prime number, 2, it multiplies it by 2 – resulting in $product now equaling 2.  The code block then adds one (.succ does this), but not to the variable – it adds it to the value returned by the sequence of Euclid Numbers we are creating.

For the next sequence element, we execute this again, but the map() function now has $_ set to the second prime number, 3.  So we multiply $product (which is set to 2 now) by 3, and get 6. So $product now equal 6. We then return that value with 1 added to it.

So we have a lazy sequence of Euclid Numbers, as many as we need!

Step 2 – Find the First Non-Prime Euclid Number

The challenge doesn’t just want the first Euclid Number, it wants the first one that isn’t prime.

say $euclids.first(! *.is-prime);

That’s easy – we just ask for the first entry where *.is-prime is not true. Then we “say” it to output it to the user.  The first() method will keep moving along the sequence until the condition is true. In this case, it keeps moving along until it gets to a non-prime value.

Perl 6 makes expressing things like this beautiful and efficient!