The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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:

 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!   
Associated Topics:
College Number Theory
High School Equations, Graphs, Translations
High School Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.