Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 9 down vote favorite

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

share|improve this question
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
Looks like there is a programming version of this same question on StackExchange: stackoverflow.com/questions/919612/… – Jordan Reiter Jul 2 '12 at 20:35
show 1 more comment

5 Answers

up vote 13 down vote accepted

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

share|improve this answer
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
up vote 20 down vote

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

share|improve this answer
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
This is how Godel numbering works, btw – houbysoft Jul 2 '12 at 23:14
@MarkBennet Ah, now I understand what you meant. – Michael Boratko Jul 2 '12 at 23:53
up vote 19 down vote

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.

share|improve this answer
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
up vote 10 down vote

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

share|improve this answer
up vote 2 down vote

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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