Holiday evenings...
Outside, the cold darkness is speckled with snowflakes slowly drifting down on the covered ground. Inside, the air is warm and filled with delicious kitchen smells. Christmas music softly plays from the radio. A perfect time to curl up in one's favorite rocking chair by the fireplace and, armed with a mug full of pipping hot eggnog, leisurely attack one's favorite form of brain teaser, let it be crosswords, sudokus or... maybe something a little more mathematical?
My own puzzles of choice come from Project Euler. The site provides a series of mathematical challenges that, once a correct way of tackling the problem has been found, can be solved by a program within one minute.
For example, the very first problem of the site is
Find the sum of all the multiples of 3 or 5 below 1000.
This is actually one of the easiest problems of the site and, after some minimal boolean logic juggling, can be solved by an elegant one-liner (can you find it before peeking at the code below?).
perl -MList::Util=sum -le 'print sum grep { not( $_ % 3 and $_ % 5 ) } 3 .. 999;'
It hardly comes as a surprise that a lot of those problems deal with—directly or indirectly—prime numbers. And while one can always recompute those prime numbers over and over again for each problem, it's just no fun. After doing it a few times, I decided that it'd be much more efficient to keep a database of prime numbers that I could reuse between problems.
As luck has it Math::Prime::TiedArray does exactly that. The module's API is very simple: tie an array to the module's class, and it will act as a virtual, infinite list of all primes. Of course, the array does not really hold all primes; it merely expand as needed. But that's okay, we're not greedy and that's more than enough to satisfy our needs. And, as a bonus, the module can also be called such that the computed primes are saved in file as well, ready to be retrieved and reused next time we need them.1
Most of the time, though, we are more interested to know if a given arbitrary number is prime. This can easily be figured out via a helping function.2
Now, with the help of Math::Prime::TiedArray and the help function is_prime(), can you solve Project Euler's problem 35?
The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
How many circular primes are there below one million?
The helper function follows.
1 { #Cuddled for closure 2 use Math::Prime::TiedArray; 3 tie my @primes, 'Math::Prime::TiedArray', cache => "primes.dbm"; 4 5 sub is_prime { 6 my $x = shift; 7 8 if ( $x > $primes[$#primes] ) { 9 10 # $x outside of the range of primes 11 # already found 12 13 my $i = 0; 14 while (1) { 15 my $p = $primes[ $i++ ]; # will magically grow as needed! 16 return 1 if $p > sqrt $x; 17 return 0 unless $x % $p; 18 } 19 } 20 21 # $x inside the range of primes already found 22 # we try to find it with a binary search 23 24 my $min = 0; 25 my $max = $#primes; 26 27 while ( $min <= $max ) { 28 my $middle = int $min + ( $max - $min ) / 2; 29 30 # ah AH! found it. it's a prime 31 return 1 if $primes[$middle] == $x; 32 33 if ( $primes[$middle] < $x ) { 34 $min = $middle + 1; 35 } 36 else { 37 $max = $middle - 1; 38 } 39 } 40 41 return 0; # not found in list, so not a prime 42 } 43 44 }
Similar results could be had with Memoize. —the management
Using List::Search::nlist_contains($x,\@primes) would simplify the logic by not rewriting binary search. —the management