=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