Summing Positive Integers with 2^r3^s

[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

 

[CompuChip]

Using induction (1 = 2⁰ 3⁰; 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 2^r 3^s + 2^{r + r'} 3^{s + s'} and show that they can be written as 2^a 3^b + 2^a' 3^b' 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 2^r 3^s + 2^{r + r'} 3^{s + s'} and show that they can be written as 2^a 3^b + 2^a' 3^b' for appropriate a, b, a' and b'.

Doesn't work. 1=2⁰3⁰ and 2=2⁰3⁰+1. How do you get from 2=2⁰3⁰+1=1+1 (illegal) to 2=2¹3⁰ 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=2⁰3⁰.
• 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.