How would you reverse this double-variable equation?

Question

So I have an example function:

$$f(a,b) = \frac 12 ((a+b)^2 + 3a + b)$$

It "encodes" two variables into one unique number.

Assuming a and b are always positive, how would you write a function to find two input variables of the "encoding" function? So basically, how would you write a function to "decode" the output of that "encoding" function?

Answer 1

Let $\mathbb N_0=\{0,1,2,\ldots\}$ and $\mathbb N=\{1,2,3,\ldots\}$.

The mapping $(a,b)\mapsto f(a,b)$ is a bijection from $\mathbb N_0\times\mathbb N_0$ to $\mathbb N_0$. Hence it is also a bijection from $\mathbb N\times\mathbb N$ to $\mathbb N\setminus D$ where $D=\left\{\frac12n(n+i)\mid n\in\mathbb N,i\in\{1,3\}\right\}$ collects the images $f(a,0)=\frac12a(a+3)$ and $f(0,b)=\frac12b(b+1)$ for $a$ and $b$ in $\mathbb N$.

To see this and how to reconstruct $(a,b)$ from $f(a,b)$, assume that $a$ and $b$ are nonnegative and call $s$ the largest integer $k$ such that $k^2\leqslant2f$, which can also be defined by the inequalities $$ s^2\leqslant2f\leqslant s(s+2). $$ Note that $2f=(a+b)^2+3a+b$ implies $(a+b)^2\leqslant2f\lt(a+b+2)^2$ hence $s=a+b$ or $s=a+b+1$.

Case $s=a+b$: this means that $2f\leqslant(a+b)(a+b+2)$, that is, $3a+b\leqslant2a+2b$, that is, $a\leqslant b$. Then, $a+b=s$ and $3a+b=2f-s^2$ hence $a=f-\frac12s(s+1)$ and $b=\frac12s(s+3)-f$. Then the condition $a\leqslant b$ holds and $a$ and $b$ are indeed integers.

Case $s=a+b+1$: this means that $2f\geqslant(a+b+1)^2$, that is, $3a+b\geqslant2a+2b+1$, that is, $a\geqslant b+1$. Then, $a+b+1=s$ and $3a+b=2f-(s-1)^2$ hence $a=f-\frac12s(s-1)$ and $b=\frac12s(s+1)-f-1$. Then the condition $a\geqslant b+1$ holds and $a$ and $b$ are indeed integers.

The first case applies when $s(s+1)\leqslant2f\leqslant s(s+2)$, the second when $s^2\leqslant 2f\lt s(s+1)$. To sum up:

For every integer $f\geqslant0$, let $s$ denote the unique integer such that $s^2\leqslant2f\leqslant s^2+2s$.

• If $s^2\leqslant 2f\leqslant s^2+s-1$, then $a=f-\frac12s(s-1)$ and $b=\frac12s(s+1)-f-1$ (additionally, in this case $a\geqslant b+1$).
• If $s^2+s\leqslant2f\leqslant s^2+2s$, then $a=f-\frac12s(s+1)$ and $b=\frac12s(s+3)-f$ (additionally, in this case $a\leqslant b$).

Exemple: If $f=15123$ as in a comment, then $2f=30246$, $s=173$, $s^2+s=30102$, $2f\geqslant s^2+s$ hence we apply the second item above, which yields $a=15123-\frac12\cdot173\cdot174=72$ and $b=\frac12\cdot173\cdot176-15123=101$.

Answer 2

Inverting a function isn't always possible, because $f$ might not be one-to-one (that is, if $f(a,b)=f(c,d)$, then it isn't always the case that $(a,b)=(c,d)$). For your example function, notice that: $$ f(1,0)=2=f(-4,7) $$ so if the output is $2$, which input do we want: $(1,0)$ or $(-4,7)$?

Answer 3

For posterity, here's my sketch that $f(a, b) = (1/2)\bigl((a + b)^2 + 3a + b\bigr)$ is injective on the set of pairs of positive integers and the image consists of all integers greater than or equal to $4$ that are neither triangular nor one less than triangular. (This conclusion duplicates Did's answer.)

Throughout, $a$ and $b$ denote (arbitrary) positive integers. Easy calculations show that $$f(a+1, b-1) = f(a, b) + 1,\qquad f(1, a+1) = f(a, 1) + 3.$$ In words, $f$ takes consecutive integer values on the "anti-diagonal segment" $(1, a), (2, a-1), \dots, (a, 1)$, and "the lowest value on the next segment skips two consecutive integers". An easy induction shows the omitted values are the triangular numbers (starting with $6$) and their predecessors.