Is it possible to combine two integers in such a way that you can always take them apart later?

Given two integers $n$ and $m$ (assuming for both $0 < n < 1000000$) is there some function $f$ so that if I know $f(n, m) = x$ I can determine $n$ and $m$, given $x$? Order is important, so $f(n, m) \not= f(m,n)$ (unless $n=m$).

-

3
It rather depends what you want to achieve. It is certainly possible because $\mathbb Z \times \mathbb Z$ is countable – Mark Bennet Jul 2 '12 at 18:22

1
The most obvious such function is $f(n,m)=(n,m)$. Or do you want the function to output integers or something? – Chris Eagle Jul 2 '12 at 18:32

4
Google "pairing function". This is a duplicate of many prior questions. – Gone Jul 2 '12 at 18:41

2
@BillDubuque This is one of those cases where as soon as I knew what the term was, I'd have my answer. But, of course, I didn't. – Jordan Reiter Jul 2 '12 at 20:35
– Jordan Reiter Jul 2 '12 at 20:35
show 1 more comment

5 Answers

If there are no bounds on your integers, use the Cantor pairing function. It is pleasantly easy to compute, as are its two "inverses."

For the case where your integers are bounded by say $10^6$, you can simply concatenate the decimal expansions, padding with initial $0$'s as appropriate. Or do something similar with binary expansions. Dirt cheap to combine and uncombine, an easy string manipulation even when we allow bounds much larger than $10^6$.

-

6
Of course the concatenation procedure can also be written mathematically: $f(m,n) = 10^6 m + n$. Given $f(m,n)$, you get back $m$ and $n$ as quotient and reminder when dividing by $10^6$. – celtschk Jul 2 '12 at 18:42

f(m,n) = m +(1/n)

If there are numbers to the right of the decimal,
m =number to the left of decimal.
n = the reciprocal of the numbers to the right of the decimal
example
f(m,n) =10.5 then m =10, n=1/(0.5) =2

If there are no numbers to right of the decimal [f(m,n) is itself an integer]
then m = f(m,n) -1,
n =1
example
f(m,n) =20 then m=19, n =1

-

Since others have answered, here is another idea - less easy to write down explicitly as a mathematical function, but easy to describe and easy to implement if you have a machine which can handle strings. Send the digits of the first number to odd positions and the digits of the other to even positions so (31, 5681) would go to 50,608,311.

-
But this would only work if the numbers had the same number of digits, right? – Jordan Reiter Jul 2 '12 at 20:33

4
@JordanReiter I have deliberately used an example where the number of digits is different. – Mark Bennet Jul 2 '12 at 21:03

1
This is the first answer so far that doesn't necessarily use at least one more than the maximum number of digits each integer is allowed, plus it has an infinite range and it's trivially easy to parse back out without knowing the original maximums. It also works just as well in binary as decimal. If storage is a premium - and I can't think of any other reason to do something like this - yours would be my first choice. – SilverbackNet Jul 2 '12 at 23:02
@MarkBennet sorry, I see that now! – Jordan Reiter Jul 3 '12 at 16:19

Define $f(n,m) = n+1000000m$. Then $n = f(n,m) \mod 1000000$, and $m = \frac{f(n,m) - n}{1000000}$.

-

$f(n,m) = 2^n 3^m$.

Alternatively, use the bijection between $\mathbb N \times \mathbb N$ and $\mathbb N$ which is given by $$f(n,m) = \frac{(n+m)(n+m+1)}{2} + m$$

-

3
The advantage the $2^n 3^m$ approach has over all the other suggestions so far is that it gives you a way of encoding an ordered $r$-tuple without knowing in advance what $r$ is, by adding in powers of 5, 7 ... . – Mark Bennet Jul 2 '12 at 18:50
@MarkBennet This scaling advantage is also shared by the Cantor pairing function, through recursive application. – Michael Boratko Jul 2 '12 at 19:46
@MichaelBoratko If you have an integer given by the Cantor Pairing you cannot decode it without knowing how many iterations you have to go through. The prime product gives you this, at the cost of not being surjective, and this also means that the coded values will tend to be significantly higher for the prime product version. – Mark Bennet Jul 2 '12 at 19:53
– houbysoft Jul 2 '12 at 23:14
@MarkBennet Ah, now I understand what you meant. – Michael Boratko Jul 2 '12 at 23:53
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 29, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9225691556930542, "perplexity_flag": "middle"}