## Expressing natural numbers

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
 PhysOrg.com science news on PhysOrg.com >> Ants and carnivorous plants conspire for mutualistic feeding>> Forecast for Titan: Wild weather could be ahead>> Researchers stitch defects into the world's thinnest semiconductor
 Recognitions: Gold Member Science Advisor Staff Emeritus 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.
 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.

Recognitions:
Gold Member
Staff Emeritus

## Expressing natural numbers

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

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?
 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.
 Recognitions: Gold Member Science Advisor Staff Emeritus 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)
 how would learning about turing machines help in this case? (because we have skipped over chapters)
 Recognitions: Gold Member Science Advisor Staff Emeritus 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.
 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.