About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
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.