Ponder This Challenge - January 2012 - Exploding dragon egg

Ponder This Challenge:

This months challenge is based on an idea from Anees Shaikh.
For each natural number there is a lamp.
At the beginning (Midnight between Saturday and Sunday), all the lamps are off.
1/2 of a second later came a little dwarf who switched their state (i.e., turned them all on).
1/4 of a second later, another dwarf comes and toggles the lamp switch for every second number. Now all the even lamps are off again and all the odd ones stay on.
1/8 of a second later comes yet another dwarf and toggles the lamp of every third number: the number 3, which was on, gets turned off, the number 6 which was off is now on, etc.
1/16 of a second later, another dwarf toggles every fourth number, and so on (after 1/2^n of a second the dwarf toggles all the numbers that are divisible by n).

Meanwhile, a red dragon is learning to count:
It counts "one" and drops a flammable egg near lamp #1.
It counts "one, two" and leaves another egg near lamp #3.
It counts "one, two, three" and places an egg near lamp #6.
It counts "one, two, three, four" and lays an egg near lamp #10; and so on.

The red dragon walks at a constant pace of one lamp per second.
Suddenly, he lays an egg too close to one of the lamps, which was on at the time, and therefore hot, and it immediately explodes.
The explosion ruined the lamp's number sign, but the last three digits are still visible: "576".
When did the explosion occur? What day of the week, hour, minutes, and seconds?

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

  In the first part of the challenge, the dwarfs leave the scene after a second and leave a lamp on if and only if its number has an odd number of divisors.

  Divisors usually comes in pairs: d and n/d. Only perfect squares can have an odd number of divisors.

  The dragon goes over all the triangle numbers, i.e., numbers that are the sum of consecutive integers from 1 to m.

  Our challenge was to find an integer n that satisfies

  n = 576+1000*l = k*k = m*(m+1)/2

  for some integers l, k, and m. These numbers satisfy ( http://en.wikipedia.org/wiki/Square_triangular_number) a recursion formula

  n_{k+1} = 34*n_k - n_{k-1} + 2 with the initial value of n_1=1 and n_0=0.

  Since we are interested in n modulo (7*24*60*60), we can compute the full cycle, using the recursion above, and get three possible solutions:

  Thu 12:09:36; Mon 21:09:36; and Mon 00:09:36.

Solvers

• Dan Dima (12/30/2011 02:27 PM EDT)
• Nick McGrath (12/30/2011 02:52 PM EDT)
• Joanna Cheng (12/30/2011 09:54 PM EDT)
• Radu-Alexandru Todor (12/31/2011 08:35 AM EDT)
• Michael Brand (12/31/2011 11:52 AM EDT)
• Kevin Williamson (12/31/2011 06:51 PM EDT)
• Joseph DeVincentis (12/31/2011 09:44 PM EDT)
• Alex Chan (01/01/2012 05:04 AM EDT)
• Andreas Razen (01/01/2012 03:45 PM EDT)
• Denys Kopiychenko (01/01/2012 04:00 PM EDT)
• Katarzyna Wojdziak (01/01/2012 06:49 PM EDT)
• Mark Pervovskiy (01/01/2012 06:55 PM EDT)
• Sergey Grishaev (01/01/2012 07:39 PM EDT)
• Radu Borza (01/02/2012 02:13 AM EDT)
• Irving Dai (01/02/2012 03:49 AM EDT)
• Ryan Milligan (01/02/2012 05:48 AM EDT)
• Phil Benamy (01/02/2012 05:30 PM EDT)
• Hakan Summakoglu (01/02/2012 09:51 AM EDT)
• Jan Fricke (01/02/2012 06:13 PM EDT)
• Gergely Pataki (01/02/2012 06:15 PM EDT)
• Peter de Rivaz (01/02/2012 06:20 PM EDT)
• John Snyder (01/02/2012 06:33 PM EDT)
• Harald Bögeholz (01/02/2012 07:37 PM EDT)
• Kipp Johnson (01/02/2012 09:01 PM EDT)
• J. Eric Ivancich (01/02/2012 09:01 PM EDT)
• Subbu Devulapalli (01/02/2012 10:16 PM EDT)
• Peter Gerritson (01/02/2012 11:17 PM EDT)
• Deron Stewart (01/03/2012 12:43 AM EDT)
• Daniel Scheinerman (01/03/2012 01:00 AM EDT)
• Dejan Stakic (01/03/2012 08:11 AM EDT)
• Stancu Mihai (01/03/2012 08:26 AM EDT)
• Chris Lewis (01/03/2012 08:45 AM EDT)
• Frederik Kaster (01/03/2012 10:58 AM EDT)
• Kevin Sham (01/03/2012 12:09 PM EDT)
• Mark Mammel (01/03/2012 02:40 PM EDT)
• Karl D'Souza (01/03/2012 03:46 PM EDT)
• Daniil Agashiyev (01/03/2012 05:28 PM EDT)
• Gale Greenlee (01/03/2012 06:43 PM EDT)
• Kshitij Gajjar (01/03/2012 07:39 PM EDT)
• Kevin Berk (01/03/2012 07:57 PM EDT)
• Arthur Breitman (01/03/2012 08:00 PM EDT)
• Shmuel Menachem Spiegel (01/04/2012 02:08 AM EDT)
• Wu ChengYuan (01/04/2012 03:43 AM EDT)
• Nicolas Wu & Andres Löh (01/04/2012 09:05 AM EDT)
• Tom Cooper (01/04/2012 09:43 AM EDT)
• Wolfgang Kais (01/04/2012 12:14 PM EDT)
• Shouky Dan & Tamir Ganor (01/04/2012 12:28 PM EDT)
• David P. Stigant (01/04/2012 04:38 PM EDT)
• Liubing Yu (01/04/2012 04:39 PM EDT)
• David Friedman (01/04/2012 07:22 PM EDT)
• Mark Manashirov (01/04/2012 08:54 PM EDT)
• Nivrutti Tambe (01/05/2012 07:22 AM EDT)
• Jonas Lindstrøm Jensen (01/05/2012 09:59 AM EDT)
• Adrian Neacsu (01/05/2012 10:41 AM EDT)
• Guler Amos (01/05/2012 10:49 AM EDT)
• Ishaan Chugh (1/05/2012 12:30 PM EDT)
• Karanveer Mohan (01/05/2012 12:38 PM EDT)
• Donald Dodson (01/05/2012 03:48 PM EDT)
• Walter Schmidt (01/05/2012 04:25 PM EDT)
• Daniel Bitin (01/05/2012 06:28 PM EDT)
• Adam Daire (01/05/2012 07:45 PM EDT)
• George J. Ross (01/06/2012 01:47 AM EDT)
• Sumanth Ravipati (01/06/2012 05:50 PM EDT)
• Anirudh Garg (01/06/2012 07:33 PM EDT)
• Jun Wang (01/07/2012 05:55 PM EDT)
• Shilei Zang (01/07/2012 06:04 PM EDT)
• Øyvind Grotmol (01/08/2012 11:39 AM EDT)
• Allen Sirolly (01/08/2012 05:36 PM EDT)
• David Greer (01/09/2012 04:23 PM EDT)
• Álvaro Begué (01/09/2012 05:23 PM EDT)
• Anunay Kulshrestha (01/09/2012 05:27 PM EDT)
• Christopher Marks (01/09/2012 06:22 PM EDT)
• Sumeet Katariya (01/10/2012 12:43 PM EDT)
• LEE Sing Chun (01/10/2012 03:54 PM EDT)
• Ashutosh Mahajan (01/10/2012 11:00 PM EDT)
• Anoop Ghanwani (01/11/2012 05:37 AM EDT)
• Serge Thill (01/11/2012 10:46 AM EDT)
• Clive Tong (01/11/2012 06:47 PM EDT)
• Renato Fonseca (01/11/2012 10:18 PM EDT)
• Rajendran Thirupugalsamy (01/12/2012 01:38 AM EDT)
• Jyothish Soman (01/12/2012 6:31 PM EDT)
• Chris Shannon (01/13/2012 04:20 AM EDT)
• Mathias Schenker (01/13/2012 06:39 AM EDT)
• Phil Muhm (01/13/2012 01:05 PM EDT)
• Sushanth Kodali (01/14/2012 03:14 AM EDT)
• Matej Kollár (01/15/2012 08:38 PM EDT)
• Joaquim Neves Carrapa (01/17/2012 11:10 AM EDT)
• Florin Spinu (01/17/2012 03:04 PM EDT)
• Abhishek Goyal (01/18/2012 02:56 PM EDT)
• Stefan Sec Zehl (01/19/2012 08:53 AM EDT)
• Dan Karliner (01/19/2012 10:16 AM EDT)
• Nagy Zoltan (01/19/2012 05:02 PM EDT)
• Edgardo Deza (01/20/2012 10:33 AM EDT)
• Armin Krauss (01/20/2012 04:41 PM EDT)
• Reinder Verlinde (01/20/2012 10:13 PM EDT)
• James Aaronson (01/21/2012 02:02 PM EDT)
• David Zimmermann (01/23/2012 04:05 PM EDT)
• Jon Namnath (01/24/2012 10:08 PM EDT)
• Kaverappa O T (01/25/2012 10:10 AM EDT)
• Nitish Chandran (01/25/2012 02:29 PM EDT)
• Anlu Wang (01/26/2012 03:00 AM EDT)
• Amir Sarid (01/26/2012 05:38 AM EDT)
• Sudhir Jha (01/26/2012 12:57 PM EDT)
• Matthias Graefenhan (01/26/2012 05:08 PM EDT)
• Stéphane Higueret (01/26/2012 08:07 PM EDT)
• Joshua Gunderson & Dustin Shively (01/26/2012 10:29 PM EDT)
• Alvaro Martinez Echevarria (01/28/2012 11:51 PM EDT)
• Albert Stadler (01/29/2012 03:14 PM EDT)
• Asaf Aharoni (01/29/2012 10:15 PM EDT)
• Adriana Clerici (01/30/2012 12:23 PM EDT)
• Kurt Hectic (01/30/2012 07:32 PM EDT)
• William Mantzel (01/31/2012 09:04 PM EDT)
• Christopher Parham (01/30/2012 10:18 PM EDT)
• Richard Bauer (01/31/2012 11:16 PM EDT)