12
$\begingroup$

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

$\endgroup$
6
  • 3
    $\begingroup$ It rather depends what you want to achieve. It is certainly possible because $\mathbb Z \times \mathbb Z $ is countable $\endgroup$ Jul 2 '12 at 18:22
  • 1
    $\begingroup$ The most obvious such function is $f(n,m)=(n,m)$. Or do you want the function to output integers or something? $\endgroup$ Jul 2 '12 at 18:32
  • 4
    $\begingroup$ Google "pairing function". This is a duplicate of many prior questions. $\endgroup$ Jul 2 '12 at 18:41
  • 2
    $\begingroup$ @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. $\endgroup$ Jul 2 '12 at 20:35
  • $\begingroup$ Looks like there is a programming version of this same question on StackExchange: stackoverflow.com/questions/919612/… $\endgroup$ Jul 2 '12 at 20:35
22
$\begingroup$

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

$\endgroup$
5
  • 3
    $\begingroup$ 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 ... . $\endgroup$ Jul 2 '12 at 18:50
  • $\begingroup$ @MarkBennet This scaling advantage is also shared by the Cantor pairing function, through recursive application. $\endgroup$
    – process91
    Jul 2 '12 at 19:46
  • 1
    $\begingroup$ @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. $\endgroup$ Jul 2 '12 at 19:53
  • $\begingroup$ This is how Godel numbering works, btw $\endgroup$
    – houbysoft
    Jul 2 '12 at 23:14
  • $\begingroup$ @MarkBennet Ah, now I understand what you meant. $\endgroup$
    – process91
    Jul 2 '12 at 23:53
20
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ But this would only work if the numbers had the same number of digits, right? $\endgroup$ Jul 2 '12 at 20:33
  • 4
    $\begingroup$ @JordanReiter I have deliberately used an example where the number of digits is different. $\endgroup$ Jul 2 '12 at 21:03
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 2 '12 at 23:02
  • $\begingroup$ @MarkBennet sorry, I see that now! $\endgroup$ Jul 3 '12 at 16:19
14
$\begingroup$

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

$\endgroup$
1
  • 7
    $\begingroup$ 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$. $\endgroup$
    – celtschk
    Jul 2 '12 at 18:42
10
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.