## Quickly recognizing primes less than 1000: memorizing exceptional composites

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!