The inverse of a certain tricky function

Question

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?$$

Answer 1

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

Answer 2

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?