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

    CompuChip

    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

    congo
     
  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)

Loading...