Drexel dragonThe Math ForumDonate to the Math Forum

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

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/   
    
Associated Topics:
High School Number Theory
High School Sequences, Series

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-2013 The Math Forum
http://mathforum.org/dr.math/