Ponder This Challenge - November 2009 - Fastest way to find the smallest divisor

Ponder This Challenge:

What is the minimal number, X, of yes/no questions needed to find the smallest (but more than 1*) divisor of a number between 2 and 166 (inclusive)?

We are asking for the exact answer in two cases:

In the worst case, i.e., what is the smallest number X for which we can guarantee finding it in no more than X questions?

On average, i.e., assuming that the number was chosen in uniform distribution from 2 to 166 and we want to minimize the expected number of questions.

* For example, the smallest divisor of 105 is 3, and of 103 is 103.

Update (11/05): You should find the exact divisor without knowing the number and answering "prime" is not a valid.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

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

Solution

• Click here to view the solution

  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...).

Solvers

• Christian Kissig (11/02/2009 07:57 PM EDT)
• Lukasz Bolikowski (11/02/2009 08:45 PM EDT)
• Ante Kovacic (11/02/2009 11:05 PM EDT)
• John T. Robinson (11/03/2009 02:47 AM EDT)
• Corey Cerovsek (11/03/2009 04:06 AM EDT)
• Andreas Eisele (11/03/2009 04:37 AM EDT)
• P. Subrahmanya (11/03/2009 04:50 AM EDT)
• Michael Brand (11/03/2009 05:01 AM EDT)
• Pratik Poddar (11/03/2009 05:11 AM EDT)
• Christian Blatter (11/03/2009 12:14 PM EDT)
• Luke Pebody (11/03/2009 12:18 PM EDT)
• Phil Muhm (11/03/2009 12:28 PM EDT)
• Arthur Breitman (11/03/2009 01:24 PM EDT)
• Martin Thiim (11/03/2009 03:56 PM EDT)
• Klaus Hoffmann (11/03/2009 05:12 PM EDT)
• Joe Fendel (11/03/2009 05:37 PM EDT)
• Austin Shapiro (11/03/2009 06:27 PM EDT)
• Donald T. Dodson (11/03/2009 06:46 PM EDT)
• Pataki Gergely (11/03/2009 08:34 PM EDT)
• Ante Turudic (11/04/2009 07:47 AM EDT)
• Are Hjørungnes (11/04/2009 08:07 AM EDT)
• William Heller (11/04/2009 08:45 AM EDT)
• Mark Mixer (11/04/2009 03:23 PM EDT)
• Irem Koprulu Eryilmaz (11/04/2009 04:23 PM EDT)
• Benedikt Engels (11/04/2009 05:25 PM EDT)
• Krunoslav Kovac (11/04/2009 05:41 PM EDT)
• Harald Bögeholz (11/04/2009 06:11 PM EDT)
• Daniel Bitin (11/04/2009 07:22 PM EDT)
• Chuck Carroll (11/04/2009 08:40 PM EDT)
• Gale Greenlee (11/04/2009 08:57 PM EDT)
• Kai Guttmann (11/04/2009 09:55 PM EDT)
• Harold Gutch (11/04/2009 11:22 PM EDT)
• Daniel Hsu (11/05/2009 01:36 AM EDT)
• Yuval Filmus (11/05/2009 02:31 AM EDT)
• Kin Keung Ma (11/05/2009 03:49 AM EDT)
• Dmitry Litvinenko (11/05/2009 08:59 AM EDT)
• Will Hasenplaugh (11/05/2009 01:28 PM EDT)
• Sevag Papazian (11/05/2009 02:19 PM EDT)
• David Friedman (11/05/2009 03:04 PM EDT)
• Gueorgui Nedev (11/05/2009 03:12 PM EDT)
• A (11/05/2009 04:54 PM EDT)
• lan Murray (11/05/2009 04:54 PM EDT)
• Greg Janée (11/05/2009 10:36 PM EDT)
• Andreas Stiller (11/05/2009 10:49 PM EDT)
• Yuanmi Chen (11/06/2009 11:04 AM EDT)
• Lei Zhao (11/06/2009 02:20 PM EDT)
• Radu Borza (11/06/2009 02:25 PM EDT)
• Hamidreza Bidar (11/07/2009 06:18 AM EDT)
• Bernardino Romera Paredes (11/07/2009 10:05 AM EDT)
• Dan Dima (11/07/2009 02:53 PM EDT)
• Stefan Sec Zehl (11/08/2009 12:57 AM EDT)
• Yuvraj Dhillon (11/08/2009 05:56 AM EDT)
• Subramanian CA (11/08/2009 06:12 AM EDT)
• Rustam Miftakhutdinov (11/08/2009 09:06 AM EDT)
• Joseph DeVincentis (11/09/2009 02:32 PM EDT)
• Sylvain Becker (11/09/2009 07:33 PM EDT)
• John G Fletcher (11/10/2009 01:59 AM EDT)
• Troels Nørgaard (11/10/2009 02:02 PM EDT)
• Wolfgang Kais (11/10/2009 02:48 PM EDT)
• Thomas Rohr (11/10/2009 02:48 PM EDT)
• Liran Katzir (11/10/2009 04:11 PM EDT)
• Guy Tannenbaum (11/10/2009 10:40 PM EDT)
• Lachezar Hristov (11/11/2009 09:29 AM EDT)
• Parashar Dave (11/11/2009 01:29 PM EDT)
• Stephen Herbert (11/11/2009 01:36 PM EDT)
• Rickard Björklund (11/11/2009 07:38 PM EDT)
• Jörg Binder (11/12/2009 07:31 PM EDT)
• Karl D’Souza (11/12/2009 11:45 PM EDT)
• Harinarayanan E V (11/13/2009 02:07 AM EDT)
• Alan Curry (11/13/2009 04:18 AM EDT)
• Albert Stadler (11/13/2009 04:04 PM EDT)
• Stephan Keil (11/13/2009 08:23 PM EDT)
• Michael Schaaf (11/15/2009 04:46 PM EDT)
• Nagy Zoltan (11/16/2009 12:26 PM EDT)
• Jeremy Cahill (11/17/2009 09:32 PM EDT)
• Susan Mielke (11/17/2009 10:59 PM EDT)
• Chris Chen Xu (11/18/2009 03:59 PM EDT)
• Ramkumar Balaraman (11/19/2009 09:09 AM EDT)
• Wang Weiyan (11/20/2009 04:53 AM EDT)
• Andy Kidd (11/20/2009 05:45 PM EDT)
• Jimmy He (11/22/2009 09:06 PM EDT)
• Se Kwon Kim (11/23/2009 03:39 AM EDT)
• Adam Daire (11/23/2009 03:35 PM EDT)
• Amos Guler (11/24/2009 12:07 PM EDT)
• Aviv Nisgav (11/24/2009 06:32 PM EDT)
• Fabio Filatrella (11/25/2009 10:14 AM EDT)
• Jason W Christopher (11/26/2009 06:52 AM EDT)
• Clive Tong (11/26/2009 08:01 AM EDT)
• James Carter (11/27/2009 06:34 AM EDT)
• Rani Hod (11/28/2009 09:04 PM EDT)
• Hengfeng Tian (11/30/2009 02:31 AM EDT)
• Shmuel Menachem Spiegel (11/30/2009 04:01 AM EDT)
• Andrew Marut (11/30/2009 07:05 AM EDT)
• Mutaamba Maasha (11/30/2009 06:08 PM EDT)
• Nyles Heise (12/01/2009 12:47 AM EDT)