# How would you reverse this double-variable equation?

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?

-
Clearly, two values of $a$ for a fixed $b$ will give us the same $f(a,b)$ –  lab bhattacharjee Jul 20 '13 at 10:02
I think it's necessary to prove first that $f:\mathbb N_+^2\to \mathbb N_+$ is bijective, which is not evident at the first sight. –  TZakrevskiy Jul 20 '13 at 11:30
Moreover, $f\ge 4$, so it's definitely not surjective (it's surjective on its image, though, but now we need to find this image). –  TZakrevskiy Jul 20 '13 at 11:38
Surprisingly (to me), $f$ is injective on $\mathbf{N} \times \mathbf{N}$, though not surjective; the image consists of all integers greater than or equal to $4$ that are neither triangular nor one less than triangular, i.e., not of the form $n(n+1)/2$ or $n(n+1)/2 - 1$ with $n \geq 3$. I don't have a formula to recover $(a, b)$ from $f(a, b)$, but it may help to express $f(a, b)$ in terms of the variables $u = a + b$ and $v = a - b$, namely, $f(a, b) = (1/2)\bigl((u+1)^2 + v - 1\bigr)$. –  user86418 Jul 20 '13 at 11:40
What if I put this into a different context. Instead of being just a function, pretend it is an "encrpytion algorithm," so that the phrase "Hello." turns into $f(72,101)+f(108,108)+f(111,46) = 15123+23544+12514 = 51181$ where the a and b values represent the decimal version of each character. Knowing it is possible to decode that number back into a phrase, how would you go about doing so? A more simple way to see it is "He" encodes into $f(72,101) = 15123$, how would you decode it back to (72,101) or "He" –  jocopa3 Jul 20 '13 at 12:04
show 1 more comment

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

-
Let's take $f=6$, then $s=3$, and by your formulas $(a,b)$ is either $(0,3)$ (which would give $f=9$) or $(1/2, 3/2)$, which is not a couple of integers. –  TZakrevskiy Jul 20 '13 at 12:57
@TZakrevskiy If $f=6$ then $s=3$ and $2f\geqslant s(s+1)$ hence the first case applies and gives $a=f-\frac12s(s+1)=0$, $b=\frac12s(s+3)-f=3$, which is correct. –  Did Jul 20 '13 at 13:08
Sorry, my bad, misplaced the coefficients at $a$ and $b$. –  TZakrevskiy Jul 20 '13 at 13:14
@TZakrevskiy No problem (and this might be my fault since a previous version of my answer had misprints). –  Did Jul 20 '13 at 13:15
I noticed $s = floor(sqrt(2f))$, so that would take out having to know $a$ and $b$. (Sorry for bad formating, not used to StackExchange's formatting system). –  jocopa3 Jul 20 '13 at 13:34
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)$?
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.