Say we have two integers, $a$ and $b$. I need a way to combine these numbers into one unique number $x$, such that they can both be recovered from $x$ and no other numbers can be recovered from $x$ There are plenty of ways to do this, but the problem is that I am using this for programming and I only have the following operators:

$+$ $-$ $\times$ $\div$ $a^x$ $\sqrt{}$

I also have sin and cos but I doubt those will be needed. Is it possible to encode and decode $a$ and $b$ using just these operators?

  • 2
    $\begingroup$ Well, assuming $a,b$ are integers $2^a\,3^b$ stores them as a single number. Probably not the most efficient solution. $\endgroup$ – lulu Feb 16 '16 at 0:30
  • $\begingroup$ @lulu Yeah, as you said, I need to be doing this calculation a lot so finding the prime factors of a number each time would not be good. $\endgroup$ – TreFox Feb 16 '16 at 0:31
  • $\begingroup$ What kind of numbers are these exactly? An answer for integers would be different from an answer for rational numbers. $\endgroup$ – Gregory Grant Feb 16 '16 at 0:32
  • $\begingroup$ @GregoryGrant I just updated my answer. They are integers. $\endgroup$ – TreFox Feb 16 '16 at 0:33
  • $\begingroup$ How about this. Why not just make a number $a.b$, put $b$ to the right of the decimal place and $a$ to the left. Or does $x$ also have to be an integer? If so you should state that. $\endgroup$ – Gregory Grant Feb 16 '16 at 0:35

Try $x=2^a (2b+1)$.

This relies on every integer being written uniquely as a power of $2$ times an odd number.

It is easy to recover $a$ and $b$: just divide $x$ by $2$ until you reach an odd number. Then $a$ is the number of divisions and $b$ is easily extracted from what is left.

However, if you need this for programming, then $a$ will be constrained to be quite small, if you use native numbers. In this context, the problem cannot be solved in full generality because you cannot compress all $2n$-bit strings into $n$-bit strings injectively.

  • $\begingroup$ Thanks! Yeah, my main concern with this is that I have no idea what the range of the numbers will be, and if they will be too big, and also I'm going to have to calculate this multiple times in a second, so repeated division might not be very efficient. $\endgroup$ – TreFox Feb 16 '16 at 1:28
  • $\begingroup$ @TreFox, there is also the Cantor pairing function, which will allow a much wider range. $\endgroup$ – lhf Feb 16 '16 at 10:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.