Update ... Monday morning ... Final runs are underway, results by
  tonight .... in the meantime, here's some more reading material!
=Fred

 **********************************************************************
 *   You can thank Rich Coco (Seive, Fermat, Euler), Bob Hall (Miller-Rabin),
 *     Jim Roche, Allan Wilks, and the POTM-master for this file.
 *   ... with any sort of luck, it's actually both accurate and useful!
 * ====================================================================
 * 			MATHEMATICS BACKGROUND
 * ====================================================================
 *
 * There are four methods that may be of interest in determining
 * prime numbers described in this mail: 
 *
 *   The Seive of Eratosthenes generates a list of prime numbers;
 *   The Miller-Rabin test produces a strong likelihood of primality
 *      by examining the modulus of an exponetiation operation;
 *   Fermat's Method is a method for testing primality by investigating
 *      whether a number can be decomposed into the difference of 2 squares;
 *   Euler's Method is another method for testing primality by investigating
 *      whether a number can be decomposed into the sum of 2 squares.
 *
 *   Plus some useful tricks you may not have known about!!!
 *
 *  Consider the nine digit number X = d8d7d6d5d4d3d2d1d0 ....
 *
 *  well, we all know that if N = d8+d7+d6+d5+d4+d3+d2+d1+d0 is divisible
 *    by 9, then X is divisible by 9.  More importantly for this problem,
 *    if N is divisible by 3, then X is divisible by 3.
 *
 *  and, of course, by looking at d0 we can figure out if X is divisible
 *    by 2 or by 5.
 *
 *	  BUT ... here's three more you may not have known about 
 *			courtesy of Allan Wilks and me!!!
 *
 *    if N = (d0-d3+d6) + 2*(d2-d5+d8) + 3*(d1-d4+d7) is divisible by 7
 *    then X is divisible by 7.   Did I hear someone say howcum????
 *    Well it's true, and I'll send you the proof ... but I found it
 *    to be fun to try and prove it myself.  (Gee, guess I need a life!)
 *
 *    if N = d0-d1+d2-d3+d4-d5+d6-d7+d8 is divisible by 11, then X
 *    is divisible by 11 ... try proving this one before you tackle the 7s!
 *
 *    if N = (d0-d3+d6) - 3*(d1-d4+d7) - 4*(d2-d5+d8) is divisible by 13,
 *    would you believe that X is divisible by 13 ???
 *
 * Now .... on to the heavy stuff !!!!
 *
 * ====================================================================
 * 1. Eratosthene's Seive
 *
 *	  Eratosthene's Seive basically involves stepping through
 *	  a contiguous sequence of integers (starting from 2)
 *	  removing all multiples of the current integer.
 *	  The ones that remain are prime.
 *	  To determine all the primes that might divide a given
 *	  number N, it suffices to seive the sequence bounded by
 *	  [sqrt(N)] ([x] = integr part of x).
 *
 *	  For this POTM, N < 10^9 (1 billion)
 *	  There are roughly 50,847,478 primes embedded in the first
 *	  one billion natural numbers!
 *	  However, we need only look at primes less than x^(1/2)
 *	  to determine if x is prime. For x = 1,000,000,000, x^(1/2) = 31622.78
 *
 ****************************************************************************
 *  The following is a program fragment (from the POTM-master entry) that
 *  implements the sieve with no multiplication ... courtesy of Knuth!
 ****************************************************************************

/*        Prepare for the job of prime-finding by computing all the
          possible factors of numbers less than 10^9 ... it turns
          out that there are 3401 of them (including 2) ...              */

/* This is the Sieve of Eratosthenes as described in Knuth, Vol 2, 
     section 4.5.4 problem 8 applied to the proiblem of finding
     all odd primes less than the square root of 10^9 without doing
     any multiplication ... the list is stored in prime_list[i]          */

     JMAX=15812;      /*       2*JMAX > sqrt(1,000,000,000)              */
                      /* there should be 3401 of them (with 2)           */

     prime_list[1]=2;
     i=1;
     for(k=1; k<JMAX; k++)           /* index into the number 2*k+1      */
          {
          if(is_composite[k]==0)     /* do nothing unless k reps a prime */
               {
               p=k+k+1;
               prime_list[++i]=p;
               /* if we reach here, p is a prime!                        */
               /* printf("     %d IS A PRIME\n",p);                      */

               for(k2=k+p;k2<JMAX; k2+=p)
               /* get rid of all odd multiples of p=2*k+1                */
               /*  by marking them as composite.
               /* note that only ODD multiples need be considered        */
               /* get rid of them by marking them as composite           */
                    {
                    is_composite[k2]=1;
                    }
               }
          }
     /* printf("Found %d primes less than %d\n",i,2*k+1);               */
 
 ****************************************************************************
 *
 * 2. The Miller-Rabin Test
 *
 * The Miller-Rabin primality test is an algorithm for probabilistically
 * testing a number for primality that is based on two group-theoretic
 * ideas.  For a much better and more precise exposition, you can read
 * about it in the Cormen/Rivest/Leiserson algorithm book (for example).
 * First, Fermat proved what is now known as "Fermat's Little Theorem"
 * which says:
 * 
 *    a^(n-1) = 1 (mod n)   for all a whenever n is prime. (^ means exponent)
 * 
 * (This is a special case of the group-theory result that raising a group
 * element to the order of the group (number of elements in the group)
 * always gives you the identity.  The group in this case is the
 * group of all numbers less than n that are prime to n under multiplication
 * mod n, sometimes denoted Z*(n).  When n is prime, this group includes all
 * positive numbers less than n.) 
 *
 * To apply this to primality testing, just notice that if n is *not* prime
 * then raising a to the n-1 mod n is rather *unlikely* to produce 1 mod n.
 * 
 * Thus, if we pick some random numbers less than n and exponentiate them as
 * above, the chances of all of them passing the test (i.e. producing 1 mod n)
 * and yet n not being prime gets small exponentially fast.  (Well, except
 * for certain rare integers called "Carmichael numbers" which are composite
 * yet produce 1 mod n for all a.  These are very rare, and can be caught
 * in some cases by the second technique (see below).
 * 
 * The thing that makes this a fast way to test a large n is that there is
 * a really cool way to exponentiate modulo n very rapidly.  This algorithm
 * involves repeatedly squaring modulo n and multiplying by a mod n, a 
 * worst-case total of k times each, where k is the number of bits in (n-1).
 * 
 * The second technique is to watch every time you do a squaring modulo n
 * in the course of doing the exponentiation and see if you get 1 mod n.
 * That is, notice if you hit an x (not equal to 1 or (n-1)) such that
 * x^2 mod n = 1.  If you do, then we know that x^2 - 1 = kn for some k
 * (by definition of modulo), so that (x-1)(x+1)=kn, which implies n divides
 * either (x-1) or (x+1) if n is prime (by the Unique Factorization Theorem).
 * But x+1 is less than n by hypothesis, so n has to be composite.
 * 
 * Miller-Rabin just combines these two ideas (exponentiating mod n some
 * random numbers less than n, and watching for nontrivial square roots of
 * unity mod n) into a single, elegant (and fast for large n, much faster
 * than repeated divisions) algorithm.
 * 
 * Notice that if the algorithm claims n is composite, you can be sure of
 * the answer, but if it claims n is prime, then you only have high confidence
 * (more random tests means higher confidence at an exponential rate).
 * Note also that it does not give any way of factoring the number.
 *
 *   POTM-master note:  it appears as though the HOT-DOG square caused
 *   alot of programs to deduce that 74447447 was composite
 *   (it is really prime!) and skip over it to arrive at 44404447 ... I
 *   don't think that Miller-Rabin can make THIS kind of error since a
 *   declaration of "composite" is always accurate ....
 *
 *   As far as which value(s) of "a" to use when you test, it seems that
 *   most folks used "2", "3", "5", or "7" .... and did three different Miller
 *   tests to deduce a high likelihood of primality.  Bob Hall's totient
 *   uses "2" and "3234" .... which Bob claims is satisfactory for the
 *   range of numbers in this problem!
 *
 *   Jim Roche suggested the following grid to try and catch folks who
 *   only used a single Fermat-based test to the base 2.
 *
 *  9 0 2 5 6
 *  0 0 0 0 6
 *  0 0 0 0 5
 *  7 0 6 0 0
 *  2 5 3 5 1
 *  
 *  Jim writes ....  The main point is that the number
 *  902566501 (easily seen in the grid) is a "strong pseudoprime to the
 *  base 2" for a primality test based on Fermat's Little Theorem.
 *  Virtually all numbers that pass the Fermat-based test to the base 2
 *  are actually prime, and I'm guessing that some of the contestants will
 *  be tempted to cut corners and stop after doing this single fast test.
 *  If they do, they'll incorrectly print out 902566501 as the largest
 *  prime in the grid, when in fact the largest prime is 902560051.
 *
 *  Apparently,  2^(902566501-1) = 1 mod 902566501 ... go figure!
 *
 *  Allan Wilks apparently did a fairly thorough analysis.  He writes:
 *
 * For your interest, the only numbers less than 10^9 that pass Miller's 
 * test to the bases 2, 3 and 5 are as follows:
 *
 *             25,326,001         161,304,001         960,946,321
 *
 * Of course, I tried to constuct squares that would cause folks to run
 * across one of these numbers, but I couldn't manage it ... I don't hold
 * out any hope for a square with the first two, but that third one ... (??)
 * 
 ****************************************************************************
 *
 * 3. Fermat's Factorization Method
 *
 *	  Fermat's Factorization Method provides a general method for
 *	  determining whether a given odd number is composite,
 *	  based on whether or not it can be expressed as the
 *	  difference of 2 squares. The following theorem applies.
 *
 *	  Theorem:
 *		Let N be an odd integer.
 *		N is composite if, and only if, (IFF) it can be
 *		expressed as the difference of two squares.
 *		That is;
 *
 *			N = ab  IFF  N = x^2 - y^2;
 *
 *		where (1 <= a <= b), x = (b+a)/2,  y = (b-a)/2.
 *
 *	  In order to apply the theorem, we note that we can write
 *
 *			x^2 - N = y^2
 *
 *	  Then we can substitute values of x starting with
 *	  x = ([sqrt(N)] + 1); where [x] = integer part of x.
 *	  If N is composite (not a prime), we will eventually
 *	  find a value of x for which (x^2 - N) is a square.
 *	  Rather than compute x^2, (x+1)^2, (x+2)^2, etc...
 *	  Fermat observed the following scheme:
 *
 *		(x + 1)^2 - N = (x^2 - N) + (2x + 1)
 *		(x + 2)^2 - N = [(x+1)^2 - N] + (2x + 3)
 *		(x + 3)^2 - N = [(x+2)^2 - N] + (2x + 5)
 *			.  .  .
 *
 *	  This observation greatly reduces and simplifies
 *	  the necessary computations.
 *
 *	  One disadvantage of this method:
 *	  since we are trying to express N as the 'difference' of
 *	  two squares, we must try values of x in the interval
 *	  [[sqrt(N)] + 1, N]. For large N, this can involve alot
 *	  of attempts. Thus, it's somewhat expensive to conclude
 *	  a large number is prime. 
 *
 ****************************************************************************
 *	  
 * 4. Euler's Method
 *
 *	  Euler's Method applies to integers of the form: 4k + 1.
 *	  A number of theorems are involved, so we will just
 *	  summarize the results w/o stating each Thoerem.
 *	  The procedure is referred to as Euler's Method
 *	  because the main factorization method ((a) below) is
 *	  commonly ascribed to him (although the method was
 *	  apparently known to Mersenne and de Bessy,
 *	  Euler was the first person to use it extensively).
 *
 *	  If N = 4k + 1, then
 *
 *	     (a) if N cannot be written as the sum of two squares,
 *		 then N is composite with an even number of prime
 *		 factors of form '4k + 3', at least 2 of which are
 *		 distinct.
 *
 *	     (b) if N can be written as the sum of two squares
 *		 which are not relatively prime, then N is composite
 *		 and has greatest common divisor (gcd) of the two
 *		 squares as a factor.
 *
 *	     (c) if N can be written as the sum of two relatively
 *		 prime squares in just one way, then N is prime.
 *		 
 *	     (d) if N can be written as the sum of two sqaures
 *		 in two distinct ways, then N is composite
 *		 and has an interesting factorization in terms
 *		 of these squares. See the theory (e.g., "Introduction
 *		 to Number Theory", James Shockley, Publisher: Holt,
 *		 Rinehard, and Winston, 1967).
 *	  
 *	  To apply Euler's Method, observe that if N = x^2 + y^2,
 *	  then either x < N/2 or y < N/2. Thus, one only has to check
 *	  (N - a^2) for square-ness for values of 'a' in the set
 *	  {1, 2, ..., [sqrt(N/2)]}. For large N, this involves far
 *	  fewer checks than Fermat's Method. In additon, note how
 *	  simple it is to determine, in software, if N = 4k + 1:
 *	  merely check the value ((N-1) & 0x03). Only if this value is
 *	  NULL can N = 4k + 1. No expensive divisions are involved.
 *	  As with Fermat's Method, the computations are greatly
 *	  simplified by noting that:
 *
 *		N - (a - 1)^2  =  (N - a^2) + 2a - 1
 *		N - (a - 2)^2  =  (N - (a - 1)^2) + 2a - 3
 *		N - (a - 3)^2  =  (N - (a - 2)^2) + 2a - 5
 *			.   .   .   .
 *
 *	  In addition, for both Fermat and Euler Method's,
 *	  we can greatly reduce the number of candidates
 *	  for square-ness by observation of the last 1 or 2 digits
 *	  of the integer in question.
 *	  For example, by computing the squares of
 *	  0, 1, 2, ..., 9 modulo 10, we see that integers ending in
 *	  2, 3, 7, or 8 cannot be square; eliminating 40% of possible
 *	  integers from consideration.
 *	  Repeating this process for modulus 100, we see that a
 *	  square must end in one of the following pairs of digits:
 *
 *	  	00  16  21  36  41  56  61  76  81  96
 *	  	01      24      44      64      84
 *	  	04      25      49      69      89
 *		09      29
 *
 *	  We can determine that 78% of numbers are not squares
 *        by checking the last 2 digits.
 *
 **********************************************************************