My daughter was learning about prime numbers and she had an exercise to identify all the prime numbers less than 100. I made a little game out of it with her by offering her 10 cents for each number correctly categorized as prime or composite within a fixed total time.
As she progressed through the numbers I noticed a pattern. It took her less time to guess that a number was composite than it took her to guess that it was prime. And of course there is a simple reason: you know that a number is composite once you find a proper factor, you know that a number is prime only when you are convinced that a proper factor does not exist.
But this was a timed-constrained task and waiting until she knows for sure that the number is prime is not an optimal strategy. She should guess that the number is prime once she thinks it is sufficiently likely that she won’t find any proper factor. And how long that will take depends on the average time it takes to find a proper factor.
In particular, if the average time before she guesses prime is larger than the average time before she guesses composite then she is not optimizing. Because if that were the case she should infer that the number is likely to be prime simply from the fact that she has spent more than the average time looking for a proper factor. At an optimum, any such introspective inference should be arbitraged away.
Cheap Talk 
11 comments
Comments feed for this article
November 7, 2012 at 10:50 pm
Alex F
“if the average time before she guesses prime is larger than the average time before she guesses composite then she is not optimizing”
I don’t follow. The optimal strategy seems like it should be to use a stopping rule: check factors for some amount of time, then guess prime if none of the factors work. This means that primes will take longer than composites. Say you’re checking 10 factors, and it takes one second each — composites take between one and ten seconds, and primes always take ten seconds. What am I misunderstanding?
November 7, 2012 at 11:29 pm
jeff
I don’t think that’s how we look for factors. At least it’s not how I do. It’s more of a passive thing where factors suggest themselves. When I say 49 you don’t check 2 then 3 then 4… Instead the number 7 just jumps into your head. If you wait long enough and no factor has jumped into your head then you guess prime.
November 8, 2012 at 11:17 pm
Alex F
Sure, but this process still leads to composite guesses taking a shorter amount of time than prime guesses?
November 9, 2012 at 8:24 am
jeff
yes you are right. if i use a stopping rule then i either find a factor before the stopping time or i don’t and then i guess prime at the stopping time. i don’t know what i was thinking.
November 7, 2012 at 11:27 pm
somemusings
Unless there’s an error term in how long it takes to recognize a number is composite. In a world of fuzzy time-until-identification, increasing the wait before declaring prime is a trade-off between alpha and beta errors. Arbitration is only possible if your daughter is overly risk averse.
November 8, 2012 at 8:24 am
Lones Smith
The problem lies in your incentives. Asymptotically, almost no numbers are prime. To offer her symmetric payoffs for guessing prime or composite is to offer her a poor incentive scheme. Gosh you can do better. The payoff for guessing prime should be rising, roughly inversely to their proportion, say as n/log n.
November 8, 2012 at 11:28 am
PLW
Why not use a sieve? No guessing and nearly instant identification. Or are you requiring her to do them in order?
November 8, 2012 at 12:53 pm
Anonymous
I was wondering the same.
-Conclude 2 is prime, quickly make ++$5.00
-Conclude 3 is prime, quickly make ++$3.20
-Conclude 5 is prime, quickly make ++$0.70
…
[She doesn’t have to do these calculations of how much money each sieve operation makes.]
I guess the main downside is that she has to either (i) redundantly say numbers more than once, or (ii) remember which numbers she’s said.
November 8, 2012 at 11:53 am
Anonymous
One flaw in your reasoning is that the time spend looking for prime and composite numbers is fixed. But it changes over time. You can pretty easily whether single-digit numbers are prime or not. Also you now that all even numbers and all numbers ending in 5 are composite. But once you have tell all those, the remaining numbers (both prime and composite will take more time).
You then may want to exhaust “squares” (49, 81) and any other rule you know, like how to rule out composites of 3.
At the end, if you still have time, you will have to check odd numbers, not ending on 5, not multiples of 3, in the interval 60-100… and that will take a lot of time, for each number…
November 8, 2012 at 8:19 pm
Zachary M. Jones
You should show her the Sieve of Eratosthenes
March 17, 2013 at 10:51 pm
Anonymous
Late to the party, but this should be pointed out:
“Introspective arbitrage” is counting evidence twice.
Yes, as time goes by without an answer, the number is (more or less monotonically) increasingly more likely to be prime. But that’s because stopping time *depends* on your subjective likelihood of possible answers. If you then change your likelihood based on stopping time, you’re lending your self-generated “rumor” more credence than actual evidence warrants.