Ponder This Challenge - June 2012 - Dividing 1,506,009,006,001,500,000,000

Ponder This Challenge:

Two players starts with the number N and play in turns.
In each turn the player chooses a prime power p^m>1, which divides N and updates N to be N/(p^m).
The player who sets N to be 1 - wins.
What are all the winning moves from the initial state of N=1,506,009,006,001,500,000,000 ?

Update 6/8: We are looking for all the moves the first player can make which, assuming he plays correctly, can guarantee him winning the game.

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

  First we factor 1,506,009,006,001,500,000,000.

  It is easy to factor out 10^8=2^8 * 5^8 and then 15=3*5.

  Noticing the binomial coefficients in the result (1,004,006,004,001) we get 1001^4=7^4 * 11^4 * 13^4.

  So the factorization of N is 2^8 * 3^1 * 5^9 * 7^4 * 11^4 * 13^4.

  Then we note that the game is a actually the classic game of Nim in disguise.

  The winning moves from the initial state of (8,1,9,4,4,4) are to remove one of the piles of 4.

  Translating it back to our game - the winning moves are 7^4, 11^4 and 13^4.

Solvers

• Zhendong Wan (05/31/2012 02:38 PM EDT)
• Yossi Fendel (05/31/2012 02:47 PM EDT)
• Peter de Rivaz (05/31/2012 03:17 PM EDT)
• Denys Kopiychenko (05/31/2012 03:25 PM EDT)
• Jochen Voss (05/31/2012 03:28 PM EDT)
• Sergey Grishaev (05/31/2012 03:31 PM EDT)
• William Heller (05/31/2012 03:37 PM EDT)
• Hrushikesh Tilak (05/31/2012 03:43 PM EDT)
• Tim Nordenfur (05/31/2012 03:48 PM EDT)
• Mark Pervovskiy (05/31/2012 04:16 PM EDT)
• Florian Fischer (05/31/2012 04:20 PM EDT)
• Donald Dodson (05/31/2012 05:19 PM EDT)
• Thomas Mack (05/31/2012 05:42 PM EDT)
• Dario Serino (05/31/2012 05:51 PM EDT)
• Harold Gutch (05/31/2012 06:01 PM EDT)
• Deron Stewart (05/31/2012 06:12 PM EDT)
• Alex Stangl (05/31/2012 06:23 PM EDT)
• Janos Csorba (05/31/2012 06:41 PM EDT)
• Deane Stewart (05/31/2012 07:42 PM EDT)
• Radu Borza (05/31/2012 08:23 PM EDT)
• Jason Lee (05/31/2012 10:01 PM EDT)
• Michael Brand (05/31/2012 11:40 PM EDT)
• David Dodson (06/01/2012 12:26 AM EDT)
• Arthur Vause (06/01/2012 02:47 AM EDT)
• Øyvind Grotmol (06/01/2012 03:22 AM EDT)
• Robin Ryder (06/01/2012 04:10 AM EDT)
• Anlu Wang (06/01/2012 04:14 AM EDT)
• Hari MP (06/01/2012 06:50 AM EDT)
• Radu-Alexandru Todor (06/01/2012 07:13 AM EDT)
• Stéphane Higueret (06/01/2012 08:09 AM EDT)
• Armin Krauss (06/01/2012 08:21 AM EDT)
• Joseph DeVincentis (06/01/2012 09:27 AM EDT)
• Kevin Sham (06/01/2012 09:36 AM EDT)
• Avishalom Shalit (06/01/2012 10:12 AM EDT)
• Joachim Dörfer (06/01/2012 10:16 AM EDT)
• Luke Pebody (06/01/2012 10:40 AM EDT)
• Joshua Small (06/01/2012 12:29 PM EDT)
• Stefan Sec Zehl (06/01/2012 01:59 PM EDT)
• Christian Pape (06/01/2012 03:08 PM EDT)
• Matej Kollár (06/01/2012 02:07 PM EDT)
• Lu Wang (06/01/2012 04:33 PM EDT)
• Adrian Orzepowski (06/01/2012 04:53 PM EDT)
• Daniel Kneezel (06/01/2012 05:19 PM EDT)
• Anders Kaseorg (06/01/2012 06:03 PM EDT)
• Ignat Soroko (06/01/2012 06:23 PM EDT)
• Yasodhar Patnaik (06/02/2012 12:06 AM EDT)
• Leo Broukhis (06/02/2012 04:59 AM EDT)
• Clive Tong (06/02/2012 05:09 AM EDT)
• Hakan Summakoglu (06/02/2012 05:36 AM EDT)
• Karanveer Mohan (06/02/2012 07:39 AM EDT)
• Martin Thiim (06/02/2012 08:45 AM EDT)
• Serge Gautier (06/02/2012 09:26 AM EDT)
• Jonathan Namnath (06/02/2012 10:23 AM EDT)
• Peter Gerritson (06/02/2012 05:42 PM EDT)
• Siddhartha Kanungo (06/02/2012 07:22 PM EDT)
• Naftali Peles (06/02/2012 09:05 PM EDT)
• Rogerio Ponce da Silva (06/02/2012 09:44 PM EDT)
• Nyles Heise (06/03/2012 12:45 AM EDT)
• David Fergemann (06/03/2012 12:00 PM EDT)
• Anunay Kulshrestha (06/03/2012 02:40 PM EDT)
• David Meiri (06/04/2012 12:21 PM EDT)
• Harald Bögeholz (06/04/2012 02:33 PM EDT)
• Levon Haykazyan (06/04/2012 03:07 PM EDT)
• Walter Schmidt (06/04/2012 05:04 PM EDT)
• Chuck Carroll (06/04/2012 06:04 PM EDT)
• Eden Hochbaum (06/04/2012 06:46 PM EDT)
• Andrew Baine (06/04/2012 07:03 PM EDT)
• Erik Bernhardsson (06/04/2012 10:53 PM EDT)
• Thomas Fleming (06/04/2012 11:25 PM EDT)
• Balakrishnan Varadarajan (06/04/2012 11:41 PM EDT)
• Shilei Zang (06/04/2012 11:55 PM EDT)
• Simon Xu (06/05/2012 12:49 AM EDT)
• Tamir Ganor (06/05/2012 09:09 AM EDT)
• John Tromp (06/05/2012 10:37 AM EDT)
• Michael Malak (06/05/2012 11:58 AM EDT)
• Yue Ru Sun (06/05/2012 12:16 PM EDT)
• Liubing Yu (06/05/2012 04:29 PM EDT)
• Bryan Wolf (06/05/2012 05:18 PM EDT)
• David Friedman (06/05/2012 10:04 PM EDT)
• Kenneth Meehan (06/05/2012 11:39 PM EDT)
• Frederik Kaster (06/06/2012 05:36 AM EDT)
• Markus Boettle (06/06/2012 10:04 AM EDT)
• Septimus G. Stevens VII (06/06/2012 10:21 AM EDT)
• Danny Scheinerman (06/06/2012 02:46 PM EDT)
• Chris St. John (06/06/2012 02:49 PM EDT)
• Motty Porat (06/06/2012 05:54 PM EDT)
• Krunoslav Kovac (06/06/2012 07:52 PM EDT)
• Lewei Weng (06/07/2012 03:37 AM EDT)
• Sondre Glimsdal (06/07/2012 08:54 AM EDT)
• Lorenzo Gianferrari (06/07/2012 11:09 AM EDT)
• Gale Greenlee (06/07/2012 01:27 PM EDT)
• Thomas Pensyl (06/07/2012 05:58 PM EDT)
• Shmuel Menachem (06/07/2012 07:58 PM EDT)
• Chris Kittlitz (06/07/2012 09:38 PM EDT)
• Ryan Milligan (06/07/2012 10:41 PM EDT)
• Xiong Zhang (06/07/2012 11:41 PM EDT)
• Amit Bhatia (06/08/2012 06:39 AM EDT)
• Hamidreza Bidar (06/08/2012 06:57 AM EDT)
• Mihai Stancu (06/08/2012 07:54 AM EDT)
• James Aaronson (06/08/2012 11:58 AM EDT)
• Colm Bhandal (06/08/2012 12:50 PM EDT)
• Rodrigo Coelho (06/08/2012 10:20 PM EDT)
• Bernard F. Richardson (06/09/2012 01:52 AM EDT)
• Wu Chengyuan (06/09/2012 09:45 AM EDT)
• Jonathon Pendergrass (06/09/2012 11:54 AM EDT)
• Eric Ivancich (06/09/2012 04:21 PM EDT)
• Don Gosiewski (06/09/2012 08:30 PM EDT)
• Akshay Nanavati (06/10/2012 02:58 PM EDT)
• M. Zecevic (06/11/2012 05:06 AM EDT)
• Gil Citro (06/11/2012 10:12 AM EDT)
• Djinn Lu (06/11/2012 12:05 PM EDT)
• Phil Benamy (06/11/2012 12:39 PM EDT)
• Hayk Aleksanyan (06/12/2012 01:38 AM EDT)
• Vishaal Kapoor (06/12/2012 03:24 AM EDT)
• Tejas Ajit Deshpande (06/12/2012 05:46 AM EDT)
• Erik Hostens (06/12/2012 07:14 AM EDT)
• Fred Schalekamp (06/12/2012 12:05 PM EDT)
• Stephen Morris (06/12/2012 04:37 PM EDT)
• Ayaskant Pani (06/13/2012 02:36 AM EDT)
• Henri Gonin (06/13/2012 12:44 PM EDT)
• Shouky Dan (06/14/2012 05:52 AM EDT)
• Duane A. Bailey (06/14/2012 02:34 PM EDT)
• Jens Voss (06/15/2012 10:34 AM EDT)
• Wolfgang Kais (06/15/2012 11:31 AM EDT)
• Arun Ramachandran (06/16/2012 12:23 AM EDT)
• Jim Clare (06/16/2012 12:45 PM EDT)
• Kun Huang (06/17/2012 03:16 AM EDT)
• Guler Amos (06/18/2012 09:45 AM EDT)
• Ritobroto Maitra (06/18/2012 03:21 PM EDT)
• Daniel Bitin (06/19/2012 09:44 AM EDT)
• Dan Arnon (06/19/2012 03:54 PM EDT)
• Lawrence Hon (06/20/2012 03:15 PM EDT)
• Puvichakravarthy Ramachandran (06/21/2012 03:32 AM EDT)
• Ken Crounse (06/21/2012 11:40 AM EDT)
• Albert Stadler (06/21/2012 12:47 PM EDT)
• Sushanth Kodali (06/21/2012 04:07 PM EDT)
• Adrian Kummer (06/21/2012 04:23 PM EDT)
• Jake Berkowsky (06/22/2012 01:56 AM EDT)
• Franza Cavalcante Jr (06/22/2012 03:31 PM EDT)
• Michael D. Moffitt (06/22/2012 03:49 PM EDT)
• Tony Harrison (06/24/2012 08:28 AM EDT)
• Amit Sinha (06/24/2012 02:28 PM EDT)
• Vibhakar Shukla (06/26/2012 01:11 AM EDT)
• Dan Dima (06/27/2012 08:52 AM EDT)
• Hannes Schenck (06/26/2012 02:57 PM EDT)
• Lutz Schaarschmidt (06/26/2012 07:33 PM EDT)
• Bradley Sherman (06/27/2012 04:02 AM EDT)
• Heiko Selber (06/27/2012 02:30 PM EDT)
• Joel Macaluso (06/27/2012 08:29 PM EDT)
• Gundars Kokts (06/28/2012 04:51 AM EDT)
• Robert Lang (06/28/2012 09:02 AM EDT)
• Anees Shaikh (06/28/2012 11:47 AM EDT)
• Mutaamba Maasha (06/29/2012 02:01 PM EDT)
• Todd Will (06/29/2012 04:49 PM EDT)
• Joseph Yoon (06/30/2012 03:55 PM EDT)
• Manuel Sanchez-Gestido (06/30/2012 03:58 PM EDT)
• Jason Levy (07/01/2012 04:52 AM EDT)