Coding Pairs of NumbersDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/