Imagine that you have a collection of very weird dice. For every prime between 1 and 1000, you have a fair die with that many sides. Your goal is to generate a uniform random integer from 1 to 1001 inclusive.
For example, using only the 2 sided die, you can roll it 10 times to get a number from 1 to 1024. If this result is less than or equal to 1001, take that as your result. Otherwise, start over.
This algorithm uses on average 10240/1001=10.228770… rolls. What is the fewest expected number of die rolls needed to complete this task?
When you know the right answer, you will probably be able to prove it. This puzzle is my own design. Solution in the comments.
You can complete the task in two rolls. You cannot do better, because then it would have to be possible to finish after 1 roll, and every event you can get with 1 roll has a greater than 1/1001 chance of occurring.
This may be counter intuitive because it is possible to prove that because 1001=7*11*13, it is impossible to be guaranteed to finish in a fixed time unless you use the 7, 11, and 13 sided dice. The trick is to use all three in the second roll by having the die you roll the second time be a function of the first roll.
First, you roll the die with 311=7*11+7*13+11*13 sides. 311 just happens to be a prime number. If you get one of the first 77 numbers, you then roll the 13 sided die. If you get one of the next 91 numbers, you then roll the 11 sided die. If you get one of the last 143 numbers you then roll the 7 sided die. There are 3003 possible ways the two rolls can be completed, and these 3003 outcomes can be partitioned into 3 sets of 1001 outcomes, with all the outcomes in a set having the same probability. Therefore, we can combining these outcomes into 1001 sets of equal probability, by taking one outcome from each set.