# A scheme to uniquely identify two integers using a single integer, with a very cheap conversion?

Assume there is a static max of N for either value, such that X <= N and Y <= N.

I would like a function such that:

func(X0,Y0) != func(X1,Y1) for all values IFF:
1. X0,Y0,X1,Y1 <= N
2. X0 != X1 and Y0 != Y1
3. X0 != Y1 and Y0 != X1


So to be clear, func(X,Y) = func(Y,X).

The result of this function should be an integer, and it should also be simple and trivial to calculate X and Y from the result of the function.

I'd like to also be able to do this without determining which of X or Y is the max.

Is this something that is impossible by principle?

Thanks!

EDIT:

Oops! N is non-negative.

-
How large is $N$? Is it just purely theoretical question, or you have some restrictions here? – Vadim Apr 22 '12 at 3:41
Surely $x$ and $y$ are non-negative also? – Théophile Apr 22 '12 at 15:14

## 3 Answers

$f(x,y)=2^{x+y}3^{|x-y|}$ should do. Given an output, divide by 2 repeatedly until you get an odd number, then divide by 3 repeatedly until you get 1; counting up the numbers of divisions, you find $m$ and $n$ such that the output was $2^m3^n$. Now to retrieve $x$ and $y$, all you have to do is solve the equations $x+y=m$, $x-y=n$, getting $x=(m+n)/2$, $y=(m-n)/2$. The solution is unique (except for swapping $x$ and $y$, and that's what you asked for), by the unique factorization theorem.

-
Should it instead be $f(x,y) = 2^{|x+y|} 3^{|x-y|}$? The question doesn't require that $x > 0$, $y > 0$, so your function may not output an integer. So then you would solve $|x+y| = m$, $|x-y| = n$. Or maybe I'm overcomplicating this... – Nicholas Stull Apr 22 '12 at 3:46
@Nicholas, I assumed OP wanted $x$ and $y$ non-negative, but you are correct to point out that that wasn't included in the question. Your suggestion won't quite work, since $f(x,y)=f(-x,-y)$. – Gerry Myerson Apr 22 '12 at 3:49
you're right that my function wouldn't work. Maybe we could modify it: If $f(x,y) = 3^n / 2^m$, just multiply by $2$ until you get an integer, divide by 3 until you get $1$. You'll get the equations $x+y = -m$, $|x-y|=n$. Again, maybe I'm overlooking something, but this seems like it might be workable for the case where $x$, $y$ are just integers.. – Nicholas Stull Apr 22 '12 at 3:58
@Nicholas, OP has saved us some effort by editing in a non-negativity requirement. – Gerry Myerson Apr 22 '12 at 5:48
@Gerry: not yet, he's only specified that $N$ is non-negative ... :) – Théophile Apr 22 '12 at 15:13

How about this: let $f(x,y) = (2N+1)(x-y)^2 + (x+y)$. Then, since $0 \leq x+y \leq 2N$ (I'm assuming your integers are non-negative), you can easily extract the sum and difference of $x$ and $y$ by dividing by $2N+1$ and looking at the quotient and remainder.

-

You could use the Cantor pairing function, making the first argument max(X,Y) and the second min(X,Y). As described in the article, you can recover the two arguments, but you have thrown away the info of which is the greater.

-
Or even better, use a triangular-number inspired method to get a bijection between $\mathbb{N}$ and $\{ (x,y) \in \mathbb{N}^2 \mid x \leq y \}$. – Hurkyl Apr 22 '12 at 6:05