Finding inverses of a function which maps ordered pairs of positive integers onto the positive integers.

Question

The function $f(x,y) = \frac{(x+y-1)(x+y-2)}{2} + y $ is a bijection which maps ordered pairs of positive integers onto the positive integers. I would like to find the functions $g$ and $h$ such that $g(f(x,y)) = x$ and $h(f(x,y)) = y$.

Through examination of a table of values, I noticed that if $t$ is the largest triangular number less than $f(x,y)$ then $f(x,y) - t = y$, and if $T$ is the smallest triangular number greater than or equal to $f(x,y)$ then $T - f(x,y) + 1 = x$. This would reduce the original problem to finding functions for $t$ and $T$, but I am not sure if this is possible.

Any tips/hints would be very appreciated! I am also curious about more generic/algebraic approaches to this type of a problem.

Answer 1

$f(x,y) = \frac{(x+y-1)(x+y-2)}{2} + y = \frac{(x+y)^2-3(x+y)+2}{2} + y = \frac{u^2-3u+2}{2} + y =g(u, y) $ where $u = x+y$.

Since $1 \le y \le u-1$, $1+\frac{u^2-3u+2}{2} \le g(u, y) \le u-1+\frac{u^2-3u+2}{2} $. Therefore $g(u, y) \le \frac{u^2-3u+2+2(u-1)}{2} = \frac{u^2-u}{2} $ and $g(u+1, y) \ge 1+\frac{(u+1)^2-3(u+1)+2}{2} = \frac{u^2+2u+2-3u-3+2+1}{2} = \frac{u^2-u+2}{2} = \frac{u^2-u}{2}+1 $.

Therefore $g(u+1, 1) =g(u, u-1)+1 $, so there is no overlap in the $g$ values between $u$ and $u+1$.

So, for any particular index $n$, find the unique $u$ such that $\frac{u^2-u}{2}+1 \le n \le \frac{u^2-u}{2}+u-1 $. Then $x+y = u$, $y = n-u$, and $x=u-y$.

To find $u$ from $n$:

From the first inequality, $u^2-u \le 2n-2$ or $4u^2-4u+1 \le 8n-7$ or $2u-1 \le \sqrt{8n-7}$ or $u \le 1+\frac12\sqrt{8n-7}$, or $u \le 1+\lfloor\frac12\sqrt{8n-7}\rfloor$.

From the second inequality $n \le \frac{u^2-u}{2}+u-1$ or $8n \le 4u^2-4u+8u-8 =4u^2+4u-8 =4u^2+4u+1-9 $ or $8n+9 \ge (2u+1)^2$, or $2u+1 \ge \sqrt{8n+1}$, or $u \ge \frac12(\sqrt{8n+1}-1)$, or $u \ge \lceil\frac12(\sqrt{8n+1}-1)\rceil$.

Answer 2

As we have freedom to choose $y$ why don't we choose the biggest $n$ s.t. $\frac{n(n+1)}{2}\lt f(x,y)$ and choose $y = f(x,y)- \frac{n(n+1)}{2}$, by construction $y\gt 0$, let's prove there exists $x \in \mathbb{N}$ for this $y$ satisfying the equation.
From construction we know that $\frac{(n+1)(n+2)}{2} \ge f(x,y)$. Then $ y \le \frac{(n+1)(n+2)}{2} - \frac{n(n+1)}{2}=n+1$, $n = x+y-2$ so if we plug this into inequality $y \le x+y-1 => x \ge 1$. Therefore, we have found desired $(x,y)$.
Now the question is how to find $n$. This is easier part, we can solve quadratic equation $n^2+n-2f(x,y)=0$, then take $p=\lfloor n1\rfloor$ of positive solution of the equation. $y = f(x,y) - \frac{p(p+1)}{2}$ and $x=p-y+2$.
If I am not mistaken in my calculations $p = \lfloor \frac{-1+\sqrt{1+8f(x,y)}}{2} \rfloor$

Answer 3

Based on the observation of tabulated values of $f(x,y) = \frac{(x+y−1)(x+y−2)}{2}+y$, $f(x,y)$ could be interpreted as the sum from $1$ to $u = x+y-2$ with an added $y$

$$f(x,y) = \frac{u(u+1)}{2}+y$$

That gives us $h(f(x,y)) = f(x,y) - \frac{u(u+1)}{2}$ when we solve for $y$.

For $g(f(x,y))$, substitute the last $y$ with $u-x+2$ and we get $g(f(x,y)) = \frac{u(u+1)}{2}+u-f(x,y)+2$ when we solve for $x$.

For any given $x$ and $y$, $\frac{u(u+1)}{2} \lt \frac{u(u+1)}{2}+y \le \frac{(u+1)(u+2)}{2}$ or $\frac{u(u+1)}{2} \lt f(x,y) \le \frac{(u+1)(u+2)}{2}$, which means if we solve for $u$ in $\frac{u(u+1)}{2} \lt f(x,y)$ and take the ceiling, we should end up with $u+1$ for all values of $x$ and $y$.

$$\frac{u(u+1)}{2} \lt f(x,y) => u \lt \sqrt{2f(x,y) + \frac{1}{4}} - \frac{1}{2} => u+1 = \lceil \sqrt{2f(x,y) + \frac{1}{4}} - \frac{1}{2} \rceil => u = \lceil \sqrt{2f(x,y) + \frac{1}{4}} - \frac{1}{2} \rceil -1$$

We now have $u$ in terms of $f(x,y)$ and can solve $g(f(x,y))$ and $h(f(x,y))$.