Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
2  
@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

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
    
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?

share|improve this answer
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.