Skip to main content
Better answer hopefully
Source Link
Julien Puydt
  • 2.1k
  • 1
  • 22
  • 23

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.

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.

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.

Source Link
Julien Puydt
  • 2.1k
  • 1
  • 22
  • 23

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.