Take the 2-minute tour ×
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.

is there some way to create unique number from 2 positive integer numbers? Result must be unique even for these pairs: 2 and 30, 1 and 15, 4 and 60. In general, if I take 2 random numbers result must be unique(or with very high probability unique)

Thanks a lot

EDIT: calculation is for computer program,so computational complexity is important

share|improve this question
    
You do not specify what you mean by making a number out of two numbers. –  shuhalo Feb 24 '11 at 9:17
    
Are the pairs ordered? Should 2 and 30 produce the same answer as 30 and 2? –  Henry Feb 24 '11 at 10:02
    
2and30,30and2 are two different pairs –  Cicik Feb 24 '11 at 10:52
5  
I don't get the bounty. Alex Kruckman gave a very good answer whose computational complexity is essentially $O(1)$ if I am not mistaken. Can you please specify what is wrong with the answer given so far? –  Asaf Karagila Mar 8 '11 at 22:20
    
I agree with Asaf. Alex Kruckman's answer mentions a quite fast pairing function. If you are really concerned about the efficiency of the algorithm (for reading and writing), then you should probably look for some other ways of combining two numbers, like a list or an ordered pair, or whatever your language supports. But as far as standard mathematical pairing functions go, Cantor's is reasonably quick. Of course, it would be much easier to answer your question appropriately if we knew what your motivation is. –  Abel Mar 9 '11 at 1:41

4 Answers 4

up vote 34 down vote accepted
+50

The sort of function you are looking for is often called a pairing function.

A standard example is the Cantor pairing function $\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$, given by: $\pi(a,b) = \frac{1}{2}(a+b)(a+b+1) + b$.

You can find more information here: http://en.wikipedia.org/wiki/pairing_function

share|improve this answer
    
thanks, this is good advice. can you suggest me which pairing function has the smallest computational complexity? –  Cicik Mar 8 '11 at 21:24
    
If you're looking for something of minimal computational complexity for a computer to handle, you could use an "infinite hotel" type construction where you think of the number as its binary expansion -- a list of 0's and 1's and then you "merge" the list by taking one term from each number, in succession. –  Ryan Budney Mar 8 '11 at 22:21
    
That's not necessarily the cheapest way, it depends on what you're counting. In most actual computers, there is a multiplication at a reasonable price, while zipping two binary expansions will take many operations. The Cantor pairing function is the cheapest in actual applications, with only three(!) additions, one multiplication, and a single right shift (to get the $\tfrac12$). –  Rhymoid Dec 24 '12 at 18:19
    
Just to make it clear, this formula DOES NOT GENERATE the same output when you change the order of A and B, e.g: f(A,B) != f(B,A). –  little dinosaur Oct 21 at 12:53

if the numbers are $a$ and $b$, take $2^a3^b$. This method works for any number of numbers (just take different primes as the bases), and all the numbers are distinct.

share|improve this answer

Google pairing function. As I mentioned in the similar question, there are also other pairing functions besides the well-known one due to Cantor. For example, see this "elegant" pairing function, which has the useful property that it orders many expressions by depth.

share|improve this answer

For positive integers as arguments and where argument order doesn't matter:

  1. Here's an unordered pairing function:

    $<x, y> = x * y + trunc(\frac{(|x - y| - 1)^2}{4}) = <y, x>$

  2. For x ≠ y, here's a unique unordered pairing function:

    <x, y> = if x < y:
               x * (y - 1) + trunc((y - x - 2)^2 / 4)
             if x > y:
               (x - 1) * y + trunc((x - y - 2)^2 / 4)
           = <y, x>
    
share|improve this answer
1  
If you look in the comments, the OP specifically notes that for their application, argument order does matter. –  Steven Stadnicki Mar 10 at 6:59

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.