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

In summary, to write natural number n in one and only one way as 1 less than a power of 2 times an odd number, one must do a few random examples and express the result as a power of 2 times an odd number. This can be done inductively or by setting up a recursion for f(n). Learning about turing machines would help in this case.
  • #1
gravenewworld
1,132
26
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:
Physics news on Phys.org
  • #2
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
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
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?
 
  • #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.
 
  • #6
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
how would learning about turing machines help in this case? (because we have skipped over chapters)
 
  • #8
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
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.
 

What are natural numbers?

Natural numbers are a set of positive whole numbers starting from 1 and continuing infinitely. They are often represented by the symbol "N".

How do we express natural numbers?

Natural numbers can be expressed in various ways, including using numerals (1, 2, 3, etc.), words (one, two, three, etc.), or symbols (I, II, III, etc.).

What is the importance of expressing natural numbers?

Expressing natural numbers is important in mathematics as it allows us to count, order, and perform operations on quantities. It also helps us understand patterns and relationships between numbers.

How are natural numbers different from whole numbers?

Natural numbers are a subset of whole numbers. While natural numbers start from 1, whole numbers include 0 in addition to all the natural numbers.

Can natural numbers be negative?

No, natural numbers cannot be negative. They are defined as positive whole numbers, and negative numbers are not included in this set.

Similar threads

  • Linear and Abstract Algebra
Replies
9
Views
2K
  • Linear and Abstract Algebra
Replies
11
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
748
  • Linear and Abstract Algebra
Replies
1
Views
912
  • Calculus and Beyond Homework Help
Replies
5
Views
613
  • Linear and Abstract Algebra
Replies
20
Views
3K
Replies
24
Views
955
  • Linear and Abstract Algebra
Replies
1
Views
776
Replies
23
Views
1K
Replies
3
Views
683
Back
Top