12

Given two integers $n$ and $m$ (assuming for both $0 < n < 1000000$) is there some function $f$ so that if I know $f(n, m) = x$ I can determine $n$ and $m$, given $x$? Order is important, so $f(n, m) \not= f(m,n)$ (unless $n=m$).

Thomas Russell
  • 10,425
  • 5
  • 38
  • 66
Jordan Reiter
  • 223

5 Answers5

22

$f(n,m) = 2^n 3^m$.

Alternatively, use the bijection between $\mathbb N \times \mathbb N$ and $\mathbb N$ which is given by $$f(n,m) = \frac{(n+m)(n+m+1)}{2} + m$$

marlu
  • 13,784
  • 3
    The advantage the $2^n 3^m$ approach has over all the other suggestions so far is that it gives you a way of encoding an ordered $r$-tuple without knowing in advance what $r$ is, by adding in powers of 5, 7 ... . – Mark Bennet Jul 02 '12 at 18:50
  • @MarkBennet This scaling advantage is also shared by the Cantor pairing function, through recursive application. – mboratko Jul 02 '12 at 19:46
  • 1
    @MichaelBoratko If you have an integer given by the Cantor Pairing you cannot decode it without knowing how many iterations you have to go through. The prime product gives you this, at the cost of not being surjective, and this also means that the coded values will tend to be significantly higher for the prime product version. – Mark Bennet Jul 02 '12 at 19:53
  • This is how Godel numbering works, btw – houbysoft Jul 02 '12 at 23:14
  • @MarkBennet Ah, now I understand what you meant. – mboratko Jul 02 '12 at 23:53
20

Since others have answered, here is another idea - less easy to write down explicitly as a mathematical function, but easy to describe and easy to implement if you have a machine which can handle strings. Send the digits of the first number to odd positions and the digits of the other to even positions so (31, 5681) would go to 50,608,311.

Mark Bennet
  • 100,194
  • But this would only work if the numbers had the same number of digits, right? – Jordan Reiter Jul 02 '12 at 20:33
  • 4
    @JordanReiter I have deliberately used an example where the number of digits is different. – Mark Bennet Jul 02 '12 at 21:03
  • 1
    This is the first answer so far that doesn't necessarily use at least one more than the maximum number of digits each integer is allowed, plus it has an infinite range and it's trivially easy to parse back out without knowing the original maximums. It also works just as well in binary as decimal. If storage is a premium - and I can't think of any other reason to do something like this - yours would be my first choice. – SilverbackNet Jul 02 '12 at 23:02
  • @MarkBennet sorry, I see that now! – Jordan Reiter Jul 03 '12 at 16:19
14

If there are no bounds on your integers, use the Cantor pairing function. It is pleasantly easy to compute, as are its two "inverses."

For the case where your integers are bounded by say $10^6$, you can simply concatenate the decimal expansions, padding with initial $0$'s as appropriate. Or do something similar with binary expansions. Dirt cheap to combine and uncombine, an easy string manipulation even when we allow bounds much larger than $10^6$.

André Nicolas
  • 507,029
  • 7
    Of course the concatenation procedure can also be written mathematically: $f(m,n) = 10^6 m + n$. Given $f(m,n)$, you get back $m$ and $n$ as quotient and reminder when dividing by $10^6$. – celtschk Jul 02 '12 at 18:42
10

Define $f(n,m) = n+1000000m$. Then $n = f(n,m) \mod 1000000$, and $m = \frac{f(n,m) - n}{1000000}$.

copper.hat
  • 172,524
2

f(m,n) = m +(1/n)

If there are numbers to the right of the decimal,
m =number to the left of decimal.
n = the reciprocal of the numbers to the right of the decimal
example
f(m,n) =10.5 then m =10, n=1/(0.5) =2

If there are no numbers to right of the decimal [f(m,n) is itself an integer]
then m = f(m,n) -1,
n =1
example
f(m,n) =20 then m=19, n =1

jeff
  • 285