=pod
=for advent_year 2008
=for advent_day 02
=for advent_title Primed for Christmas
=for advent_author Yanick Champoux
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 A.
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
=begin quote
Find the sum of all the multiples of 3 or 5 below 1000.
=end quote
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?).
=begin pre
perl -MList::Util=sum -le 'print sum grep { not( $_ % 3 and $_ % 5 ) } 3 .. 999;'
=end pre
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 M 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 I
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.N
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.N
Now, with the help of B and the help function
I, can you solve Project Euler's
A?
=begin quote
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?
=end quote
The helper function follows.
=sourcedcode mod2.pl
=begin footnote ed1
=end footnote
=begin eds
Similar results could be had with P<2000-18|Memoize>. —the management
=end eds
=begin footnote ed2
=end footnote
=begin eds
Using M::C would simplify the logic
by not rewriting binary search. —the management
=end eds