Expressing natural numbers

1. Apr 17, 2005

gravenewworld

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. Apr 17, 2005

Hurkyl

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.

3. Apr 17, 2005

gravenewworld

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.

4. Apr 17, 2005

Hurkyl

Staff Emeritus
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?

5. Apr 17, 2005

gravenewworld

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.

6. Apr 17, 2005

Hurkyl

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)

7. Apr 17, 2005

gravenewworld

how would learning about turing machines help in this case? (because we have skipped over chapters)

8. Apr 17, 2005

Hurkyl

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.

9. Apr 18, 2005

gravenewworld

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.