IBM Research | Ponder This | November 2009 solutions
Skip to main content

November 2009

<<October November December>>

The smallest divisor of a number between 2 and 166 has 38 different possibilities. Therefore, for the first case (worst case) one needs at least ceil(log2(38)) = 6 questions.

On the other hand, since the probabilities are biased, we can use Huffman coding to find it in less than three questions on average (494/165 = 2.9939...).

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: