Inverse Function for Natural Numbers
Date: 6/10/96 at 11:32:20 From: Juhasz Tibor Subject: Inverse function for natural numbers Dear Dr. Math, I've read about a bijective function in the book Roger Penrose: _The Emperor's New Mind_. This function connects the pairs of natural numbers to single natural numbers based on the following formula: (a,b) -> n: n = 0.5((a+b)^2+3a+b); a, b and n are natural numbers. But what is the formula of the inverse function? How can I calculate the a and b based on the n? Can you help me? I would be very grateful to you. Tibor Juhasz
Date: 6/13/96 at 23:24:36 From: Doctor Ceeks Subject: Re: Inverse function for natural numbers Let z = a+b. Note that z^2+z <= 2n < (z+1)^2+(z+1) (Recall that a,b >= 0). Therefore z=[(-1+sqr(1+8n))/2] where [x] = greatest integer less than or equal to x. We then have a = n-(z^2+z)/2 and b = (z^2+3z)/2-n. It might help if you wrote the number n over (a,b) on a piece of graph paper to see what is going on: 10 6 11 3 7 12 1 4 8 13 0 2 5 9 14 (for the first few). Note on terminology: Some people mean "natural numbers" to be the positive integers, and some people mean it to be the non-negative integers, so it never hurts to specify which meaning you intend (in this case, non-negative integers). -Doctor Ceeks, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.