Pairing function that is linear in one of its arguments

Question

I'm looking for a pairing function ($f: \mathbb{N}^2 \rightarrow \mathbb{N})$ which is linear in one of its arguments. That is to say it takes $(x,y)$ to some function $ax+b$ where $a$ and $b$ are determined by $y$. Any ideas?

Answer 1

The mapping $$\pi : \mathbb{N}_{\geq 0}^2 \longrightarrow \mathbb{N}_{\geq 0} ~~~;~~~ (x,y) \longmapsto 2^{y+1}x + (2^y -1)$$ will do the job.

Written differently, we have $$ \pi(x,y) = 2^y (2x + 1) -1 $$ which makes it easier to see that $\pi$ has an inverse: For a given number $n \in \mathbb{N}_{\geq 0}$ you count the number of times you can divide $(n+1)$ by two, which gives you $y$. After these divisions you are left with an odd number, which can be written as $2m+1$, telling you that $x = m$. Formally: $$ y= \max\Big\{~ k \in \mathbb{N}_{\geq 0} ~~\Big\vert~~ \frac{n+1}{2^k} \in \mathbb{N} ~\Big\} ~~~,~~~ x = \frac{1}{2} \Big(\frac{n+1}{2^y} - 1 \Big) $$