Is 8,675,309 prime?

This semester, to remind today’s college students of the greatness of the 1980s: I made my class answer the following question on an exam:

Jenny wants to find out if 8,675,309 is prime. In a few sentences, describe an efficient procedure she could use to answer this question.

Amazingly, it turns out that 8,675,309 is a prime number, though I seriously doubt that Tommy Tutone had this fact in mind when he wrote the classic 80s song. To my great disappointment, nobody noticed (or at least admitted to noticing) the cultural significance of this number on the exam.

Naturally, I didn’t expect my students to actually determine this on a timed exam, and I put the following elaboration on the exam:

Although Jenny has a calculator, answering this question would take more than 80 minutes. So don’t try to find out if it’s prime or not! Instead, describe a procedure for answering the question and provide enough details so that Jenny could follow your directions. Since Jenny will need a lot of time, your procedure should be efficient, or as quick as possible (even if it takes hours).

Your answer should include directions for making a certain large list of prime numbers. Be sure to describe the boundaries of this list and how this list can be made efficiently. Hint: We described an algorithm for making such lists of prime numbers in class. (Again, do not actually construct this list.)

I thought it was reasonable to expect them to describe a process for making this determination on a timed exam.  Cultural allusions aside, I thought this was a good way of checking that they conceptually understood certain facts about prime numbers that we had discussed in class:

  • First, to check if 8,675,309 is prime, it suffices to check if any of positive prime numbers less than or equal to \sqrt{8,675,309} \approx 2,945.387\dots are factors of 8,675,309.
  • To make this list of prime numbers, the sieve of Eratosthenes can be employed. Notice that \sqrt{2,945} \approx 54.271\dots, and the largest prime number less than this number is 53. Therefore, to make this list of prime numbers, one could write down the numbers between 2 and 2,945 and then eliminate the nontrivial multiples of the prime numbers 2, 3, 5, 7, 11, \dots 53.
  • If none of the resulting prime numbers are factors of 8,675,309, then we can conclude that 8,675,309 is prime.

I was happy that most of my class got this answer either entirely correct or mostly correct… and I was also glad that nobody suggested the efficient one-sentence procedure “Google Is 8,675,309 prime?.”

2 thoughts on “Is 8,675,309 prime?

  1. Pretty long odds of ol’ Tommy Tutone blundering into such a significant prime number no? This was no boating accident…

    1. I know your question was asked tongue-in-cheek, but I was curious. According to Mathematica, there are 515,646 prime numbers between 2,000,000 and 9,999,999 (since a 7-digit US phone number can’t start with either a 0 or 1). So the odds of picking a prime number at random from this list would be about 6.4%, or odds of about 14.5:1.
      The odds are considerably better if we deliberately choose a phone number that doesn’t end in 0, 2, 4, 5, 6, or 8 (since clearly such numbers can’t be prime). If we deliberately avoid such numbers and don’t consider other divisibility tests — like the divisibility test for 3 — then the chances become 515,646 in 3,200,000, or about 1 chance in 6.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.