# Euclid and Reduce

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 Numberthat is not prime. This challenge was proposed byLaurent 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 **P _{n}#**. 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.