Prime Time

Every so often I go back through posts on my old blog, which is securely archived for my own random access.1 I read one the other day that made me chuckle with geekish delight as I read:

1,000,003 is the smallest seven-digit prime number I could think of, which, being completely impossible to wholly divide from, should take care of the repetitive quotes.

Backstory: I used to have a random quote generator made up of stupid phrases I'd collected over time. Some were output from fortune, some from movies or tv shows, and others were stupid inside jokes. There were far too many Family Guy references, IIRC. It played well to the quasi-personal, friends-oriented content I was producing at the time. Each quote was an entry in a MySQL table with a primary key which I used for retrieval based on this code:

$tq\_query = mysql\_query("select count(qid) from quotes") or die ('Invalid Query: ' . mysql_error());
$getQuote = sprintf("select quote from quotes where qid='%s';", addslashes(rand(1, mysql\_result($tq\_query,0)-1)));
$gq\_result = mysql\_query($getQuote) or die ('Invalid Query: ' . mysql_error());
echo mysql\_result($gq\_result,0);

Aside: As I copy and paste this now, I wonder why I didn't just do something like "SELECT quote FROM quotes ORDER BY rand() LIMIT 1", putting the responsibility for randomness on MySQL's already set up random seed? I may have been over-prioritizing database robustness on a site that never got more than a few hundred hits per day.

My girlfriend at the time (now my wife) noticed that the quotes didn't actually seem that random and, in fact, the same few kept repeating themselves over and over again. I had noticed the same thing, but never felt that motivated to investigate.2

After reading a bunch of threads on the PHP website, I reasoned that the problem was that I was seeding the random stack with an even number. Due to silly rounding and a padding value, the number most commonly returned out of this function was 24, which is incredibly un-prime. [Even cooler to the numbers nerd inside of me, 24 is the largest number divisible by all numbers less than its square root.] So.. following good number theory, I changed the seed value to 1000003, which is prime, and in few other ways special.

In additional retrospect, saying "that I could think of" was quite silly… The list of smallest n-digit primes is readily available, so this shouldn't require much thought at all. If memory serves, I don't believe I looked this up, and really, how hard should it be for someone who finds math fun to know that 100001 and 100002 aren't prime (11 and 2 are lowest divisors, respectively)?

  1. There are some fairly good posts on it about technology that wouldn’t make sense to re-post here, but are still a good reference for me.

  2. She was, I think, between classes and it bothered her… so who am I to argue?

May 19th, 2008