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.
February 2022 - Challenge
It is well known that every natural number can be uniquely written as the sum of powers of 2, e.g., . The same goes for powers of 3, e.g.,
. In these representations, for every pair of summands, one divides the other, i.e.,
divides
and
divides
.
However, if we allow the representation of numbers as a sum of the product of a power of 2 and a power of 3, it is possible to find for every number a representation where for each pair of summands, none divides the other, e.g., ,
, and as a more complex example,
. In the last example, the list of powers involved can be also written as [(5, 0), (4, 1), (3, 2), (2, 4), (0, 5)], where each pair (a,b) represents the number
.
Let’s look at the number 10100100101110110000. That’s a 20-digit number in base 10, whose digits consist only of 1s and 0s, with a leading 1. It can be represented in the above method as [(41, 2), (30, 12), (29, 13), (26, 19), (20, 23), (13, 28), (12, 31), (4, 37)].
Your goal: Find a number with exactly 200 decimal digits, consisting only of the digits 1 and 0 with a leading 1, that can be represented by a sum of less than 150 summands. Write your solution in two lines: The first consisting of the number itself, and the second consisting of the list of powers, in the list format given above.
A bonus "*" will be given for finding a 300-digit number with a sum of less than 215 summands.
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:
01/02/2022 @ 12:00 PM EST
Solution:
04/03/2022 @ 12:00 PM EST
List Updated:
07/02/2022 @ 12:00 PM EST
People who answered correctly:
*Lazar Ilic (1/2/2022 2:29 PM IDT)
*Paul Revenant (1/2/2022 4:51 PM IDT)
*Gaétan Berthe (1/2/2022 5:05 PM IDT)
Reiner Martin (2/2/2022 1:48 AM IDT)
*Sanandan Swaminathan (2/2/2022 8:47 AM IDT)
*Anders Kaseorg (2/2/2022 2:16 PM IDT)
*Alexander Gramolin (3/2/2022 3:23 AM IDT)
*Benjamin Lui (3/2/2022 8:16 AM IDT)
*Uoti Urpala (3/2/2022 9:17 AM IDT)
*Vladimir Volevich (3/2/2022 7:57 PM IDT)
*Bert Dobbelaere (5/2/2022 11:36 AM IDT)
*Asaf Zimmerman (6/2/2022 5:48 PM IDT)
*Latchezar Christov (7/2/2022 10:50 PM IDT)
*Peter Moser (8/2/2022 4:00 PM IDT)
*Amos Guler (8/2/2022 11:34 PM IDT)
*Oleg Vlasii (9/2/2022 10:27 AM IDT)
*Daniel Chong Jyh Tar (9/2/2022 5:48 PM IDT)
*Marco Bellocchi (11/2/2022 7:56 AM IDT)
*Li Li (11/2/2022 11:29 AM IDT)
*Andreas Stiller (11/2/2022 8:09 PM IDT)
*Pål Hermunn Johansen (12/2/2022 5:53 PM IDT)
*Daniel Bitin (12/2/2022 11:15 PM IDT)
*Gary M. Gerken (13/2/2022 6:51 AM IDT)
Maksym Voznyy (13/2/2022 8:31 PM IDT)
*Thomas Egense (15/2/2022 4:45 PM IDT)
*Alper Halbutogullari (15/2/2022 9:51 PM IDT)
*Bertram Felgenhauer (17/2/2022 3:47 PM IDT)
*Dan Dima (17/2/2022 7:52 PM IDT)
*Franciraldo Cavalcante (19/2/2022 12:27 AM IDT)
*Tim Walters (21/2/2022 3:20 AM IDT)
*David Greer (21/2/2022 1:28 PM IDT)
*Liubing Yu (23/2/2022 9:52 AM IDT)
Peter Wu (23/2/2022 11:32 AM IDT)
*Chris Shannon (24/2/2022 2:58 AM IDT)
*Karl Mahlburg (24/2/2022 4:41 AM IDT)
Eran Vered (25/2/2022 6:24 PM IDT)
*Stephen H. Landrum (27/2/2022 12:26 AM IDT)
*Motty Porat (27/2/2022 1:37 AM IDT)
*John Goh (1/3/2022 5:42 AM IDT)
*Radu-Alexandru Todor (1/3/2022 10:58 AM IDT)
Nyles Heise (3/3/2022 5:17 AM IDT)
*Clive Tong (3/3/2022 7:15 PM IDT)