Produce unique number given two integers

Solution 1:

How about just $2^a+2^b$? This represents the binary number with $1$s at exactly the $a$-th and $b$-th positions if $a\ne b$, and a single $1$ at the $(a+1)$-th position if $a=b$.

Solution 2:

If we restrict $a,b$ to be non-negative integers, we can try $f(a,b) = \dfrac{\max(a,b)(\max(a,b)+1)}{2}+\min(a,b)$.

This satisfies $f(a,b) = f(b,a)$ and grows quadratically with $\max(a,b)$. To help you see the pattern:

$f(0,0) = 0$,

$f(1,0) = 1$, $f(1,1) = 2$,

$f(2,0) = 3$, $f(2,1) = 4$, $f(2,2) = 5$,

$f(3,0) = 6$, $f(3,1) = 7$, $f(3,2) = 8$, $f(3,3) = 9$,

...

If you want to allow any integers $a,b$ then let $g$ be your favorite bijection from $\mathbb{Z}$ to $\mathbb{N}_0$, then let $f(a,b) = \dfrac{\max(g(a),g(b))(\max(g(a),g(b))+1)}{2}+\min(g(a),g(b))$.

One such bijection is $g(n) = \begin{cases} -2n & n \le 0 \\ 2n-1 & n \ge 1\end{cases}$.

Solution 3:

I think $a\circ b=(2^a+1)(2^b+1)$ works, if I understand correctly. $a \circ b = b \circ a$ and $a$ and $b$ can be found (up to permutation) from $(2^a+1)(2^b+1)$ (assuming $a$ and $b$ are integers.)

Solution 4:

Peter Woolfitt's suggestion ($2^a + 2^b$) is the simplest so far, but it becomes extremely large for quite small values of $a$ and $b$. For a more manageable function, I suggest interleaving the binary representations of $a$ and $b$. Then the result will be no larger than $\max(a,b)^2$.

To make it commutative ($f(a,b)=f(b,a)$), you will first have to swap $a$ and $b$ if $a< b$. Then it goes something like this:

f := 1
while a != 0 or b != 0
    // Incorporate bottom bit of a
    f := 2 * f
    if a is odd then f := f + 1
    a := a/2 // Discard bottom bit of a

    // Incorporate bottom bit of b
    f := 2 * f
    if b is odd then f := f + 1
    b := b/2 // Discard bottom bit of b
wend

Solution 5:

Note: This answer is substantially the same as the one given by JimmyK4542. I am leaving it here in case some minor difference in wording helps someone understand the derivation.

If we can additionally assume that the integers are nonnegative, I believe that the following will satisfy the conditions given.

First note that commutativity can be guaranteed by sorting the elements, so without loss of generality we assume $a \geq b$. Call the given pair which has been sorted $(a_0, b_0)$. We can identify the following sequence which uniquely transforms a sorted pair $(a,b)$:

\begin{aligned} (0,0) &\rightarrow 0 \\ (1,0) &\rightarrow 1 \\ (1,1) &\rightarrow 2 \\ (2,0) &\rightarrow 3 \\ (2,1) &\rightarrow 4 \\ (2,2) &\rightarrow 5 \\ &\vdots \end{aligned}

From this it is clear that if we can compute the number of elements in this sequence which have $a < a_0$, and then add $b_0$, we have an answer that works. Let \begin{equation} N(k) = \sum_{n=0}^{k}{n} = (k)(k+1)/2 \end{equation}

Then we have a mapping \begin{equation} (a \, \& \, b) \rightarrow N(max(a,b))+min(a,b) \end{equation} which satisfies the two properties given.

As a benefit, this answer also scales only quadratically with the largest number in the pair.