Interesting one

[sachinism]

Show that every positive integer is a sum of one or more numbers of the form 2^r3^s, where r and s are nonnegative integers and no summand divides another.

not my doubt

just found it interesting so posted here :smile:

[CompuChip]

Using induction (1 = 20 30; assuming that k can be written in such a way, then so can k + 1) is the easy part.
You only need to exercise some care with the part that "no summand divides another."

So assuming that all k < n can be written as requested, suppose that you get two terms 2r 3s + 2r + r' 3s + s' and show that they can be written as 2a 3b + 2a' 3b' for appropriate a, b, a' and b'.

[sachinism]

nice one man , exactly what i had in mind

congo

[D H]

So assuming that all k < n can be written as requested, suppose that you get two terms 2r 3s + 2r + r' 3s + s' and show that they can be written as 2a 3b + 2a' 3b' for appropriate a, b, a' and b'.
Doesn't work. 1=2030 and 2=2030+1. How do you get from 2=2030+1=1+1 (illegal) to 2=2130 via this? This approach only works for a small number of elements k: 4 and 6, but not 2,3,4, or 7.

[D H]

Recursion will work here, however. Just not in the simple way that CompuChip mentioned.

I don't know if this is homework, so providing an answer is not appropriate. Some hints are:
Recursion is a good idea, with an obvious base case of 1=2030.
Game over if n is divisible by 2 or 3 (why?)
That leaves the cases where n is not divisible by either 2 or by 3. I'll leave attacking these as an exercise to the OP.