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

Expressing natural numbers

  1. Apr 17, 2005 #1
    How can one write any natural number n in one and only one way as 1 less than a power of 2 times an odd number?

    n=2^f(n)(2g(n)-1)-1


    where the red minus is the modified difference function, i.e. x-y =x-y if x>=y or x-y=0 if x<y
     
    Last edited: Apr 17, 2005
  2. jcsd
  3. Apr 17, 2005 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    By adding one to n, and expressing the result as a power of 2 times an odd number!

    It's fairly simple -- just do a few random examples, and all should be made clear.
     
  4. Apr 17, 2005 #3
    I could let f(n)=z(n) where z(n) is the function that takes all n to 0 and let g(n)=n/2+1. That works, but my problem is that this is the 1st step of 1 problem. I have to be able in the end to show that f(n) and g(n) are primitive recursive, and I have learned of no way thus far to express things like n/2 as a primitive recursive function.
     
  5. Apr 17, 2005 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I guess you haven't gotten to turing machines yet -- I think that would make this fairly easy.


    Let's start with f(n) = floor(n/2), I suppose.


    What you need, I think, is to find a way to write this function inductively.

    Or...

    Can you write a primitive recursive function g(x, y) that is 1 if and only if 2x = y or 2x+1 = y? Then couldn't you use g, somehow, to express f?
     
  6. Apr 17, 2005 #5
    floor(n/2) is just the quotient of dividing n by 2 right?

    quo(n,2)=floor(n/2) and I know quo is PR.
     
  7. Apr 17, 2005 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Hrm.

    Have you looked at the actual sequence f(n)? Maybe that would suggest an approach.


    Or, you could look at setting up a recursion for f(n). For example, f(2n+1)=2f(n) gives you half the values. (Or something like that -- I think I have an off by one or two error)
     
  8. Apr 17, 2005 #7
    how would learning about turing machines help in this case? (because we have skipped over chapters)
     
  9. Apr 17, 2005 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, if I recall correctly (and I might not), the class of primitive recursive functions is the same as the (Turing) computable functions.

    It's fairly easy to present an algorithm for computing f(n) and g(n) that terminates on every output, so the functions are (Turing) computable.
     
  10. Apr 18, 2005 #9
    Ahhh I give up on this problem. I already spent 4+ hours on it. Its 330 am and have way to much other homework to do.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Expressing natural numbers
  1. Natural numbers Z? (Replies: 6)

  2. Natural Numbers Proof? (Replies: 5)

Loading...