In my previous post I wrote about a procedure for testing the primality of any number less than :
Test for divisibility by all primes up to , and also . (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.)
Check if the number is one of a memorized list of 18 composites less than which are not divisible by either or any prime . (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:
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 . Each of these numbers is a product of with some other prime, and the second prime increases by every time. That is, , then , and . 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 , and if we continue it further we see that it contains several more numbers from our exceptional set as well:
What about if we start with and keep adding ?
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 (, , , ).
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 . On the other hand 529 is .
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 , which is the closest integer to two-thirds of 1000. If you know that , 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 .
The last exceptional composite in the 600’s is 697, which is from the sequence of multiples of 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 . 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 , and 851 is . Finally we have 899 which is .
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 . It’s , but unlike some of the other differences of squares I’ve highlighted, I doubt this will actually help me remember it.
961 is . I think it’s cute that , , and are all perfect squares.
Last but not least, . If you happen to know that (I sure don’t!), then this is easy to remember as .
Repetition helps too, so let’s recite: it starts with , 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!