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/
```

```Date: 05/26/2016 at 03:37:08
From: Ram
Subject: Coding Pairs of Numbers

Sir, I cannot implement this coding.

If you please provide me with an example, I will be highly obliged.

```

```Date: 05/26/2016 at 13:25:12
From: Doctor Peterson
Subject: Re: Coding Pairs of Numbers

Hi, Ram.

To encode a pair, we use

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

Say we want to encode (13, 5). We can collapse it so:

f(13, 5) = [(13 + 5)^2 + 3*13 + 5]/2
= 184

To decode this, we use

c = int[[sqrt(8N + 1) - 1]/2]
a = N - c(c + 1)/2
b = c(c + 3)/2 - N

Thus,

c = int[[sqrt(8*184 + 1) - 1]/2]
= int[18.69]
= 18

a = 184 - 18(18 + 1)/2
= 184 - 171
= 13

b = 18(18 + 3)/2 - 184
= 189 - 184
= 5

And these were the numbers I started with.

Is that what you need to see?

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

```Date: 05/27/2016 at 10:50:21
From: Ram
Subject: Thank you (Coding Pairs of Numbers)

Sir, I am really very much thankful for the time you have provided me. I
am highly obliged. Very, very thank you, sir. Good night, sir.
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search