I want to encode $n$ natural numbers into one natural number. Also, I should be able to decode it back. I tried Gödel's encoding scheme, but it takes a lot of space (doesn't fit into a double) and requires a lot of computation. Is there a better scheme?
Thanks in advance.
One can give an explicit bijection $f_n:\mathbb{N}^n\to\mathbb{N}$. In the case $n=4$ it is $$ f_4(p,q,r,s) = \left(\begin{matrix} p+q+r+s+3 \\\\ 4\end{matrix}\right)+ \left(\begin{matrix} p+q+r+2 \\\\ 3\end{matrix}\right)+ \left(\begin{matrix} p+q+1 \\\\ 2\end{matrix}\right)+p $$ The general case follows the obvious pattern. We can order $\mathbb{N}^n$ as follows: if $a_1+\dotsb+a_n\lt b_1+\dotsb+b_n$ we declare that $a\lt b$, but if we have a tie according to this test then we instead compare $a_1+\dotsb+a_{n-1}$ with $b_1+\dotsb+b_{n-1}$, and so on. Then $f_n(a)=|\{b\in\mathbb{N}^n:b \lt a\}|$. To find $f_4^{-1}(k)$ you first find the largest $u$ such that $\left(\begin{matrix}u+3\\\\ 4\end{matrix}\right)\leq k$, then the largest $v$ such that $\left(\begin{matrix}u+3\\\\ 4\end{matrix}\right)+ \left(\begin{matrix}v+2\\\\ 3\end{matrix}\right)\leq k$, and so on. This is not quite as good as a formula but at least it is a fairly straightforward algorithm. One can check that $f_4(p,q,r,s)<2^{64}$ provided that $p+q+r+s\lt 145053$, so 64 bit integers are enough for a reasonable range of values.
I'd just like to point out that more than one of the answers above can be viewed as follows. The problem becomes easy if, instead of working with natural numbers, you work with finite strings over some fixed alphabet. To code a finite sequence of strings, just concatenate them, inserting some punctuation to show where one string ends and the next begins (or assuming some a priori information on the input that can determine the break points without punctuation). To solve the problem for natural numbers rather than strings, identify numbers with strings in one of the well-known ways, for example the standard expansion in some base $b$. The counting argument mentioned in some previous answers shows that you can't do significantly better than this. (In some cases you can do a little better by being clever about the punctuation.) In particular, Snark's interpretation of the question, asking for even a single integer to be compressed by coding, is implausible.
There is a series of good answers on StackOverflow and Quora, where I learned these go by the name pairing functions (related to dovetailing in computer science), can be generalized to any infinite sets, and iterated to encode arbitrary-length tuples as @Hugo illustrates.
In particular Szudzik's function is relatively efficient in computation and representation:
$$ ElegantPair (x, y) = \begin{cases} y^2 + x & x \neq max(x, y)\\ x^2 + x + y & x = max(x, y)\\ \end{cases} $$
and its inverse:
$$ ElegantUnpair (z) = \begin{cases} (z - \lfloor{\sqrt{z}}\rfloor^2, \lfloor{\sqrt{z}}\rfloor) & z - \lfloor{\sqrt{z}}\rfloor^2 < \lfloor{\sqrt{z}}\rfloor\\ (\lfloor{\sqrt{z}}\rfloor, z - \lfloor{\sqrt{z}}\rfloor^2 - \lfloor{\sqrt{z}}\rfloor) & z - \lfloor{\sqrt{z}}\rfloor^2 \geq \lfloor{\sqrt{z}}\rfloor\\ \end{cases} $$
Which looks like this:
Imagine the sequence of numbers that covers the two dimensional grid as follows:
This gives you a very simple and compact way of encoding two numbers into one. Suppose that $a$ is the row, $b$ is the column and $N$ is the cell value at coordinates $(a,b)$.
You can easily verify that the encoding formula is just:
$$ N = \frac{(a+b)^2 + 3a + b}{2} $$
And the decoding, given $N$, is given by:
$$ s = \lfloor{\sqrt{2N}}\rfloor $$
$$ a = \frac{2N - s^2 - s}{2} $$ $$ b = s - a $$
Where $s$ is just an auxiliary variable, for conveniency, and $\lfloor \rfloor$ is the floor operator, that keeps only the integer part of a real number.
Now, you can extend this idea recursively. If you want to encode 3 numbers, encode the first with the second, and then encode the result with the third, to obtain a single integer. The same generalizes to k numbers. Just keep on going.
To decode you apply a similar reasoning. If you know that you expect k numbers, perform the decoding k-1 times, successively.
To a finite set $A\subset\mathbb{N}$ assign the natural number $\sum_{a\in A}2^a$. This map is bijective and requires little computation.
Of course this method is only good when the numbers to encode are different. If you want to encode a finite sequence of natural numbers into one, then I suggest the following. Write each number dyadically and and change the leading "1" into a "2". Then concatenate these strings and interpret the resulting sequence of digits 0,1,2 in base 3.
If you want to encode $n$ natural numbers $a_1,\ldots,a_n$, with $0\leq a_i < B$, then encode it as $a_1 + a_2B + \cdots + a_nB^{n-1}$.
I'm not sure GH's answer is what was asked : as I understand it, the question is about an injection $\mathbb N^n\rightarrow\mathbb N$ for $n\geq2$.
The easy way is to note $p_1,\dots,p_n$ the first $n$ prime numbers and consider : $(d_1,\dots,d_n)\mapsto p_1^{d_1}\dots p_n^{d_n}$. Decoding is pretty easy in this case because you have to factor an integer knowing the prime numbers which appear.
EDIT: as I (and EJ 17 seconds before me) noted, this doesn't answer the question. So let me try another answer : generally no, it isn't possible to do better ; there's a definite limit of information you can encode in a given number of bits. But in more specific contexts, it is possible to do much better : for example for a pair of integers of the form $(m, m+1)$, you can get away with the same size to encode the pair as encoding $m$! So if you give us more specifics on the tuples you want to encode, then you'll get more interesting answers.
What about Morton numbers ? They are obtained by interleaving the bits of one or more source numbers. If your source numbers are sufficiently small you can decode it back.
