MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## encoding n natural numbers into one and back

Hello, I want to encode n natural numbers into one natural no. Also I should be able to decode it back. I tried Gödel's encoding scheme, but it takes a lot of space[doesen't fit into a double] and requires a lot of computation.Is there a better scheme?

-
By what standard are you going to measure 'better'? A random guess on my uneducated behalf hints to me that given any bounded set of $n$ numbers (say by $2^K$, $n$ arbitrary), the complexity of encoding these as a single number will probably escape the bound. What if you are trying to encode $2^K -n-1, 2^k - n ,\ldots, 2^K - 1$? – David Roberts Jul 1 2011 at 10:46
A trivial counting argument tells you that it is impossible to encode $n$ $m$-bit integers into less than $nm$ bits. Anyway, this does not look like research-level math question, see the faq. – Emil Jeřábek Jul 1 2011 at 10:48
I do not understand why this question was downvoted. I find an interesting question whose answer can be useful for programming. – Roland Bacher Jul 1 2011 at 16:23
Without more restrictions, this doesn't seem to be a research level mathematics problem. In addition, this question could be rewritten to be much clearer and to be informative. I can immediately think of several encoding schemes, but I don't know what Gödel's encoding scheme was for $\mathbb{N}^n$, or exactly why that was unsatisfactory. If you want such an encoding scheme for programming, you may want additional properties such as that the usual operations (e.g., addition, comparison) on the results have some meaning on the decoded number, at least for some restricted set of inputs. – Douglas Zare Jul 1 2011 at 17:16

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.

-
That's cute! But in practice, if you have a permanent restriction to 64 bits, and $n=4$, you probably may as well use my scheme (below) with $B = 2^{16}$. It's worth mentioning that, with that value of $B$, you can rapidly encode and decode using binary shift operations. – James Cranch Jul 1 2011 at 12:38
We might as well add where this is coming from geometrically. For $n = 2$, it's the inverse of the usual enumeration of $\mathbb{N}^2$ where one skims along diagonals parallel to $x+y = 0$ in succession, and the starting point on each diagonal is on the $x$-axis. Similarly, for $n=3$, it's inverse to an enumeration which proceeds by filling out each successive triangle parallel to $x+y+z = 0$. – Todd Trimble Jul 1 2011 at 16:27
(Well, I guess Neil pretty much said that in different words.) – Todd Trimble Jul 1 2011 at 16:29

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.

-

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

-
 This is the type of optimized encodings I had in mind with better informations about the type of (finite) sequences to encode. I remember an atari computer where the pointers were 32 bits... but only 24 of them were used to jump, so the eight others were used to pass a little more data to the functions :-) – Julien Puydt Jul 1 2011 at 13:32

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.

-

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.

-