# Produce unique number given two integers

Given two integers, $a$ and $b$, I need an operation to produce a third number $c$. This number does not have to be an integer. The restrictions are as follows:

1. $c$ must be unique for the inputs (but it does not have to be reversible).
2. $a$ and $b$ must be interchangeable ($a$ & $b$ = $b$ & $a$)

Initially, the first thing I thought of was simply $a+b$, however naturally that does not fit restriction 1. Then I considered a hash function of some sort, but that doesn't fit 2.

Any thoughts?

• What do you mean that doesn't fit 1, there is only one unique number which is the sum of a and b. – Adam Hughes Jul 30 '14 at 18:08
• I believe that the OP wants an injective operation from $\mathbb Z \times \mathbb Z$ to $\mathbb Z$ as condition 1, and for the operation to be commutative for condition 2. – qaphla Jul 30 '14 at 18:08
• @qaphla Almost, except it should be $2$-to-$1$, since $f(a, b) = f(b, a)$. – user61527 Jul 30 '14 at 18:09
• It's impossible to have such an injection from ordered pairs, but an injection from two-element subsets is fine, since then the 'commutativity' condition is implied -- $f(\{a,b\}) = f(\{b,a\})$. – qaphla Jul 30 '14 at 18:14
• I'd say that a commutative function on ordered pairs can be pretty clearly identified with a function on sets of size two, and the difference between the two isn't worth caring about. – qaphla Jul 30 '14 at 18:31

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}$.

• This is certainly the best solution so far from an implementation point of view. – lemon Jul 30 '14 at 20:18
• Great answer - I can see this being very useful. – Keith Jul 31 '14 at 4:01
• Additionally, if you wanted $f$ to take on negative values as well as positive values, you could define $$f(a, b) = g^{-1}\left(\dfrac{\max(g(a),g(b))(\max(g(a),g(b))+1)}{2}+\min(g(a),g(b))\right).$$ – Strants Jul 31 '14 at 4:09
• I should look to see if there is a $g$ that maps my answer to yours. – robjohn Aug 1 '14 at 15:51

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$.

• This is a better answer than mine. – deinst Jul 30 '14 at 18:28
• reversible? Using this method we get a and b from c. – mridul Jul 30 '14 at 19:08
• @mridul Any method we use is theoretically reversible (up to specifying which input is $a$ and which is $b$) because we have a uniqueness requirement - meaning from $f(a,b)$ we can extract the information $\{a,b\}$. – Peter Woolfitt Jul 30 '14 at 19:18
• If we're talking about a computer, this becomes trickier as soon as $a$ or $b$ get bigger than $64$... not a great range. – Jack M Jul 30 '14 at 20:30
• @JackM The goal of this answer was to give a nice mathematical solution to the problem regardless of practicalities. For a good way to actually solve the problem on a computer, please see the other answers - say TonyK's answer, or JimmyK4542's answer. – Peter Woolfitt Jul 30 '14 at 20:34

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.)

• Nice answer; especially since one can tell the original two numbers by glancing at the binary representation of the result. – Clinton Curry Jul 30 '14 at 18:19
• -1 Mathematically elegant but this isn't practical to implement into code for large $a$ and $b$. – lemon Jul 30 '14 at 18:21
• Who said anything about practicality for code? – deinst Jul 30 '14 at 18:23
• Finding a power of 2 modulo a prime is trivial. – deinst Jul 30 '14 at 18:35
• @ozo If that's what the OP wants, then he ought to ask a more specific question. This answer perfectly fits the requirements as stated. It's ridiculous to downvote someone for not reading the OP's mind or making unwarranted assumptions from the question. – Chris Hayes Jul 30 '14 at 19:05

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

• And what happens to the uppermost bits? It seems they get left out... – abiessu Jul 30 '14 at 18:42
• @abiessu: No, every bit gets inspected and incorporated. That's why a and b get divided by 2. – TonyK Jul 30 '14 at 18:44
• You're right, I mixed up my "negated input AND" logic and thought it would end prematurely. – abiessu Jul 30 '14 at 18:48
• Oh, no! You're right! That 'and' should be an 'or'. I have fixed it now. – TonyK Jul 30 '14 at 18:54
• @ozo: Yes, you are right. I have fixed that with f:=1 instead of f:=0; perhaps it works now... – TonyK Jul 30 '14 at 19:19

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 $$N(k) = \sum_{n=0}^{k}{n} = (k)(k+1)/2$$

Then we have a mapping $$(a \, \& \, b) \rightarrow N(max(a,b))+min(a,b)$$ which satisfies the two properties given.

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

• It appears that the answer by JimmyK4542 was posted while I was typing this up. What is the proper etiquette here (I'm new)? Should I delete my answer, being that it is basically the same? – Hunter Jul 30 '14 at 19:58
• The rule of thumb is: if you think that your explanation is clearer/more concise than someone else's then keep it. Otherwise, it's good etiquette to delete it. – lemon Jul 30 '14 at 20:20
• @Hunter There is not really a consensus on this issue of etiquette. Please see here and here for discussions on this topic. – Peter Woolfitt Jul 30 '14 at 20:46

More programmerly than mathily, use a nondigit separator, like the convenient decimal point. In this case I concat a string together then cast it to a float.

c = parseFloat(max(a,b) + '.' + min(a,b))


c will be unique and reversible for all interchangeable combinations of a and b.

so for example,

myhash(124,24) = 124.24
myhash(24,124) = 124.24

myhash(11231,26611) = 26611.11231


I think some index systems like the Dewey Decimal system and some part numbering schemes use this sort of bin-based technique.

But oops, then there is a problem if the second number ends with trailing zeros, so stringwise reverse it to preserve them:

c = parseFloat(max(a,b) + '.' + reverse(min(a,b)))


then

myhash(123,456) = 123.654
myhash(12300,4560) = 12300.0654

• Whoops, this won't handle negative integers very well. – Nathan Jul 30 '14 at 20:06
• Assuming $a$ and $b$ are of a similar size then this limits them each to about 3 significant figures (32-bit IEEE float) or 8 significant figures (64-bit IEEE float). – lemon Jul 30 '14 at 20:15
• You could encode the sign of min(a,b) in the first decimal digit (so for example myhash(2,1) = 2.01, myhash(2,-1) = 2.11). – hvd Jul 31 '14 at 12:24
• @ozo That assumes they'll be stored in an IEEE floating point variable. That's a problem for the programming aspect, but not for the maths aspect. – hvd Jul 31 '14 at 12:26

Sort a and b ,then apply hash function.

c=hash(sort(a,b))

Here,

1. c is unique for the inputs and not reversible.
2. a and b are interchangeable (a & b = b & a).
• All hash functions have collisions, multiple inputs with the same output. So this violates requirement 1. The probability of getting a collision for two randomly chosen inputs may be very low, and so not worth worrying about in practice, but it can theoretically happen. – David Z Jul 31 '14 at 0:10

Let $p$ and $q$ be distinct primes, and let

$$c=\min(p^aq^b,p^bq^a)$$

In fact this generalizes to a function for $n$ interchangeable variables $a_1,\ldots,a_n$, using distinct primes $p_1\ldots,p_n$:

$$c=\min_{\pi}\{\prod_{i=1}^np_i^{a_{\pi(i)}}\}$$

where the min is taken over all permutations of $\{1,\ldots,n\}$.

(Note, the integers $a$ and $b$ need not be positive. The Fundamental Theorem of Arithmetic still guarantees that different multisets correspond to different values of $c$.)

Well, there is a rather simple way to do this using string operations:

1. Let x = min(a,b) and y=max(a,b)
2. Treating x and y as strings and + as the concatenation operator, let z = x + "|" + y
3. Use your favorite string to binary/hex/decimal function to turn z into a number.

Let's look at an example. f(25,-36).

x = -36 and y = 25.

z = "-36|25".

Using a standard ASCII to Decimal converter, we get the number 4551541245053.

• I am trying to create combinations of a set of numbers in excel and thus realized that I need a function like the one mentioned in the main question of this thread. While I already tried 2^a + 2^b i realized it does not work for large a and b due to excel issues... but i Found some really great mathematical answers on this page and learnt a lot.. William Forcier from an excel point of view your answer is awesome. I made only 1 change...instead of converting the concatted text to a number I used a countifs and running countifs to weed out duplicates... Thank you very much for the base idea :) – RAVI D PARIKH Feb 10 '19 at 5:56

Given $\max(|a|,|b|)$ and $a+b$, we can recover the unordered pair $(a,b)$ as $$\textstyle\left(\min(a+b,0)+\max(|a|,|b|),\max(a+b,0)-\max(|a|,|b|)\right)\tag{1}$$ There are $4n+1$ unordered pairs of integers so that $\max(|a|,|b|)=n$; their sums being $$\{-2n,-2n+1,\dots,0,\dots2n-1,2n\}\tag{2}$$ Since $$\sum_{k=1}^n(4k+1)=2n^2+3n\tag{3}$$ we will set $$f(a,b)=2\max(|a|,|b|)^2+\max(|a|,|b|)+a+b\tag{4}$$ Then the greatest $f(a,b)$ can be for $\max(|a|,|b|)=n$ is $$2n^2+n+2n=2n^2+3n\tag{5}$$ and the least it can be for $\max(|a|,|b|)=n+1$ is $$2(n+1)^2+(n+1)-2(n+1)=2n^2+3n+1\tag{6}$$ Therefore, the $f$ given in $(4)$ maps unordered pairs of integers to non-negative integers injectively (and incidentally, surjectively).

• Beautiful. Looks like the best solution so far to me, since the OP apparently wants to use it as a perfect hashing function or something like that. -- There are parenthesis missing around $4k+1$ in (3). – user20796 Aug 1 '14 at 13:58
• @HansAdler: thanks. I can see your point about the parentheses, so I have added them. However, I usually write $1+\sum\limits_{k=1}^n4k$ when I intend the other association, just to be sure. – robjohn Aug 1 '14 at 15:59

If $P$ are all the primes, then:

$f(a,b) = P(a) P(b)$

f(0,0)=4
f(1,0)=6
f(1,1)=9
f(2,0)=10
f(2,1)=15
f(2,2)=25
f(3,0)=14
f(3,1)=21
f(3,2)=35
f(3,3)=49


$a$ & $b$ are interchangeable. It is reversible, but very hard for large numbers of c. I think this is also how asymmetric cryptography works in its most simple form with large numbers of '$a$' & '$b$'.

Example:

• 'P(a)' being the public-key on the server side
• 'P(b)' being the private-key on the client side
• 'c' being the token to be transmitted.

2. server transmits token to client and requests for a factor of it.
3. client divides token with the locally stored private-key and send the result to the server
4. Server compares stored public-key with given result, if same then grants access
• And it works also if you have more then 2 input variables. – Paul Verschoor Dec 9 '14 at 12:23

Since your answer need to be a integer the following simple steps should work:

1. Sort the numbers a and b with the smallest first if a = b just put a first.
2. Now put the first number in front of the dot and the second number behind the decimal, then append one to the end (so that if the second number ended in 0 it will now end in 01 to keep it unique)
3. now you have a unique easily reversible number.

This method will also be reasonably memory efficient, and also ensure uniqueness (and you can easily find a given b and b given a).

• I see two difficulties with this approach: 1) The result for numbers with trailing zeroes won't be unique (1.50 = 1.500) - this can be resolved by reversing the number behind the decimal point. 2) the question states "integers", how can this function be improved to handle negative integers while still being injective? – waldrumpus Jul 31 '14 at 8:51
• @waldrumpus, as TonyK observed when I asked much the same question of his answer, you could handle signs by encoding $a\le b$ as $ax.yr$, where $r$ is $b$ written in reverse (as you suggested) and $x,y\in\{0,1\}$ to indicate the signs of $a$ and $b$. – Barry Cipra Jul 31 '14 at 19:17
• added a simple trick just append 1 to the end and it will always be unique – Thijser Jul 31 '14 at 19:45
• @BarryCipra Very nice! Since this answer was the first thing to pop into my mind, I'm glad to see it improved and perfectly acceptable. – waldrumpus Aug 1 '14 at 7:51

Use complex numbers $u+vI$ with integer coefficients $u, v$. Let $c=a*b=(a+b)+abI$. It is easy to see that if we know $u=a+b$ and $v=ab$ then we know $a, b$. To see this consider the polynomial $x^2-ux+v$ then this has roots $a,b$.

If you want the answer to be real then you could use $(a+b)+(ab)\pi$

Yet another (and quite standard) solution is using the Cantor pairing function $\pi: \mathbb N\times\mathbb N\to \mathbb N$. It is a bijection. So now let's only find a bijection between unordered pairs ${\mathbb N}\choose{2}$ and ordered pairs $\mathbb N\times \mathbb N$. One such is $$\sigma:\{a,b\}\mapsto(\min\{a,b\},\max\{a,b\}-\min\{a,b\})$$ with the inverse $$\sigma^{-1}:(x,y)\mapsto \{x,x+y\}.$$

Therefore $\pi\circ\sigma$ satisfies your requirements, moreover, it is a bijection between unordered pairs of natural numbers and natural numbers, so it's efficient.

If you need integers instead of natural numbers, use your favourite bijection $\mathbb Z\to\mathbb N$, there's plenty of them.

Since some seem to be talking about programming and this is too long for a comment, I'll post this answer even though it's not really appropriate for a mathematics question. Given two 16 bit signed ints a and b, you can sort them and or them together. Meaning:

int uniqueCombo(int a, int b) { //assuming -2^15<=a,b<=2^15-1
if(a<b)
return (a&0xFFFF)|(b<<16);
else
return (b&0xFFFF)|(a<<16);
}


This, by the magic of signed and unsigned integers, unless I'm mistaken, will handle positives and negatives perfectly fine and is easy to invert (to get a as a 32 bit signed int, take out the first sixteen bits. If the biggest place digit is a one, pad the new 16 large place digits with ones. Else zeros.)