Interesting one

1. Aug 31, 2010

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

2. Aug 31, 2010

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'.

3. Sep 1, 2010

sachinism

nice one man , exactly what i had in mind

congo

4. Sep 2, 2010

D H

Staff Emeritus
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.

5. Sep 2, 2010

D H

Staff Emeritus
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.