Convert a Pair of Integers to a Integer, Optimally?

Question

What's the best algorithm that takes in two positive integers $a,b$ and returns a positive integer $c$, such that all $c$'s are unique and $(a,b)$ is distinguishable from $(b,a)$; where the best means that the length of $c$ in terms of digits is shortest possible, on average?

This implies that we can work out $a,b$ from $c$ with the same algorithm. (reversing it)

If we have a bound $x$ such that $a,b\le x$, then $f(a,b)$ has $x^2$ unique values which means our $c$ needs to take values from $[1,x^2]$ to have the least amount of digits, which can be achieved with the following function:

$$f(a,b)=(a-1)x+b$$

If $x$ does not exist, what's the optimal algorithm then?

(To make sense which algorithm is the shortest, I was comparing the length of the $c$ with the sum of lengths of $a,b$ and calculating the average which is more precise the more values we consider.)

---

I had two ideas so far;

$(1)$ Factorization

Take the factors of $a$ and $b$. Now you can use the second longest sequence of $0$s as a separator between factors, and the longest sequence of $0$s as a separator between the factors of the two numbers.

Example: $f(123,1007)=(3\times41 ),( 19\times53)=30410019053$

Example: $f(30,1006)=(2\times3\times5),(2\times503)=2003005000200503$

But this can be optimized, for cases such as $f(2^{64},3^{64})$, and even then, seems like it is too much extra digits.

$(2)$ Trailing zeroes

Take $a$, reverse its digits and put a random digit in front of the first digit. That way, the result does not have trailing zeroes. Then use the longest sequence of $0$s as a separator from $b$.

Example: $f(123,456)=93210456$

Example: $f(123,10100)=932100010100$

Example: $f(420,314)=902400314$

This also has room for optimization if we look at individual cases and add more specific rules. But it feels like it won't be optimal even then.

I suppose the optimal solution would need to look at couple or more cases individually?

Answer 1

One possibility is $$f(a,b) = \frac12 (a+b-2)(a+b-1) + a$$ which basically sort the points $(a,b) \in \mathbb{Z}_{+}^2$ first by $a+b$ and then by $a$.

$$\begin{bmatrix} f(1,1) & f(1,2) & f(1,3) &\cdots\\ f(2,1) & f(2,2) & f(2,3) &\cdots\\ f(3,1) & f(3,2) & f(3,3) & \cdots\\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} = \begin{bmatrix} 1 & 2 & 4 & \cdots\\ 3 & 5 & 8 & \cdots\\ 6 & 9 & 13 & \cdots\\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} $$ It is not that hard to work out the inverse of $f(a,b)$. I will leave the fun for you.

Answer 2

The Cantor pairing function covers the non-negative integers nicely. As a bijection, it uses all the target values for $f(a,b)$, so you can't get more efficient than that. The value of the pairing function is roughly $\frac 12(a+b)^2$. To handle integers, you can just compose it with a bijection between the integers and the naturals: $$g(n)=\begin {cases} 2n& n \ge 0\\-2n-1 & n \lt 0 \end {cases}$$ then use the pairing function on the resulting naturals.

Answer 3

Here's something that should do the trick: Given $a$ and $b$, let $h$ be the number of digits in $a$, $k$ be the number of digits in $b$, and $n=h+k$ the total number of digits. First write down $n$, then $h$, then $n$ $0$'s, then $k$, then $a$, then $b$. For example

$$f(13,47)=42000021347\quad\text{while}\quad f(134,7)=43000011347$$

To get from $c$ back to $(a,b)$, count the number of digits in $c$, then peel off the largest number from the beginning that's less than that. E.g., from the $11$-digit number $42000021347$, you get $4$, not $42$. That tells you the concatenatation is $ab=1347$, leaving $200002$ to be the concatenation of the number of digits in $a$ and $b$ individually, with $4$ $0$'s in between.

You can probably get by with fewer than $n$ $0$'s. My first attempt didn't have any at all, e.g., $g(13,47)=4221347$, but then I realized you can run into ambiguities, such as

$$g(12345678910,1)=g(1,23456789101)=12111123456789101)$$

where it's not clear if $12=11+1$ or $1+11$.

Answer 4

We need symmetricity for $(a,b)=(b,a)$. One way could be to store binary $a+b,a\oplus b$ that is inclusive and exclusive or of bits. Those are both symmetric. If we need to map to base 10 we can first do convert to binary coded decimal.

Can someone help me prove it works? Should be doable by a small logic table showing that any combination of or and xor only gives one possible combination a and b.