Are there nice inverse functions for the diagonal indexing function $x + (x + y) (1 + x + y) / 2$?

52 Views Asked by At

I've been trying to work out nice inverse functions for the x and y coordinate parts of the diagonal indexing function $$I(x,y) = x + \frac{(x + y) (1 + x + y)}{2},$$ which produces the table $$\begin{array}{c|cccc} y \backslash x & 0 & 1 & 2 & 3 \\ \hline 0 & 0 & 2 & 5 & 9 & \\ 1 & 1 & 4 & 8 & 13 & \cdots\\ 2 & 3 & 7 & 12 & 18 \\ 3 & 6 & 11 & 17 & 24 \\ && \vdots \end{array}$$

I want two inverse functions, call them $K_x$ and $K_y$, which take the above numbers and reverse the transformation, for example $K_x(3) = 0$, $K_x(8) = 2$, $K_y(8) = 1$.

I have come up with some which work, but they are not very nice functions. Let $$T(k) = k (k + 1)/2 \qquad (\text{the triangular numbers}) \\ T^{-1}_f(k) = \left\lfloor \frac{\sqrt{1 + 8 k} - 1}{2} \right\rfloor \\ T^{-1}_c(k) = \left\lceil \frac{\sqrt{1 + 8 k} - 1}{2} \right\rceil$$ then $$K_x(k) = k - T(T^{-1}_f(k)) \\ K_y(k) = T(T^{-1}_c(k + 1)) - k - 1.$$

Now, these functions work, but I find them somewhat ugly. We want to find which triangular number are below and above our number. We do this by taking the inverse triangular number, which requires a square root, which comes out as an algebraic number when the input isn't triangular, so then we need to floor/ceiling.

My question is: is there a better way than this?

The solution doesn't have to be a closed form expression; an algorithm would be great (so long as it's more efficient than "try all the numbers in range"). But if they are nice, meaningful closed form expressions, then all the better.