2

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?

Nico A
  • 4,934
  • 4
  • 23
  • 49
  • 2
    Well, assuming $a,b$ are integers $2^a,3^b$ stores them as a single number. Probably not the most efficient solution. – lulu Feb 16 '16 at 00:30
  • @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. – Nico A Feb 16 '16 at 00:31
  • What kind of numbers are these exactly? An answer for integers would be different from an answer for rational numbers. – Gregory Grant Feb 16 '16 at 00:32
  • @GregoryGrant I just updated my answer. They are integers. – Nico A Feb 16 '16 at 00:33
  • 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. – Gregory Grant Feb 16 '16 at 00:35
  • @GregoryGrant How can I get the decimal part of x using only those operations? – Nico A Feb 16 '16 at 00:55
  • I figured you could just get it by inspection. But I see it's a game where you have to recover it with those operations. I guess you don't have the floor function? – Gregory Grant Feb 16 '16 at 01:13

2 Answers2

5

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.

lhf
  • 216,483
  • 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. – Nico A Feb 16 '16 at 01:28
  • 1
    @TreFox, there is also the Cantor pairing function, which will allow a much wider range. – lhf Feb 16 '16 at 10:43
0

You didn't specify whether $x$ needed to be an integer. In order to avoid massive numbers in exponentation, we could take $$x=a+\frac{1}{b}$$ Since $a,b$ are integers, $a$ will just be the integer part of $x$ and $1/b$ will be the reciprocal part, which you should be able to computationally reciprocate and round to the nearest integer (again, if $b$ is too big this may lead to floating point errors but this should be much better than calculating $2^a$ or similar).

GossipM
  • 405
  • I realised that @Gregory Grant gave a simpler (and maybe more computationally intuitive) answer, but I'll leave this up since maybe the approach works better for what you want to calculate. – GossipM Jan 17 '21 at 08:35