February 2022 - Challenge
It is well known that every natural number can be uniquely written as the sum of powers of 2, e.g., 13 = 1 + 4 + 8. The same goes for powers of 3, e.g., 13 = 1 + 3 + 9. In these representations, for every pair of summands, one divides the other, i.e., 4 divides 8 and 3 divides 9.
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., 13 = 4 + 9, 15 = 2\cdot3 = 6 + 9, and as a more complex example, 719 = 32 + 48 + 72 + 324 + 243. 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 2^{a}3^{b}.
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)