# The inverse of a certain tricky function

What is the explicit form of the inverse of the function $f:\mathbb{Z}^+\times\mathbb{Z}^+\rightarrow\mathbb{Z}^+$ where $$f(i,j)=\frac{(i+j-2)(i+j-1)}{2}+i?$$

-
Does you $\mathbb Z^+$ include $0$? – Mariano Suárez-Alvarez Mar 3 '11 at 3:01
No. Zero is not included. – Henry B. Mar 3 '11 at 3:13
What is your motivation for inverting this function? – Abel Mar 3 '11 at 3:59
@Abel: It's just curiosity. I realize that the function, I mentioned, shows that the number of entries in an infinite grid are countable. Naturally,I wanted to see the inverse. However, when I tried to construct it, I realized it was more complicated than I thought. I wanted to see how to work this example. – Henry B. Mar 3 '11 at 4:06
@Henry: In that case, the key phrase is "pairing function". Your $f$ is a specific example of one, particularly, a "displacement" of Cantor's pairing function. Notice that you can apply it repeatedly in order to demonstrate the isomorphism between $\mathbb{N}^n$ and $\mathbb{N}$, for a natural $n$. In my opinion, it is conceptually easier to use Gödel numbering, based on the fundamental theorem of arithmetic, to "encode" an $n$-tuple of natural numbers into one. Lastly, keep in mind that one explicitly writes these functions in order to constructively demonstrate an isomorphism, which in ... – Abel Mar 3 '11 at 4:43

Let $i+j-2 = n$.

We have $f = 1 + 2 + 3 + \cdots + n + i$ with $1 \leq i \leq n+1$. Note that the constraint $1 \leq i \leq n+1$ forces $n$ to be the maximum possible $n$ such that the sum is strictly less than $f$.

Hence given $f$, find the maximum $n_{max}$ such that $$1 + 2 + 3 + \cdots + n_{max} < f \leq 1 + 2 + 3 + \cdots + n_{max} + (n_{max} + 1)$$ and now set $i = f - \frac{n_{max}(n_{max}+1)}{2}$ and $j = n_{max} + 2 - i$.

$n_{max}$ is given by $\left \lceil \frac{-1 + \sqrt{1 + 8f}}{2} - 1 \right \rceil$ which is obtained by solving $f = \frac{n(n+1)}{2}$ and taking the ceil of the positive root minus one. (since we want the sum to strictly smaller than $f$ as we need $i$ to be positive)

Hence, \begin{align} n_{max} & = & \left \lceil \frac{-3 + \sqrt{1 + 8f}}{2} \right \rceil\\\ i & = & f - \frac{n_{max}(n_{max}+1)}{2}\\\ j & = & n_{max} + 2 - i \end{align}

-
It looks like the final formula for the maximum n is in conflict with the one in the body of the text, the ceiling function has become a floor function. – Henry B. Mar 3 '11 at 6:00
@Henry: edit done – user17762 Mar 3 '11 at 6:33

Since your function seems to be Cantor's pairing function $p(x,y) = \frac{(x+y)(x+y+1)}{2} + y$ applied to $x= j-2, y = i$, and since the inverse of the pairing function is $p^{-1}(z) = (\frac{\lfloor \frac{\sqrt{8z+1}-1}{2} \rfloor^2 + 3\lfloor \frac{\sqrt{8z+1}-1}{2} \rfloor}{2}-z,z-\frac{\lfloor \frac{\sqrt{8z+1}-1}{2} \rfloor^2 + \lfloor \frac{\sqrt{8z+1}-1}{2} \rfloor}{2})$, the inverse of your function is: $f^{-1}(z)=(z-\frac{\lfloor \frac{\sqrt{8z+1}-1}{2} \rfloor^2 + \lfloor \frac{\sqrt{8z+1}-1}{2} \rfloor}{2},2+ \frac{\lfloor \frac{\sqrt{8z+1}-1}{2} \rfloor^2 + 3\lfloor \frac{\sqrt{8z+1}-1}{2} \rfloor}{2}-z)$, which can be a bit ugly. What is your motivation for inverting this function?

-
A minor correction though. The OP wants $i,j \in \mathbb{Z}^+$, so you need to make slight modifications to the answer. For instance, $z=1$ should give $(1,1)$ but your solution gives $(0,3)$ – user17762 Mar 3 '11 at 3:41
@Sivaram: You're probably right. I'm pretty sure that after some modification (probably replacing all instances of $\lfloor \frac{\sqrt{8z+1}-1}{2}\rfloor$ with $\lfloor \frac{\sqrt{8z+1}-3}{2}\rfloor$), one would obtain the desired inverse, ending up with your solution. – Abel Mar 3 '11 at 4:06