14
$\begingroup$

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.
$\endgroup$
  • 4
    $\begingroup$ $10001 + 32^2 = 105^2$ $\endgroup$ – Will Jagy Mar 18 '15 at 0:39
  • 2
    $\begingroup$ Will beat me to it. This requires $5$ iterations of Fermat's factorization method (consider $101^2-10001$, $102^2-10001$, ... until we get a square). This is probably somewhat faster than $21$ trial divisions. But there is not really any way of knowing in advance that it would work. $\endgroup$ – Dan Brumleve Mar 18 '15 at 0:41
  • $\begingroup$ This is definitely cool, and highlights the value of combining trial division with Fermat's factorization method. But agreed that there's no good way to know it would work. I was curious about the likelyhood of this working. On average odd composites between 9981 and 10019 require 443 iterations. Although 7/18 require 11 or fewer, so it's worth a shot. $\endgroup$ – William Macrae Mar 18 '15 at 1:29
  • 2
    $\begingroup$ Have three people try to factor factor your three numbers $10001, 10007, 10009$ while a fourth person watches the time. At the end of the time, pick $10007$ because obviously $10001$ is probably a trick. $\endgroup$ – Qiaochu Yuan Mar 18 '15 at 6:32
  • 1
    $\begingroup$ @DanBrumleve $102^2-10001$, $103^2-10001$ and $104^2-100001$ have final digits $3$, $8$ and $15$, so they can't be squares. Still, I'd be impressed by anyone who actually did the computation (including choosing this approach) in one minute. $\endgroup$ – David E Speyer Mar 31 '15 at 12:55
10
+50
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Ha. I also use the trick in lines 3 and 5 to eliminate two prime factors at once (although with smaller multiples of smaller primes), but I've never used the trick in line 1; very nice! $\endgroup$ – Qiaochu Yuan Apr 1 '15 at 7:10
  • 1
    $\begingroup$ And of course lots of people who did Olympiads around the year $2000$ (e.g. me) memorized the prime factorizations of all of the relevant years, but memorizing the prime factorization of $2501$ is really looking ahead to the future... $\endgroup$ – Qiaochu Yuan Apr 1 '15 at 7:13
  • $\begingroup$ I remember 2501 because it is useful to know a lot of things that end in 01, and because $41 \times 61 = (51)^2 - 100$ is easy. But I feel a little guilty recording this sort of thing; it isn't really what I "should" be taking up memory slots with. $\endgroup$ – David E Speyer Apr 1 '15 at 14:04
  • 2
    $\begingroup$ I don't know if it offers any kind of a real speed-up, but as $200=2\cdot10^2$ is manifestly a quadratic residue modulo $10001$, so is $2$. Thus, by the extension to the law of quadratic reciprocity, we know that the prime factors are $\equiv \pm1\pmod8$. Combining this with your starting point that $-1$ is also a QR, we see that we only need to check primes $\equiv1\pmod8$. $\endgroup$ – Jyrki Lahtonen Apr 1 '15 at 16:03
  • $\begingroup$ Thanks for the explanation! I don't think there's anyway I or anyone on the team could have done this fast enough in the time allotted, but it's neat to see how someone who could factor in time would do so :) I think in the end the comment about Fermat's factorization method was a little more satisfying for the case of 10,001, since it feels more doable, but your approach likely generalizes much better to other factoring situations. $\endgroup$ – William Macrae Apr 2 '15 at 18:26
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Cool! This is fairly lucky, but definitely solves it if you have that knowledge, and it's neat to know how you got it. And I appreciate the point about the residue modulo 8 - interesting that this came up in two different answers; it's probably a solid starting point for ruling out factors without trial divisions. $\endgroup$ – William Macrae Apr 2 '15 at 18:22
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is a well thought-out explanation of how to look for the next prime, but it doesn't actually rule out 10,001. Also, I disagree with some assertions, such as the fact that the advantages of a brain over a computer are minimal, so we're stuck only with computational methods. Certain operations, such as modular multiplication are really efficient when done by computers, but trickier for humans, while others, such as adding digits to check for divisibility by 3 work really well for humans. I'd appreciate more thought about methods that work very well for humans, and solve the question. $\endgroup$ – William Macrae Apr 2 '15 at 18:17
  • $\begingroup$ This does actually rule out 10001 and any other composite. The process will mark off any multiple of primes less than 100, and even two prime factors over 100 puts a number out of range, the smallest example being $101^2=10201$. For example, when 73 is processed, you will find that 10000=72 mod 73, add the negative of that mod 73, which is 1, and mark off 10001. If you have further doubts that this absolutely rules out all composites in the interval, I suggest you check out the wiki article on Sieve of Eratosthenes. $\endgroup$ – jack Apr 2 '15 at 18:41
  • $\begingroup$ I'll explain the brain/computer thing in more detail in an edit giving a final paragraph to the answer. $\endgroup$ – jack Apr 2 '15 at 18:44
  • $\begingroup$ Hmm, I don't think we need the philosophical debate on computers/humans to agree that some of the other answers provide really strong human approaches to this problem. What I meant about 10,001 is that other than recognizing that we don't need pure division, just divisibility, and trial division can be done through a sieve (neither of which is surprising), this doesn't really do anything better than the naive approach I said I wanted to do better than in my question. But, I'm not sure it's productive to debate this, I just wanted to explain why despite the detail I prefer the other answers. $\endgroup$ – William Macrae Apr 2 '15 at 22:56
  • $\begingroup$ This is much faster than trial division. You could do this whole process faster than just 4 or 5 trial divisions. $\endgroup$ – jack Apr 2 '15 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.