0
$\begingroup$

A smilar question has been asked before Create unique number from 2 numbers.

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)Mine should be Unique

Thanks a lot

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

The aceepted answer suggest the user to use Cantor pairing function which I tried to program it like this:

To calculate π(47, 32):

47 + 32 = 79,

79 + 1 = 80,

79 × 80 = 6320,

6320 ÷ 2 = 3160,

3160 + 32 = 3192,

so π(47, 32) = 3192.

To find x and y such that π(x, y) = 1432:

8 × 1432 = 11456,

11456 + 1 = 11457,

√11457 = 107.037,

107.037 − 1 = 106.037,

106.037 ÷ 2 = 53.019,

⌊53.019⌋ = 53,

so w = 53;

53 + 1 = 54,

53 × 54 = 2862,

2862 ÷ 2 = 1431,

so t = 1431;

1432 − 1431 = 1,

so y = 1;

53 − 1 = 52,

so x = 52; thus π(52, 1) = 1432.

π(a,b)=12(a+b)(a+b+1)+b.

But the Canton Pairing doesn't always create a unique number based on the two numbers used e.g:

a=73114279

b=1

π(a,b)=663902325

But when you inverse it, using the inverse fomular such that:

π(x,y)=663902325

You would get

π(-536868496,536884434)=663902325

My question is: What formular can I use so that I can always get a unique number from just two numbers, though the formular must be inversible such that:

(a,b)=c (b,a)=d

But when you inverse it, using the inverse fomular such that:

You would get c=(a,b) d=(b,a)

$\endgroup$
  • $\begingroup$ What do you need this for? Your practical needs will to a large degree determine what you should be using, and the nice looking formulas such as the zig-zag function may not be what makes the most sense in practice. $\endgroup$ – Henning Makholm Nov 18 '18 at 22:45
  • $\begingroup$ E.g. in most practical cases you will not be working with the whole infinite $\mathbb N$, but with machine integers of a particular fixed width. In that setting simply concatenating those fixed-width integers is much simpler and more efficient for many purposes. $\endgroup$ – Henning Makholm Nov 18 '18 at 22:47
  • $\begingroup$ I'm using it in a Java program, concatenating it wouldn't be helpful, though it would be fast. And as you noted I would be within a fixed range of integer which in Java is not more than 2 billion. So you see why concatenating would also be a bad idea assuming I have 243425 and 478363, concatenating both would really go beyond the 2 billion limits. Though negative numbers too are welcomed. $\endgroup$ – king amada Nov 18 '18 at 22:53
  • $\begingroup$ If you have two ints as input and want a single int as output, you will get collisions. There's no way around that. Again what do you need this for? (Yes, I see that your secret use of this function is in a Java program, but you have not told what that use is). $\endgroup$ – Henning Makholm Nov 18 '18 at 22:58
  • 1
    $\begingroup$ "but still give same answer as the other values" So? If it's not positive than it doesn't count. Are there any other positive pairs that give the same answer? If not you don't have a problem. $\endgroup$ – fleablood Nov 18 '18 at 23:09
0
$\begingroup$

If order is important--i.e., the number you create from $(a,b)$ must be different from $(b,a)$--then exploit the Unique Factorization Theorem to create the number:

$n = {\rm Prime}[a]^2 \rm{Prime}[b]$ where ${\rm Prime}[a]$ is the $a^{th}$ prime number.

  • ${\rm Prime}[2]^2 {\rm Prime}[30] = 1017$
  • ${\rm Prime}[1]^2 {\rm Prime}[15] = 188$
  • ${\rm Prime}[4]^2 {\rm Prime}[60] = 13769$

In Mathematica:

f[a_Integer, b_Integer] := Prime[a]^2 Prime[b]

For two numbers above $10^9$, this takes $0.030089$ seconds on a Mac laptop. Not wasteful at all... extremely efficient... And of course provably unique.

Of course, to go backward, you merely perform a Factorization:

FactorInteger[1017]

(* {{3, 2}, {113, 1}} *)

which means $1017 = 3^2 \times 113$

This tells you that the first element, $a$, is such that the $a^{th}$ prime is $3$, and the second element, $b$, is such that the $b^{th}$ prime is $113$.

You can easily and efficiently find these numbers:

PrimePi[3]

(* 2 *)

PrimePi[113]

(* 30 *)

In simple, efficient code:

reversef[n_Integer] := PrimePi[#] & /@ FactorInteger[n][[All, 1]]

So for the example you requested:

reversef[1445]

(* {3,7} *)

$\endgroup$
  • 1
    $\begingroup$ That is all well and good for theoretical purposes, but wasteful and slow in practice. $\endgroup$ – Henning Makholm Nov 18 '18 at 22:42
  • 2
    $\begingroup$ "that is all well and good for theoretical purposes, but wasteful and slow in practice." What practice? The op asked for a way to get unique numbers that is invertible. This is that. $\endgroup$ – fleablood Nov 18 '18 at 22:53
  • 1
    $\begingroup$ An example of what David G. Stork is suggesting is that $(3,7)\mapsto \text {third prime}^2\times \text{seventh prime}= 5^2\times 17 = 425$ and $(7,3) \mapsto \text {seventh prime}^2\times \text{third prime}= 17^2\times 5 = 1445$. It should be clear that the terms are unique. $\endgroup$ – fleablood Nov 18 '18 at 22:58
  • 1
    $\begingroup$ @DavidG.Stork: They say they're using it in a computer program, and in that context it will hard for them to have numbers that are not fixed width, unless they're making special efforts to use bignums. I'm guessing that probably they're not. $\endgroup$ – Henning Makholm Nov 18 '18 at 23:02
  • 1
    $\begingroup$ Every number has a unique prime factorization. $1445 = 5*17^2$. So $(a,b)$ will be so that $17$ is the $a$th prime and $5$ is the $b$th prime. And $17$ is the 7th prime and $5$ is the 3rd so $a = 7; b= 3$. $\endgroup$ – fleablood Nov 18 '18 at 23:17
2
$\begingroup$

In the comments you say you want to use your function in a Java program where it looks like you want it to have a signature more or less like

static int pair(int a, int b) {
     ...
}

However, then you're out of luck: It is impossible for a pure function with this signature to always give different outputs for different inputs. Even if you restrict yourself to nonnegative inputs, there are $2^{31}\cdot 2^{31}=2^{62}$ possible inputs to the function and only $2^{32}$ possible output values, so by the pigeonhole principle there must be some output values that are produced by more than a single input pair.

In your question you quote the Cantor pairing function $\pi(a,b)=\frac12(a+b)(a+b+1)+1$ and claim that $$\pi(73114279, 1) =663902325$$ But this result is wrong. The actual value of $\pi(73114279, 1)$ is $2672849006516341$ -- the smaller number you're seeing is the effect of arithmetic overflow when your Java program tries to multiply $73114280 \times 73114281$ and the result of that doesn't fit in an int.

Something, therefore, has to give. Depending on what you need the pairing for, I think you have basically these options:

  • Let the output be a long instead of an int. In that case I would forget about the Cantor pairing function and simply do a binary concatenation of the two values:

    static long pair(int a, int b) {
       return ((long)a << 32) + (b & 0xFFFFFFFFL);
    }
    
  • Decide that you won't be able to handle inputs so large that the pairing function overflows. In that case you might still want to do a simple concatenation:

    /** a and b should not be more than 65536 */
    static int pair(int a, int b) {
       return (a<<16) + b;
    }
    
  • Accept that there will sometimes be collisions and deal with them somehow. What you want may be simply a hash function -- for example run a through one of the functions suggested here and add b.

  • Use BigInteger instead. (The lazy option, but I think the chance that it is actually best for you is quite small).

  • Drop the idea of representing your two integers as one number and instead use simply an int[] or an object with two int fields a and b. (Even lazier, and better in many contexts).

$\endgroup$
1
$\begingroup$

I showed in this answer how to adapt the Cantor pairing function to accept negative as well as positive arguments. It is not a complex calculation, a few adds and one multiply. The problem is that the number you get is approximately four times the square of the sum of the absolute values of the two input numbers. If those numbers are even about $32{,}000$ the result will overflow $32$ bits. There is no way around it. If your input numbers have $16$ bits there are $2^{16}$ of them, so there are $2^{32}$ pairs of them and you will overflow. What is your objective for combining two numbers into one?

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