Mathematical function to convert two numbers into one?

Question

Is there a mathematical function that converts two numbers into one so that the two numbers can always be extracted again?

Answer 1

Consider the map $$(x, y)\to 2^x3^y$$ For example, $$(\color{blue}{7}, \color{green}{3})\mapsto 2^\color{blue}{7}3^\color{green}{3} = 128\cdot27 = 3456.$$

To extract the original two numbers, divide 3456 by 2 and count how many times you can do this before you are left with an odd number: $$3456 \to 1728\to 864\to 432\to 216\to108\to 54\to 27$$ That's $\color{blue}{7}$ times. Then divide 27 by 3 until you are left with 1: $$27\to9\to3\to 1$$ That's $\color{green}{3}$ times, so the original numbers were $\color{blue}{7}$ and $\color{green}{3}$.

Unlike the other answer in this thread, this works for any whole numbers, of unlimited size. But the process for extracting the original two numbers by this method is slow.

Answer 2

Computer programmers have to deal with this kind of problem all the time. Usually the problems they deal with are even more complicated: "take 3 lists of numbers of arbitrary length, and a description of a finite mapping from numbers to numbers, and 3 extra numbers, and turn them into a single number". The process of doing this is called serialization. Unsurprisingly, many different solutions are used, depending on the exact engineering details of the problem being solved.

For concreteness, we will suppose that numbers are always written in base-10 notation. (In the computer, they are most often stored and sent in a base-256 notation, but the principle is the same.)

First suppose we have two numbers, 1111 and 2222. We want to send them together. But if we send 11112222, the receiver won't know if this is $(1111,2222)$, as we intended, or $(11,112222)$ or $(1111222, 2)$ or even $(11,112,222)$.

There are three basic techniques we can use to fix this problem:

1. Restrict the size of the numbers. If we guarantee that all our numbers will be less than 1,000,000, say, then we can guarantee that every number we send is exactly six digits long, and send 001111002222. This unambiguously represents $(1111, 2222)$. It can't be $(111, 12222)$, because that would be sent as 000111012222. This is essentially the solution of Leox elsewhere in this thread. It is very commonly used when we can place an upper bound on the size of the numbers we want to send.

2. Sometimes we need to send unbounded numbers. We need a way to show where a number ends. We can do this by attaching a "terminator" to the end (or beginning) of each number. (A separator between each two numbers is exactly the same, except that the final terminator is omitted.)

   For example, to send $(1111, 2222)$ we actually send the number 1111.2222..

   But wait. 1111.2222. isn't a number! But it could be: we could understand it as a base-eleven number, where the . is the eleventh digit.

   Or alternatively, we could convert 1111 and 2222 to base 9 numerals, which never include the digit 9, and then use the digit 9 as a terminator. 1111 in base 9 is written 1464, and 2222 is written 3038, so we can send $(1111,2222)$ as 1464930389. The recipient gets the base-9 digits, splits them up at the 9's into 1464 and 3038, and then sees that hose represent the numbers 1111 and 2222. (In computer applications, converting a series of base-9 digits to a number is neither more nor less difficult than converting a series of base-10 digits.)

   To send $(111, 12222)$ instead, we send 1339176809, because 111 and 12222 in base 9 are 133 and 17680. To send $(11, 112, 222)$, we send 12913492669 because 11, 112, and 222 in base 9 are 12, 134, and 266.

   This may seem bizarre, but variations of it are actually quite common. In computer applications we need to send a sequence of base-256 "digits" where the digits are all between 0 and 255. Instead, we convert them to base-128 and send digits between 0 and 127, except the last one, which has 128 added to it, and is between 128 and 255 instead. This high value signals to the recipient that a new number is starting. Variations on this scheme appear in the commonly used ASN.1 standard and the UTF-8 encoding for Unicode codepoints. It has the advantage that you can pick up a partial sequence of data and understand most of what follows.

   In a variation on this scheme, we can continue to use regular base-10 numerals, but we adopt an "escape sequence" scheme to distinguish ordinary 9's from the special 9's that terminate numerals. The rule is typically something like this: Every 9 in the original number is replaced by 99, but the terminator is something different, like say 93. Then to send $(1111, 2222)$ we actually send 111199222299. But to send $(1191, 2922)$ we will send 11931992932299. The recipient reads this by breaking apart the transmission at each 99, then replacing 93 with 9 in each part to get the ordinary base-10 numeral for each number.

3. In a third scheme, each number we want to send is preceded by a length. For example, to send $(1111, 2222)$, we will actually send $(4, 1111, 4, 2222)$. To send $(111, 12222)$, on the other hand, we will actually send $(3, 111, 5, 12222)$.

   But now there's a question of how to separate the lengths from the data. If the receiver gets a long enough string that begins with 4111142222 it won't be clear that the first length is 4; it might be 41 or even 411. So we have to use one of the other two strategies for this: either require that the length itself has a maximum size, or use some sort of separator scheme.

   Say we require that the lengths be at most 9. Then 4111142222 is completely unambiguous. If we allow lengths up to 99, we need to send 041111042222 instead, and we can send any numbers up to 99 digits long. In the scheme of paragraph 1, we would have had to pad out 1111 with 94 leading zeroes to achieve this. D.J. Bernstein's "netstring" protocol uses this method. Data sent by his method is preceded by at most 9 digits indicating the length; this means that the actual data can't exceed 999999999 characters in length, which is usually enough.

   We can even use two levels of lengths. Say the first digit, between 1 and 9, is the length of the following numeral the describes the length of the actual number we wanted to send. Then we can send $(1111, 3333333333333333)$ as 1411112163333333333333333. The initial 1 means that the following 4 is the length of the following number, 1111; then there is a 2, which means that the next two digits, 16, are the length of the following number, 3333333333333333. With this scheme, we can compactly encode any sequence of numbers of up to 999999999 digits each. Numbers as big as $10^{10000000000}$ are very unusual, so this may be sufficient.

Answer 3

It is possible if you omit the condition "always". For example, for natural numbers $n,x,y \leq 10^n$ consider the function $f(x,y)=10^{2n}x+y.$ It this case we are able to extract $x$ and $y$ from $f(x,y).$