Week 12, Challenge 1

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.

From the Wiki:

Not all Euclid numbers are prime. E6 = 13# + 1 = 30031 = 59 × 509 is the first composite Euclid number.

Knowing where the right answer is is always useful.

Anyway, we’re talking primes, and I wrote some useful functions for week 8:

``````sub is_prime ( \$n ) {
my @factors = factor(\$n);
return scalar @factors == 1 ? 1 : 0;
}

sub factor ( \$n ) {
my @factors;
for my \$i ( 1 .. \$n - 1 ) {
push @factors, \$i if \$n % \$i == 0;
}
return @factors;
}
``````

And we can add a `while` loop and pick up more and more primes.

``````my @primes;

while (1) {
state \$n = 0;
\$n++;
if ( is_prime(\$n) ) {
push @primes, \$n;
# infinite loop, so we'll keep getting more and more primes forever
# remember, kids: last your loops!
}
}
``````

A Euclid Number is found by adding one to …well, Wikipedia puts it like Pn#. I think that’s product?

``````\$ perldoc -f product
No documentation for perl function 'product' found
``````

Hrm. I guess we have to build one.

I don’t know if these thoughts came more from Schwartzian Transforms or me simply trying to understand what Hadoop is and does, I’m more and more into the `map` and `grep` style of programming. `map` transforms each element in an array, and `grep` gives you a smaller array, but what if you want to boil an array into one value?

There are instances: `sum` gives you all the elements added together, `min` gives you the smallest value, and `max` would give you the largest. And, I should mention, these are from `List::Util`.

Get to know `List::Util`. It is your friend.

And one of the things you can get from `List::Util` is `reduce`. That’s the second half of MapReduce! Coolness.

``````my @list = 1 .. 4;

my \$max     = reduce { \$a > \$b ? \$a : \$b } @list ;  # 4
my \$min     = reduce { \$a < \$b ? \$a : \$b } @list ;  # 1
my \$sum     = reduce { \$a + \$b } @list ;            # 10
my \$product = reduce { \$a * \$b } @list ;            # 24
``````

And here is we get our `product`.

``````#!/usr/bin/env perl

use strict;
use warnings;
use utf8;
use feature qw{ postderef say signatures state };
no warnings
qw{ experimental::postderef experimental::smartmatch experimental::signatures };

use List::Util qw{reduce};

my @primes;

while (1) {
state \$n = 0;
\$n++;
if ( is_prime(\$n) ) {
push @primes, \$n;
my \$eu = 1 + reduce { \$a * \$b } @primes;
if ( !is_prime(\$eu) ) {
say join "\t", \$n, \$eu;
say join ',', @primes;
say join ',', factor(\$eu);
last;
}
}
}

sub is_prime ( \$n ) {
my @factors = factor(\$n);
return scalar @factors == 1 ? 1 : 0;
}

sub factor ( \$n ) {
my @factors;
for my \$i ( 1 .. \$n - 1 ) {
push @factors, \$i if \$n % \$i == 0;
}
return @factors;
}
``````

I could probably inject more clever, but this teaches `reduce` and gives us the right answer.

``````13	30031
2,3,5,7,11,13
1,59,509
``````

So excuse me as I take a victory lap.

If you have any questions or comments, I would be glad to hear it. Ask me on Twitter or make an issue on my blog repo.