Recently, Mark Dominus wrote about trying to memorize all the prime numbers under . This is a cool idea, but it made me start thinking about alternative: instead of memorizing primes, could we memorize a procedure for determining whether a number under is prime or composite? And can we make it clever enough to be done relatively quickly? This does tie into my other recent posts about primality testing, but to be clear, it’s also quite different: I am not talking about a general method for determining primality, but the fastest method we can devise for mentally determining, by hook or by crook, whether a given number under is prime. Hopefully there are rules we can come up with which are valid for numbers less than —and thus make them easier to test—even though they aren’t valid for bigger numbers in general.
As a warmup, today I’ll write about how I determine whether a number less than 100 is prime: I don’t have them memorized, but can very quickly decide whether such a number is prime or not—and you can, too! This is a situation where doing a little mathematical analysis beforehand goes a long way.
Since , every composite number less than has at least one factor which is less than . This means that every composite less than is divisible by , , , or . Multiples of 2, 3, and 5 are relatively easy to recognize, and as we’ll see, is not hard to deal with either.
Any even number or multiple of 5 (i.e. numbers ending with an even number or with a 5) is clearly composite. (Other than 2 and 5 themselves, of course.)
Multiples of are composite. There are many numbers which I think of as “obvious” multiples of three: 9, 21, 27, and 33 because I have had their factorizations memorized since third grade; 81 because it’s a power of three so I have it memorized too; and 39, 63, 69, 93, and 99 because they consist of two digits each of which is a multiple of three. As you probably know, there is also a simple test for determining divisibility by three: just add the digits and see whether the result is divisible by three. This test identifies a few more “nonobvious” multiples of three which you might otherwise think are prime: , , and .
What’s left? There are only three numbers less than 100 which are composite and not divisible by 2, 3, or 5:
- and are easy to spot.
- is the one I always used to forget about—I call it a “fool’s prime” because it “looks” prime but isn’t. It’s worth just memorizing the fact that it is composite (and its factorization).
So, to sum up, faced with a number less than 100 that I want to test for primality, I can quickly rule it out if it is divisible by 2, 3, or 5, or if it is a multiple of 7 I recognize (49, 77, or 91). And that’s it! Anything else has to be prime.
In a future post I plan to write about how feasible it is to come up with a similar procedure to identify all primes under 1000.
Yes, that’s how I’ve always thought about the primes under 100. There’s a divisibility test for 7, but I don’t use it often since the time I had to prove it about 10 years ago. The one for 11 is easy. I remember when looking into the one for 7 that there’s some principle that can lead from that to tests for 13, 17, etc., but I don’t think I understood it at the time and definitely don’t remember it. 😦
Indeed, which divisibility test for 7 are you thinking of? There are a few I know of. I do also know about divisibility tests for bigger primes, which will come up when I write about testing numbers under 1000 for primality — stay tuned!
I did recently post [an article about testing for divisibility by 7](https://blog.plover.com//math/divisibility-by-7.html). I have a followup in the works with additional tricks, but testing for divisibility by 7 is pretty easy and is not the issue with mental identification of primes under 1000. The problem is with numbers like 851.
851 = 900 – 49 = (30+7)(30-7)
91 is also of the form a^2 – b^2, for small b.
Oh, nice observation!
I would be interested to see an machine learning approach designed to overfit. Pick a small set of features (the digits of the number) and a decent set of human-computable transformations (“add”, “multiply”, “is divisible by k”, “equals k”), and then find small decision trees that get 95+% classification rate, memorizing the remaining <= 50 composites.
Is this similar to what you had in mind?
er– for decision trees you’d have to compute all the features in advance. Could also try small branching programs, or a really small neural network…
Yes, this is exactly the sort of thing I had in mind, though at this point I hadn’t got much farther than thinking there should be a way to pick some features and run an algorithm to build small decision trees. A straightforward approach is to run through divisibility tests up to 13 and then memorize the ~25 remaining composites which are products of primes >= 17; I’m curious to see whether we can come up with something better using an approach like what you outline. Would you be interested in collaborating on this? I’m not very familiar with machine learning techniques beyond the basics.
Surely! Shoot me an email at firstname.lastname@example.org
A composite approach may work best. Check for factors up to, say, 13, and also check a^2 – b^2 for small b, say up to 13. This would give you every number up to 799 (47×17), with no memorization needed, other than squares.
If you make that b <= 18, then all numbers up to 1000 are checked by applying those two procedures. There are some short cuts in checking whether it’s of the form a^2 – b^2, so it can be done quite quickly (and memorizing squares is easier and a lot more useful than memorizing the factors of numbers like 851).
Interesting! Can you explain the short cuts you refer to (or give a link to some explanation)?
Take 851 as an example. You don’t need to successively add 1, 4, 9, 16, … and see whether you have a square each time. Rather you can subtract it from 900, 961, 1024, … and see whether that is a square. (The first one you try is.) Further, this sequence terminates quickly as you have tried direct division up to 13, so if it is composite a-b must be at least 17. This no longer happens after a is 34, so you settle primality with at most five subtractions.
The two methods complement each other because direct division works quickly if there is a small factor, and difference of two squares works well when the two factors are close together. There are very few composite numbers under 1000, which aren’t one or the other, and none at all if you divide up to 13, and then check a^2 – b^2 for b up to 18.
Another short cut is to use the fact that the difference of successive squares increases by 2 each time. So in the previous example, if 900 – 851 isn’t a square, you add 61, then 63, then 65, etc until you get a square or get over 324. That way you only have to memorize the first 18 squares, which you probably already know.
One final comment: if you first verify there is no factor of 13 or less, then capping b at 15 is sufficient to establish primality for every number up to 1000 with the sole exception of 901.
Pingback: Quickly recognizing primes less than 1000: divisibility tests | The Math Less Traveled
Thank you! My Dyslexic child is learning to divide by factoring rather than by the traditional algorithm, and this will be a huge help.