Function of two integers that has not repeated values

Question

In order to implement a software I need a function $f:\mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ such that: $$(x' \neq x \lor y' \neq y) \Rightarrow f(x,y) \neq f(x',y') $$

It's very easy to implement an algorithm that implements such a function, but I was not able to find an analytical representation of it.

coult you help me?

What's wrong with having an algorithm? – Oct 11 '13 at 12:22 — , Oct 11 '13 at 12:22
Just a performance issue. An equation would be faster. – Aslan986 Oct 11 '13 at 12:25 — Aslan986, Oct 11 '13 at 12:25

score 3 · Answer 1 · answered Oct 11 '13 at 12:19

3

If you are not afraid of being wasteful, try $f(x,y)=2^x3^y$. This is however hardly suitable for limited software.

answered Oct 11 '13 at 12:19

Hagen von Eitzen

374,180

Along similar lines: $3^x+2^y$, although proving the required condition may be a challenge (if it actually holds)... – abiessu Oct 11 '13 at 12:23
1

@abiessu: It doesn't: $3^1+2^1 = 5 = 3^0+2^2$. And if you don't like zeroes, $3^1+2^3 = 11 = 3^2+2^1$. – hmakholm left over Monica Oct 11 '13 at 12:26

hmakholm left over Monica · Accepted Answer · 2013-10-11T12:43:25.553

3

The usual "Cantor zig-zag" mapping can be defined as

$$ (x,y) \mapsto \frac{(x+y)(x+y+1)}{2} + x $$

It has the (sometimes) nice property that it is surjective, that is, every natural number is the image of some pair, so nothing goes to waste.

edited Oct 11 '13 at 12:43

answered Oct 11 '13 at 12:24

hmakholm left over Monica

286,031

1

$(a, 0)$ and $(0, 1 + a)$ are both sent to the same value. I think you need $(x + y + 1)$ in the numerator instead of $(x + y - 1)$ to make it work. – Arthur Oct 11 '13 at 12:32
@Arthur: Hm, yes, fixed. I forgot there are $N+1$ combinations with $x+y=N$, not just $N$. – hmakholm left over Monica Oct 11 '13 at 12:36
The inverse function would be $x+y=floor(sqrt(2n+2)-0.5)$ – Empy2 Oct 11 '13 at 12:59

Function of two integers that has not repeated values

2 Answers2