August 2007
<<July August September>>
Define f(0)=1 and f(n) to be the number of different ways n can be expressed as a sum of integer powers of 2 using each power no more than twice.
For example, f(10)=5 since there are five different ways to express 10: 1+1+8, 1+1+4+4, 1+1+2+2+4, 2+4+4 and 2+8.
Describe, in a single sentence, the multiset {f(n)/f(n-1)} for positive integer n.
Show your proof to this sentence.
As usual, we ask that you only submit your original work.
UPDATE, 8/2/07: The solution is more elegant than just a recursion formula. You'll recognize it once you find it.
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
Challenge:
08/02/2007 @ 10:00 AM EDT
Solution:
09/05/2007 @ 02:30 PM EDT
List Updated:
09/05/2007 @ 02:30 PM EDT
People who answered correctly:
Henry Bottomley (08.02.2007 @01:14:21 PM EDT)
Alan Murray (08.02.2007 @03:19:18 PM EDT)
Yang Frank (08.02.2007 @04:55:02 PM EDT)
Jiri Navratil (08.02.2007 @06:06:34 PM EDT)
Balakrishnan V (08.02.2007 @06:41:20 PM EDT)
Ashutosh Mehra (08.02.2007 @06:46:31 PM EDT)
Ramasamy Chandramouli (08.02.2007 @07:09:32 PM EDT)
John T Robinson (08.02.2007 @08:34:12 PM EDT)
Dan Dima (08.02.2007 @09:39:32 PM EDT)
Irem Koprulu and Atilla Eryilmaz (08.02.2007 @11:29:10 PM EDT)
Michael Quist (08.03.2007 @12:04:50 AM EDT)
Graeme McRae (08.03.2007 @ 02:11:13 AM EDT)
Albert Stadler (08.03.2007 @ 02:45:17 AM EDT)
Daniel Bitin (08.03.2007 @ 07:07:35 AM EDT)
Joseph DeVincentis (08.03.2007 @ 11:01:22 AM EDT)
Michael Brand (08.04.2007 @12:20:00 AM EDT)
Alexander Vardy (08.04.2007 @01:01:43 PM EDT)
Celia Anteneodo (08.04.2007 @02:32:01 PM EDT)
Harsha HS (08.05.2007 @02:09:23:22 AM EDT)
Daniel Hsu (08.05.2007 @02:41:27 AM EDT)
Harald Boegeholz (08.05.2007 @12:28:10 PM EDT)
Philippe Fondanaiche (08.05.2007 @01:04:09 PM EDT)
Ed Sheppard (08.05.2007 @03:24:01 PM EDT)
Josh Boorstein (08.05.2007 @04:10:33 PM EDT)
Gale Greenlee (08.05.2007 @08:07:17 PM EDT)
John G. Fletcher (08.06.2007 @01:12:05 AM EDT)
James Dow Allen (08.06.2007 @02:48:27 AM EDT)
Christian Blatter (08.06.2007 @07:35:15 AM EDT)
Arthur Breitman (08.06.2007 @10:57:25 AM EDT)
Dr. Phil Muhm (08.06.2007 @11:15:37 AM EDT)
Dion Harmon (08.06.2007 @11:26:09 AM EDT)
Adel El-Atawy (08.06.2007 @03:56:18 PM EDT)
Wei Zhou (08.06.2007 @08:02:49 PM EDT)
Zhou Guang (08.07.2007 @03:40:45 AM EDT)
Riyaaz Shaik (08.07.2007 @04:04:38 AM EDT)
Adrian Atanasiu (08.07.2007 @7:25:47 AM EDT)
Wang Tong (08.07.2007 @07:41:11 AM EDT)
Cobus de Waal (08.07.2007 @09:38:11 AM EDT)
Se Kwon Kim (08.07.2007 @12:42:45 PM EDT)
Karl D’Souza (08.07.2007 @01:59:09 PM EDT)
Dave Biggar (08.08.2007 @07:39:54 AM EDT)
Roy John (08.09.2007 @07:07:56 AM EDT)
David McQuillan (08.09.2007 @05:04:06 PM EDT)
Parashar Dave (08.10.2007 @01:05:07 AM EDT)
Andrew Buchanan (08.10.2007 @11:38:26 AM EDT)
Øyvind Grotmol (08.11.2007 @06:30:31 AM EDT)
Roger Thompson (08.13.2007 @02:58:43 AM EDT)
José H. Nieto (08.13.2007 @06:51:50 AM EDT)
Patricios Tlacaelel Alva Pufleau (08.13.2007 @06:35:30 PM EDT)
Rajeev Rao (08.15.2007 @002:33:37 PM EDT)
Abhisek Ukil (08.16.2007 @07:17:45 AM EDT)
Clive Tong (08.16.2007 @11:24:26 AM EDT)
Ionel Santa (08.16.2007 @03:09:34 PM EDT)
Tom Gutman (08.16.2007 @03:56:25 PM EDT)
Hongcheng Zhu (08.16.2007 @10:26:49 PM EDT)
Martin Thiim (08.20.2007 @09:48:06 AM EDT)
Suthambhara N (08.20.2007 @02:17:09 PM EDT)
Jack Kennedy (08.21.2007 @05:46:55 AM EDT)
Wolfgang Kais (08.21.2007 @09:01:54 AM EDT)
Duane Bailey (08.21.2007 @05:11:39 PM EDT)
Renato Fonseca (08.21.2007 @08:58:20 PM EDT)
Balazs Ugron (08.22.2007 @07:38:49 AM EDT)
Maxim G. Smith (08.22.2007 @01:18:27 PM EDT)
Erik Hostens (08.23.2007 @04:11:41 AM EDT)
Karthik Tadinada (08.23.2007 @10:56:31 AM EDT)
Ervan Darnell (08.25.2007 @01:53:34 AM EDT)
Changyuan Yu (08.26.2007 @04:29:34 AM EDT)
David Friedman (08.26.2007 @10:38:23 AM EDT)
Andreas Eisele (08.27.2007 @12:23:23 PM EDT)
Bhaumik Chokshi (08.27.2007 @03:11:01 PM EDT)
Guillaume de Longeaux (08.29.2007 @05:47:10 PM EDT)
Dharmadeep Muppalla (08.31.2007 @07:46:00 AM EDT)
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.