Mental Primality Testing

Question

At a trivia night, the following question was posed: "What is the smallest 5 digit prime?"

Teams (of 4) were given about a minute to write down their answer to the question. Obviously, the answer is googleable, so I'm not asking what the answer to the trivia question is, but rather: how could a team quickly find the answer without previous knowledge of it? If you wanted to try solving the trivia question yourself, don't read any further, as I will start discussing the answer and ruling out other numbers now.

---

My thoughts so far:

1. If you know your slide rules, you expect that prime density is close to $ln(10,000)$ or about 10%. So, a reasonable approach would be to focus on numbers 10,000 through 10,010. Really, what matters is that (I assume) you start at 10,000, factor as many numbers in a row as you can, and then guest the first number you haven't factored.
2. We can rule out a lot with easy divisibility tests, leaving 10001, 10003, 10007, and 10009.
3. Assuming one of your people is fast with division or knows better divisibility rules, 10003 is also eliminated because it has a small divisor (7). This shouldn't require a special technique.
4. We're now left with 3 numbers that reasonable divisibility tests won't handle. It turns out 10,001 is composite, while 10,007 and 10,009 are both prime. But the smaller factor of 10,001 is 73, which is the 21st prime. If the team could do the above steps and then rule out 10,001 by dividing by the first 21 primes (also assuming they know the first 21 primes), they would presumably guess 10,007 thereby being right (though not necessarily confident in their answer).
5. But, let's assume that 21 divisions aren't quite possible. Is there a faster way? Let's say that either a test that quickly determines that 10,001 is likely composite or a test that determines that 10,007 is likely prime is sufficient, since we might be down to some guess work at this point, but bonus points if we can know for sure 10,001 is composite or know for sure 10,007 is prime, and extra bonus points if we do both!
6. There are potentially approaches that don't rely on ruling out 10,001. For example, I had the idea initially that given that 10,001, 10,007, and 10,009 are each hard to divide, maybe it's fairly likely that 10,007 and 10,009 are twin primes, and therefore it is more likely that 10,007 is a prime than 10,001 and so you would guess it anyway. While 10,007 and 10,009 do turn out to be twin primes, I don't actually think that the assertion holds, and this seems more like luck.

Answer 1

For what it is worth, I just timed myself doing trial division:

$10001=100^2+1$, so I only need to check primes that are 1 mod 4

$10001=10010-9$, so not $7$, $11$, $13$

$10001=10030-29$, so not $17$ or $29$

$10001 = 9990+11$ so not $37$

$41*61 = 2501 = 10001-7500$ so not $41$ or $61$

$10600-10001 = 599$ so not $53$

$10001 +219 = 10220 = 20*511 = 20*7*73$

So $73$ is a factor!

Time: 3 minutes 40 seconds. (Doesn't include going back to reformat the equations.) I might have been able to get under 3 minutes back when I was doing math contests twenty years ago. I doubt there are more than ten people in the country who could do the trial division in under a minute, except by luckily guessing which prime to try. Sasha Schwartz was scary fast in my day, perhaps he could have.

As you can see, part of the way that I do trial division is that I have memorized a lot of nonprimes near multiples of 100: $7 \times 11 \times 13 = 1001$, $17 \times 59 = 1003$, $19 \times 53=1007$, $3 \times 23 \times 29 = 2001$, $31 \times 71 = 2201$, $3^3 \times 37=999$, $41 \times 61 = 2501$, $43 \times 7 = 301$. That covers all the primes up to 43, plus a few more. (Hmm, having written this out, I feel like I should memorize a multiple of $47$, since I already have $53$, $59$, $61$, $71$ and $201 = 3 \times 67$. Maybe I'll try to remember $799=47 \times 17$.)

This suggests to me that some people who are more obsessed than me might have memorized nonprimes near multiples of 1000, and thus might know 10001 = 73*137 by heart.

Other than that, though, I think you have to get lucky to answer this one in a minute.

Answer 2

Maybe someone was lucky enough to read List of Primes and remembered (like me) there are only two known "Generalized Fermat primes base 10", so 10001 is not prime. Does that count?

P.S. You could also use this A theorem about prime divisors of generalized Fermat numbers? to find you "only" need to divide 10001 by prime numbers of the form $8k+1$ for $k=1,\ldots,12$, and those are $17,41,73,89,97$

So if the queston is "What is the smallest n digit prime?" for some relatively small n, you could carelessly omitt $10\ldots01$ from factoring, saving some time, since people surely checked for those "Generalized Fermat primes base 10", or you could at least speed up your factoring.

Sorry, I can't comment.

Answer 3

When you are doing something like this, the advantages of a brain over a computer are minimal. It is best to admit that and select the algorithm that you can carry out fastest. Creativity will play a minimal role in intuitively recognizing anything but the smallest primes, and any "tricks" would almost certainly correspond to known primality tests and thus fall under the proposed approach anyway.

So, look at this like a computational problem. There are two basic approaches to finding primes computationally. You can test single numbers, or you can find all primes in an interval using a technique called "sieving".

The fastest way for a computer to test a single small number for primality is to use Miller-Rabin testing with a potential witness set that is known beforehand to be deterministic. Check out the wiki article on Miller-Rabin testing if you are not familiar with it. however, deterministically Miller-Rabin testing a 10000ish number would require a couple dozen modular multiplications with a base of the number being tested. This is not very practical for a person to do in a minute for even one number. Other deterministic single number testing methods are at least comparably complex, so this approach is probably not going to work.

For a small interval, a computer would probably use a combination of sieving and primality testing. There really is not much else available. Since primality testing is out, you only have sieving.

To deterministically sieve an interval, you "sieve" out the composites. There is little incremental cost in increasing the size of the interval, so you probably want to go with something like [10000,10030] to make sure you don't miss your prime.

The most efficient sieve for small intervals is the Sieve of Eratosthenes (the Sieve of Atkin is more efficient for large intervals, but the intervals need to be large). The Sieve of Eratosthenes basically requires you to mark off multiples of primes less than $\sqrt{1030}$, so you are interested in primes less than 100. This is because every composite number in the test interval has a prime factor less than 100.

The trick is to carry this out quickly. To do this, reduce 10000 modulo each prime, and use this reduction to find the next multiple. Subsequent multiples follow easily by adding the number to the its first multiple.

As I explained before, I really don't think anything faster is available. If it were, it would be used in computer algorithms, rather than the methods mentioned. So, doing this in a minute would be hard, but a fast team of several people could probably pull it off if they started on this algorithm right away. Note that the 25 primes less than 100 (23 other than the simple cases of 2 and 5) allow for easy paralelization of this algorithm, and it is reasonable to do this with each person taking only 5-6 primes.

I will give the case of 29 as an example. Note that the modular reductions could be done quickly in each case by reducing 100 and then squaring it. So,

$$100 = 13 \;\text{mod}\; 29; \;\;\; 10000 = 13^2 \;\text{mod}\; 29 = 169 \;\text{mod}\; 29 = 24 \;\text{mod}\; 29$$

That is really pretty fast, and it certainly beats dividing anything that big by 29. 23 of these operations really are pretty reasonable. Simply add -24 mod 29 to 10000 to get the first multiple of 29. That is 10005. The next is out of range. So mark off 10005, or just move on to the next prime recognizing that this number was already marked off when 5 was processed and its multiples were marked off.

After 25 (23 non-trivial) such operations, you'd have all the primes in your interval. Anything significantly faster than this would probably require fundamentally new knowledge in the area of prime computing.

Finally, I suggested a fairly large interval, which in fact contains no primes beyond an interval of 10 or so. That is because I am assuming no special knowledge of prime distribution in the interval in question, and a larger interval is in general better for this sort of thing, since it has very little extra cost and it sometimes would be necessary to prevent failure.

EDIT: As far as my comment on brains having little advantages over computers on this sort of thing, let me explain. Brains can blow computers out of the water in many circumstances. For example, a computer takes so long to find a proof that it will never happen without guidance in all but the simplest cases, while a brain can find amazing and complex proofs. However, this problem is inherently computational. There have been many man-years of research put into what can be done to identify primes. The brain work for this sort of thing has really been hammered out. You may be the next brilliant person that makes a breakthrough, but you won't do it in a minute. So, rely on the brainwork that has already been done, and select the best algorithm that has been found.

With regard to the difference of cost in operations between a brain and computer, that was considered. I presented the algorithm that is simplest based on the relative computation time of operations for a brain. What I meant was not to do what a computer program would do (that would possibly be to just do Miller-Rabin testing on everything in the range to avoid memory allocations and/or instruction cache misses). I meant to treat your brain as a computer, selecting the fastest algorithm that could be carried out given the relative costs of operations for the brain. So, for example, the process I gave may be improved for the case of 3 by recognizing that any power of 10 is 1 mod 3, and so 1002 is the first multiple thereof. You could also recognize that 97*103 is under range while 97*105 is over range and not bother with 97. But the algorithm as I gave it cannot be made drastically faster, considering what brains do best, without new knowledge on prime computations.