Writing Natural Numbers: A Unique Expression Using Powers of 2 and Odd Numbers

[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

 

[Hurkyl]

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.

 

[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.

 

[Hurkyl]

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?

 

[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.

 

[Hurkyl]

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)

 

[gravenewworld]

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

 

[Hurkyl]

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.

 

[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.