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/ 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. Please help. 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. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/