Show that every positive integer is a sum of one or more
numbers of the form 2^r*3^s, where r and s are nonnegative
integers and no summand divides another.
Remarks: This problem was originally created by Paul Erdős.
Note that the representations need not be unique: for instance,
11 = 2+9 = 3+8:
number 1 is rule out as a summand for the other numbers, because the restriction that no summand divides another.
For even numbers it is always possible to express them relaying on its divisor odd number. If this odd can be express as a sum of 2^r*3^s terms, the same for the even number, just multiplying by 2. If the even number comes from other even, we can repeat again the same and multiply the odd by 2^2, and so on.
So all the evens depends on the odds. If we can express the odds, so the evens.
I haven't a winning strategy for the odds. What I have see is that it is possible to fill the numbers just adding 8, 9, or 10 (2^3, 3^2, 2*3+2^2) to a number already fill. Often adding 9 do not modify the condition of indivisibility, but sometimes does. Adding 8 or 10 solve the problem, in the numbers I have tested.
But I suppose that when numbers are bigger, would be necessary to change this numbers proportionally (to 26, 27, 28, and 80,81,82 and so on. Not did it.
Edited on February 14, 2016, 3:23 pm
Posted by armando
on 2016-02-14 10:32:27