5
$\begingroup$

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

  • 0
    ... the end does not rely on the details of the construction. That is to say, we don't usually care whether these pairing functions have nice inverses in the sense of having a closed-form expression, but only about the existence of the function and its inverse.2011-03-03

2 Answers 2

5

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

  • 0
    @Henry: edit done2011-03-03
3

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?

  • 0
    @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.2011-03-03