I'm looking for a pairing function $f(x,y)$ which gives unique values for every combination of integers $x,y>0$ and and as special property 0 for $x=0$ $\forall y$.
Or to be more general we can also replace $0$ with constants.
We do know the max values of $x$ and $y$ can achieve
We are allowed to shift $x, y$ values. So we also know their min values. Which don't need to be 0
So the more general definitions with constants $c_x, c_f$ (instead of $0$): $$ x_{min} \le x \le x_{max}$$ $$ y_{min} \le y \le y_{max}$$ $$\forall y: f(c_x,y) = c_f $$ $$\forall y, \forall x\not= c_x: f(x,y)\not = f(y,x) \not = c_f$$It will be used in a computer program. The goal is finding a function with a max result as small as possible (bit's needed for representation) while still being easy and fast to compute by a machine (not using too much storage). Therefore integer calculations are appreciated. Floating point can lead to inaccuracies.
The inverse can be anything. We only need to check if two variables $x,y$ lead to the target number.
No case selections are allowed (e.g. for $x=0$). Something like Kronecker Delta function which can only be $0$ for input $0$ and $1$ for anything else is also not allowed.
Target value size, the number of different values $|${$x$}$|$ $= 2^{16} = 65536$ and
$|${$y$}$|$ at least $2^{26} = 67108864$.
Size $|${$y$}$|$ can be bigger but $\max f(x,y) < 2^{92}$
Can we find any such function?
Here some Examples:
I) Pairing functions which do not work ( not $0$ or a constant for any $x = c_x$ ) :
Cantor's pairing function :
$$f(x,y)=\frac{(x+y)\cdot (x+y+1)}{2} + a$$
Szudzik pairing function:
$$ \begin{eqnarray*} f(x,y) = \begin{cases} y^2 + x, &\text{if }x < y, \\ y^2 + x + y, &\text{if }x \ge y \end{cases} \end{eqnarray*} $$ This has some cases selection we do not want. We can shift $y$ to be always larger than $x$ and with this reduce it to: $$f(x,y) = (y+x_{max} +1 )^2 + x$$ Can we modify them to be a constant for a certain $x = c_x$?
II)
Pairing function which does work but needs extra memory/time :
If we use $0 \le x \le 2^{16}-1$ it can not surpass value $2^{16} = 65536$. Next prime above it is 65537. This is the 6543'th prime number.
Let $p(i)$ return the $i'th$ prime number.
Let $0 \le y \le 2^{26}-1$
With this we can do the pairing function:
$$f(x,y) = x \cdot p(y + 6543)$$
This returns a unique value for every combination $x,y$ except for $x = c_x = 0$ it will always return the constant $c_f = 0$.
However this works good in theory but calculating $p$ takes quite a long time. Storing all values would take a lot of memory ($\approx 268$ MB) - not a nice option.
Max value of $f(x,y)$ would be $2^{46.31}$ needing $47$ bits which is not too far from optimum $42$ bits. (Cantor and Szudzik are much bigger)
To reduce memory we can split $y$ into half bit-size parts. For $2^{26}$ different values this would be $2^{13}$. First part gets represented by the first $2^{13}$ primes after $2^{16}$, second part by the $2^{13}$ primes after that. $$f(x,y) = x \cdot p(y_{\text{bits } 1..13} + 6543) \cdot p(y_{\text{bits } 14..26} + 6543 + 2^{13}) $$ This would reduce memory but scales the max value of $f(x,y)$ to $2^{51.3}$, so we need $52$ bits.
Question: Can we find any such pairing function which does not need to replace parameter $x,y$ with their primes (or similar) while the resulting value $f(x,y)$ won't get much bigger than $2^{52}$ (at most $2^{92}-1$ ) ?
III) Pairing function which might work but is too big:
While testing around I came up with
$$f(x,y) = ((x+1)^2+y^2) \cdot (x^3+(y+1)^2) \cdot x$$
I have no proof that this is a valid pairing function for all combinations $x,y$ but in tests it did work for all combinations $x<2^{8}, y<2^{20}$
However the results can get too big. It needs up to $121$ bits.
Can we find a pairing function with a smaller max value?
Edit:
IV) For $0\ge x < 2^{m}$, $0\ge y < 2^{n}$ we could do
$$ f(x,y) = 2^{m}\cdot x \cdot y + x$$
With target $m=16, n=24$ this will give us $58$ bit numbers.
Can we go smaller?