Inverting the Cantor pairing function

Solution 1:

Rather than follow the Wikipedia derivation, I’ve produced my own; it’s essentially the same, but I think that it may be a bit easier to follow.

Let $T_n=\binom{n+1}2=\sum_{k=1}^nk$, the $n$=th triangular number. We can write the pairing function as $$\langle x,y\rangle=\frac{(x+y)(x+y+1)}2+y=T_{x+y}+y\;,$$ making it clear that every $\langle x,y\rangle$ is of the form $T_n+k$ for some $n,k\in\Bbb N$ with $k\le n$.

Lemma. Every natural number has a unique decomposition of this form.

Proof. To prove existence, fix $m\in\Bbb N$, let $n\in\Bbb N$ be maximal such that $T_n\le m$, and let $k=m-T_n$. Then $T_n\le m<T_{n+1}$, so $k=m-T_n<T_{n+1}-T_n=n+1$, i.e., $k\le n$.

To prove uniqueness, suppose that $T_m+i=T_n+k$, where $i\le m$ and $k\le n$, and without loss of generality assume that $m\le n$. Then $$i+\sum_{j=1}^mj=k+\sum_{j=1}^nj\;,$$ so $$i-k=\sum_{j=m+1}^nj\;.\tag{1}$$ If $m<n$, this implies that $m>i-k\ge m+1$, so $m=n$, $i-k=0$, and $i=k$. $\dashv$

Inverting the pairing function is then simply a matter of calculating the unique $n$ and $k$ such that $z=T_n+k$ and $k\le n$: once $n$ and $k$ are known, just set $y=k$ and $x=n-k$.

From the proof of the lemma it’s clear that finding $n$ and $k$ boils down to finding the maximal $n$ such that $T_n\le z$, i.e., the unique $n$ such that

$$\frac12n(n+1)\le z<\frac12(n+1)(n+2)\tag{1}\;.$$

The first inequality in $(1)$ can be rewritten $n^2+n\le2z$, or $n^2+n-2z\le0$; over $\Bbb R$ this has the solution

$$\frac{-1-\sqrt{1+8z}}2\le n\le\frac{-1+\sqrt{1+8z}}2\tag{2}$$

from the quadratic formula. The first inequality in $(2)$ says nothing useful, since $n\ge 0$ anyway.

Similarly, the second inequality in $(1)$ becomes $n^2+3n+2-2z>0$, with the solution

$$n<\frac{-3-\sqrt{1+8z}}2\quad\text{or}\quad n>\frac{-3+\sqrt{1+8z}}2\;,\tag{3}$$

where the first alternative is plainly impossible. Combining the useful parts of $(2)$ and $(3)$, we see that

$$\frac{-3+\sqrt{1+8z}}2<n\le \frac{-1+\sqrt{1+8z}}2\;.\tag{4}$$

Let $$\alpha=\frac{-1+\sqrt{1+8z}}2\;;$$ then $(4)$ just says that $\alpha-1<n\le\alpha$, i.e., that $n$ is the unique integer in the range $(\alpha-1,\alpha]$ so that $n=\lfloor\alpha\rfloor$. (If that’s not immediately clear, note that from $\alpha-1<n$ we get $\alpha<n+1$, and we already have $n\le\alpha$.)

The computation of the inverse is now essentially complete. Given $z\in\Bbb N$, let

$$n=\left\lfloor\frac{-1+\sqrt{1+8z}}2\right\rfloor\;;$$

then $z=\langle x,y\rangle$, where $y=z-T_n=z-\frac12n(n+1)$ and $x=n-y$.

Solution 2:

In that Wikipedia article it is shown that inverse function to $$f(w)=\frac{w^2+w}2$$ is the function $$f^{-1}(t)=\frac{\sqrt{8t+1}-1}2.$$

These functions are strictly increasing on $[0,\infty)$.

So $$f(w)\le z<f(w+1)$$ implies $$w\le f^{-1}(z)<w+1,$$ which is what you wrote.

I'll add the link to the current revision of the Wikipedia article, so that this post makes sense even in the case the article is changed.