# Easily computable function that is one-to-one and onto with 2 or more inputs

I am looking for a function that will take take n inputs and have 1 output, and knowing the 1 output and function you can get back the n inputs, without error and computationally easy in both directions.

For example, the smallest natural number solution to a linear diophantine equation.

ax + by = c

Where x and y are some numbers, likes just say 3 and 5.

304923049049*3 + 2049823483230*5 = 11163886563297

Now given 11163886563297, we can solve

a*3 + b*5 = 11163886563297

This has infinite many solutions to it, but only 1 of them is "smallest". My limited understanding is that finding the smallest solution to a linear diophantine equation is not computationally easy, and has to be done by bruteforce. ( I also think the smallest solution is not even the numbers I picked, bad example but I think you get the point)

My hope is that the function is super fast to calculate both way computationally, and allow for many inputs. Like 100 inputs and get 1 output and from the 1 output get back the 100 inputs.

I understand it probably doesn't exist, but I am looking for good candidates, even some which seem to be the case but havent been proven they are accurate or inaccurate.

• Maybe the Cantor pairing function (please see Wikipedia) can serve as a basis. If we combine pairs in parallel it might be acceptably fast. But simple interleaving, though cruder, will likely be far more efficient. – André Nicolas Jun 11 '15 at 5:42
• Something reasonably close, but not onto, is to send your $n$ arguments $(a_1,a_2,...,a_n)$ to $2^{a_1}3^{a_2}...p_n^{a_n}$, where $p_n$ is the $n$th prime. Factorization in general is slow, of course, but here we know which factors we want, so the inverse operation just becomes an integer division a linear number of times in the sum of the arguments on the left hand side, or at most $\log_2$ times on the right hand side. – Kevin Arlin Jun 11 '15 at 6:14
• Andre please post cantor/interleaving as an answer so I may mark it. – ParoX Jul 14 '15 at 4:21

## 1 Answer

This question is very related to: https://stackoverflow.com/questions/919612/mapping-two-integers-to-one-in-a-unique-and-deterministic-way

In which @nawfal posts this link: http://szudzik.com/ElegantPairing.pdf which the pairing function is as space-efficient as possible .