All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Interesting representation (Posted on 2016-02-08)
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:

Comments: ( Back to comment list | You must be logged in to post comments.)
 Some ideas | Comment 4 of 6 |
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.

Es
13=3^2+2^2   26=2*3^2+2^3

21=2^2*3+3^2   30=21+9=2^2*3+2*3^2

Edited on February 14, 2016, 3:23 pm
 Posted by armando on 2016-02-14 10:32:27

 Search: Search body:
Forums (0)