Coding Pairs of Numbers

Date: 10/18/2001 at 16:18:07
From: SoonMin Yee
Subject: Coding Pairs of Numbers

I have been told that it is possible to code pairs of numbers as 
single numbers. Supposedly, for example, the pair (a, b) can be 
represented as a single natural number by the following equation:

1/2 ((a + b)^2 + 3a + b)

(where ^2 is a superscript). I have plugged in numbers for a and b 
and worked it out. But what I do not see is how that necessarily 
"codes the pair" (a, b) into a single number. 

Perhaps I am just misunderstanding what is meant. Does this at all 
make sense and, if so, what am I not seeing? (I guess the real 
question is that if this equation codes the pair (a,b) into a single 
number, it would seem logical that it is somehow possible to "recover" 
the pair from the single number, but I am not sure how that would 
work.)

Date: 10/18/2001 at 22:20:28
From: Doctor Peterson
Subject: Re: Coding Pairs of Numbers

Hi, SoonMin.

I recognize this as essentially the same as the formula I discussed 
here:

   Counting Positive Rational Numbers
   http://mathforum.org/dr.math/problems/alfred.09.09.01.html   

If you make a table of values of this function

    f(a,b) = [(a+b)^2 + 3a + b]/2

      b
        0  1  2  3
   a  +------------
    0 | 0  1  3  6
    1 | 2  4  7
    2 | 5  8
    3 | 9  ...

you can see that it actually counts through all pairs diagonally, 
first 0, the 1-2, then 3-4-5, and so on. How can we prove this? We can 
simply construct the function from this fact. The a=0 row of my table 
consists of triangular numbers; for any pair (a,b), if we follow its 
diagonal up to this row (subtracting a from the function value), we 
will be at (a+b,0) and 
will find triangular number T[a+b] there.

This means that

    f(a,b) = T[a+b] + a
           = (a+b)(a+b+1)/2 + a
           = [(a+b)^2 + (a+b) + 2a]/2
           = [(a+b)^2 + 3a + b]/2

which is just what you were given.

The way we formed this makes it clear that, as you were told, this 
function does in fact "encode" every pair of non-negative integers as 
a non-negative integer.

Now, as you say, that implies that we can extract the original pair 
from the function value. Let's do it!

First, we have to invert the triangular number. What is the greatest 
triangular number less than or equal to a given number N? Suppose that

    N = T[c]

    N = c(c+1)/2

    2N = c^2 + c

    c^2 + c - 2N = 0

Solving for c,

    c = [-1 +/- sqrt(1 + 8N)]/2

We need only the positive value for c, so

    c = [sqrt(8N+1) - 1]/2

Of course, this isn't in general an integer; but if we take the 
greatest integer less than this, we will get the index of the greatest 
triangular number not greater than N:

    T^-1(N) = int[[sqrt(8N+1) - 1]/2]

where I am writing "int[x]" as the greatest integer function for 
clarity.

Now, given that f(a,b) = T[a+b] + a, we can find a and b such that 
f(a,b)=N:

    We first find c = T^-1(N).

    Then c = a+b, and T(c) + a = N.

    So a = N - T(c), and b = c - a.

That is,

    a = N - c(c+1)/2

    b = c - N + c(c+1)/2
      = c(c+3)/2 - N

So yes, we can recover the pair from the function value.

There are, of course, other ways to do all this. An alternative 
"encoding" I can picture is simply to write a and b in binary and 
interleave the bits to form a new number twice as long. It would be 
easy to unpack this to recover the two numbers.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/