1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Interesting one
  1. This is interesting. (Replies: 1)

  2. Interesting Identity (Replies: 4)

  3. Interest Formula (Replies: 2)