Quickly recognizing primes less than 1000: memorizing exceptional composites

Posted on October 15, 2018 by Brent

In my previous post I wrote about a procedure for testing the primality of any number less than 1000:

  1. Test for divisibility by all primes up to 13, and also 19. (In practice I test for 2 and 5 first, which is pretty much automatic; then for 3 and 11, which both involve adding and subtracting digits; then 7 and 19, which both involve multiplying the final digit by two and either subtracting (7) or adding (19); and last I test for 13.)

  2. Check if the number is one of a memorized list of 18 composites less than 1000 which are not divisible by either 19 or any prime \leq 13. (In practice, of course, I do this check first, before doing any divisibility tests.)

How fast is it?

Using this method, presented with a random number from 1-1000 not divisible by 2 or 5 (I exclude those because I can pretty much tell they are not prime instantaneously, and I think it makes for a more interesting measurement to exclude them), right now it takes me on average 15 seconds to determine whether such a number is prime or not. Of course the variance is huge: numbers that are divisible by 3 I can identify in a second; for numbers that are actually prime, it can take me something like 40 seconds to run through all the divisibility tests in my head. I expect with practice I’ll get faster.

I’m still interested in exploring other methods as well, but figured this is something relatively simple that can provide a good baseline for comparison!

Memorizing exceptional composites

For the rest of the post I want to talk about how I memorized the list of exceptional composites. Here’s the list again, this time with prime factorizations given:

\begin{array}{rcl}289 &=& 17^2 \\ 391 &=& 17 \cdot 23 \\ 493 &=& 17 \cdot 29 \\ 527 &=& 17 \cdot 31 \\ 529 &=& 23^2 \\ 629 &=& 17 \cdot 37 \\ 667 &=& 23 \cdot 29 \\ 697 &=& 17 \cdot 41 \\ 713 &=& 23 \cdot 31 \\ 731 &=& 17 \cdot 43 \\ 799 &=& 17 \cdot 47 \\ 841 &=& 29^2 \\ 851 &=& 23 \cdot 37 \\ 899 &=& 29 \cdot 31 \\ 901 &=& 17 \cdot 53 \\ 943 &=& 23 \cdot 41 \\ 961 &=& 31^2 \\ 989 &=& 23 \cdot 43 \end{array}

That looks like a lot of stuff to memorize. And it would be, if you tried to memorize it as a bunch of individual, disconnected facts. But fortunately we can do better! Human brains are good at remembering sequences and stories. So we’re going to look at the numbers in order and tell ourselves stories about them. The better we get to know them and their relationships the easier they are to remember!

289, 391, 493

There is only one exceptional composite in each of the 200’s, 300’s, and 400’s, namely, 289, 391, and 493. What strikes one immediately about these numbers is that each is exactly 102 more than the previous. Is this a coincidence?

Of course not! It is actually due to the fact that 102 = 6 \cdot 17. Each of these numbers is a product of 17 with some other prime, and the second prime increases by 6 every time. That is, 289 = 17 \cdot 17, then 391 = 17 \cdot (17 + 6) = 17 \cdot 23, and 493 = 17 \cdot (23 + 6) = 17 \cdot 29. Of course adding 6 to a prime doesn’t always get us another prime—but it works surprisingly often for smaller primes. And every prime besides 2 and 3 is either one more than a multiple of 6, or one less. So if we start with 5 and 7 and keep adding 6, we will definitely hit all the primes.

This sequence of multiples of 17 starts from 17 \cdot 5, and if we continue it further we see that it contains several more numbers from our exceptional set as well:

\begin{array}{rcl}85 &=& 17 \cdot 5 \\ 187 &=& 17 \cdot 11 \\ \mathbf{289} &=& 17 \cdot 17 \\ \mathbf{391} &=& 17 \cdot 23 \\ \mathbf{493} &=& 17 \cdot 29 \\ 595 &=& 17 \cdot 35 \\ \mathbf{697} &=& 17 \cdot 41 \\ \mathbf{799} &=& 17 \cdot 47 \\ \mathbf{901} &=& 17 \cdot 53 \end{array}

What about if we start with 17 \cdot 7 and keep adding 102?

\begin{array}{rcl}119 &=& 17 \cdot 7 \\ 221 &=& 17 \cdot 13 \\ 323 &=& 17 \cdot 19 \\ 425 &=& 17 \cdot 25 \\ \mathbf{527} &=& 17 \cdot 31 \\ \mathbf{629} &=& 17 \cdot 37 \\ \mathbf{731} &=& 17 \cdot 43 \\ 833 &=& 17 \cdot 49 \end{array}

This sequence yields three of our exceptional composites, and quite a few others which in theory we can rule out with our divisibility tests but are probably worth knowing anyway (119, 221, 323, 833).

527, 529, 629, 667, 697

There are only two exceptional composites in the 500’s, and they are twins: 527 and 529. 527 we have already seen: it shows up in the sequence of multiples of 17 that begins with 17 \cdot 7. On the other hand 529 is 23^2.

The next exceptional composite is 629, the next multiple of 17 in the sequence after 527. Of course it is also exactly 100 bigger than 529. I personally find the sequence 527, 529, 629 to be quite memorable.

Next is 667 = 23 \cdot 29, which is the closest integer to two-thirds of 1000. If you know that 676 = 26^2, then 667 is also easy to remember for two reasons: it has the same digits as 676 but with the 7 and 6 reversed, and it is exactly 9 less than 676, and hence it is 26^2 - 3^2 = (26 - 3) \cdot (26 + 3).

The last exceptional composite in the 600’s is 697, which is from the sequence of multiples of 17 that started with 289, 391, 493 (595 is skipped because it is obviously a multiple of 5).

713, 731, 799, 841, 851, 899

Next come a pair of twins, a 99, then another pair of twins, then another 99! 713 and 731 are twins because they have the same digits, with the 1 and 3 reversed. 731 we have already seen: it is from the same 17-sequence as 527 and 629. 713 is 729 - 16 = 27^2 - 4^2 = (27-4)\cdot (27+4). 799 is again from the 17-sequence beginning with 289.

841 and 851 are twins because they have the same digits except the 4 and the 5, which are consecutive. 841 is 29^2, and 851 is 900 - 49 = 30^2 - 7^2 = (30 - 7) \cdot (30 + 7). Finally we have 899 which is 900 - 1 = 30^2 - 1^2 = (30 - 1) \cdot (30 + 1).

901, 943, 961, 989

I haven’t thought of a nice story to tell about these—I think of the last three as sort of “sporadic”, but there’s only three of them so it’s not that hard. Someone else could probably come up with a nice mnemonic.

901 in any case is not too hard to remember because it’s a twin with 899, and it’s also the end of the 17-sequence that started with 289.

943 is 23 \cdot 41. It’s 1024 - 81 = 32^2 - 9^2, but unlike some of the other differences of squares I’ve highlighted, I doubt this will actually help me remember it.

961 is 31^2. I think it’s cute that 169, 196, and 961 are all perfect squares.

Last but not least, 989 = 23 \cdot 43. If you happen to know that 33^2 = 1089 (I sure don’t!), then this is easy to remember as 33^2 - 10^2 = (33-10) \cdot (33+10).

Once again

Repetition helps too, so let’s recite: it starts with 289 = 17^2, then continues by 102s: 391, 493. After that the twins 527, 529, followed by 629; then 667 and 697. Then two sets of twins each with its 99: 713, 731, 799; 841, 851, 899; then 901 to come after 899, and then the three sporadic values: 943, 961, 989!

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in arithmetic, computation, primes and tagged , , , , , , , . Bookmark the permalink.