Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Interesting one

  1. Aug 31, 2010 #1
    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:
  2. jcsd
  3. Aug 31, 2010 #2


    User Avatar
    Science Advisor
    Homework Helper

    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'.
  4. Sep 1, 2010 #3
    nice one man , exactly what i had in mind

  5. Sep 2, 2010 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
  6. Sep 2, 2010 #5

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook