Question 4 has been out for a while now and it's taken me a while to blog the solution for a couple of reasons, I've not had much time to work out the solution recently, and this question seems a lot more difficult than the other three (for me at least).
Here's my question this time around:
Find the smallest number that can be expressed as
the sum of 25 consecutive prime numbers,
the sum of 99 consecutive prime numbers,
the sum of 189 consecutive prime numbers,
the sum of 467 consecutive prime numbers,
the sum of 535 consecutive prime numbers,
and is itself a prime number.
For example, 41 is the smallest prime number that can be expressed as
the sum of 3 consecutive primes (11 + 13 + 17 = 41) and
the sum of 6 consecutive primes (2 + 3 + 5 + 7 + 11 + 13 = 41).
First of all I thought I'd write a routine (once again in Perl) to generate prime numbers. I know I'm not entering a competition to find the worlds largest primes so chose to write an optimised solution rather than a super efficient one. The difference here is computational complexity v coding complexity. I chose the simpler code but less efficient solution rather than the more complicated code but efficient solutions offered by algorithms such as the
Sieve of Eratosthenes.
sub primes {
my $max = shift || 10;
my @primes = ( 2, 3, 5, 7 );
return @primes if ($max <= 9);
my $loop = 9;
while (scalar(@primes) < $max) {
my $is_prime = 1;
for (my $div = 3; $div < ($loop-1)/2; $div++) {
$is_prime = 0 if ($loop % $div == 0);
}
push (@primes,$loop) if ($is_prime);
$loop += 2;
}
return @primes;
}Now I had a way of populating an array with prime numbers I thought about the solution a bit more carefully and decided it wasn't likely to be simple to calculate, however long the code I managed to write was. So, I decided to search around for lists of prime numbers and decided to use a list of the
first million primes. I could, on reflection, just used my routine to generate 1 million primes and written them to a file instead of generating each time.
The solution I came up with is shown below. It starts by populating an array with the first million primes from the downloaded file. Then the sums of the required continuous number of primes are generated and stored in another array. At this early stage, the solution is now contained in this array (with the assumption the solution exists within the first one million primes of course) so it's just a case of searching the array to find it. In order to find the number, I numerically sort the list. Now it's a simple case of finding the first (and therefore lowest) prime in the new list that is repeated 5 times.
use strict;
use FileHandle;
sub sum_primes {
my $amount = shift;
my $start = 0;
my @sums;
while ($amount < scalar(@_)) {
my $sum = 0;
for (my $i = $start; $i < $amount; $i++) {
$sum += $_[$i];
}
push(@sums,$sum);
$start++;
$amount++;
}
return @sums;
}
sub read_primes {
my $filename = shift;
my $fh = new FileHandle;
$fh->open($filename) || die "$filename: $!\n";
my @primes;
push(@primes,split) while (<$fh>);
$fh->close();
return @primes;
}
sub is_prime {
my $num = shift;
foreach my $prime (@_) {
return 1 if ($num == $prime);
}
return 0;
}
my @primes = read_primes("1000000.txt");
my @sum_list;
push(@sum_list, sum_primes(25,@primes));
push(@sum_list, sum_primes(99,@primes));
push(@sum_list, sum_primes(189,@primes));
push(@sum_list, sum_primes(467,@primes));
push(@sum_list, sum_primes(535,@primes));
@sum_list = sort(@sum_list);
my $prev = 0;
my $same = 0;
foreach my $num (@sum_list) {
if ($num == $prev) {
$same++;
if ($same == 4) {
print "Found $num, checking... ";
if (is_prime($num,@primes)) {
print "PRIME! :-)\n";;
last;
} else {
print "not prime :-(\n";
$same = 0;
}
}
} else {
$same = 0;
}
$prev = $num;
}
This code takes a few minutes to run. I'm sure it's not the smartest solution to the problem, there must be some maths I can use to calculate a solution. Instead, this approach turns the problem into a search solution but it works pretty well and identified the correct answer of 6990493 for my question.
My second choice of home media server arrived on my doorstep last week after my unwillingness to maintain the painfully slow and awkward slug. This time around I've plumped for a TinyTuxbox Series 8 which seems to be a UK resold version of the e-Box 4300. It fits the extra requirements I made after parting with the SLUG, that is it's an x86 based machine and has lots more memory. I'm not the only one at work with one of these types of boxes either, James Taylor has the Netvoyager re-badged version of the previous box to my one, the e-Box 2300.
It is, in fact, a fully functional x86 PC but just a really small one, even smaller than the pretty tiny Fit-PC which I was also seriously considering and probably would have gone for were it not for the excellent pre-sales support of one of the TinyTuxbox staff over e-mail. That said, the excellent pre-sales was balanced with painfully slow delivery. It took 28 days to get it to my door which for a delivery cost of nearly £20 I consider poor. I've been left with a upward feeling though, post-sales support has been promising too as I initially had some problems installing the box, which it turned out were my fault and I solved quickly enough anyway. I'm not going to talk software here though, that's a story for another day. So how does my TinyTuxbox look and spec up....?
The workhorse of the TinyTuxbox is the 500MHz Via Eden ULV processor which provides a 32-bit x86 processor along with a built-in graphics processor with hardware MPEG decoding. The processor is an impressive bit of kit, it runs all that from just 1 watt of power, see the link for the full specs! Away from the processor we have 512MB RAM (some of which is shared for the video output), on-board Ethernet, 3 USB ports, VGA output, a PS/2 connector (supplied with PS/2 Y-Splitter cable to connect both keyboard and mouse), a compact flash slot, sound in and out, power button, and hard disk and power LEDs. The box is also fitted with an IDE connector and can house a 2½" laptop type hard disk in it. I ordered it without the hard disk and fitted my own as the supplied ones were not good value for money probably due to the services incurred from the fitting itself.
The TinyTuxbox site advertises the unit as consuming a maximum of 8 watts and I'm pleased to report that was absolutely accurate. According to my current cost meter, it uses 8 watts with the hard disk spinning so once I get it to spin down on idle it should use very little juice. Click the various images for a link to my Flickr page and some more notes.
