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.

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?

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

3 Answers 3

up vote 3 down vote accepted

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

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

share|improve this answer
    
What if the two input values are always positive and anything with a negative number is an extraneous solution, could you "decode" from there? –  jocopa3 Jul 20 '13 at 10:59

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.

share|improve this answer

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.