IBM Ponder This #286 · February 2022

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\cdot 3+3^2=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.

Solution

Best opened after a real attempt

To be added.