I need a hash function that will give all values from $0$ to $2^n - 1$. Will $f(x) = \frac{x^2 + x}{2} \; \text{mod} \; 2^n$ do the job?

Question

I need a hash function that will give all values from $0$ to $2^n - 1$. I want to know if this function does what is needed?

$$f(x) = \frac{x^2 + x}{2} \; \text{mod} \; 2^n$$

the values of $x$ are integers in the range $[0, 2^{n} - 1]$.

Answer 1

Consider if there are any $x, y \in [0, 2^n - 1]$ where $x \neq y$ and $f(x) = f(y)$. If so, then there's a $k \in \mathbb{Z}$ where

$$\begin{equation}\begin{aligned} \frac{x^2 + x}{2} - \frac{y^2 + y}{2} & = k\left(2^n\right) \\ x^2 + x - (y^2 + y) & = k\left(2^{n+1}\right) \\ x^2 - y^2 + x - y & = k\left(2^{n+1}\right) \\ (x - y)(x + y) + (x - y) & = k\left(2^{n+1}\right) \\ (x - y)(x + y + 1) & = k\left(2^{n+1}\right) \end{aligned}\end{equation}\tag{1}\label{eq1A}$$

Now, if $x - y$ is even, then $x + y + 1$ is odd, and vice versa. This means all of the $n + 1$ or more factors of $2$ must be in just one of those $2$ factors on the left, i.e.,

$$x - y \equiv 0 \pmod{2^{n+1}} \; \; \text{ or } \; \; x + y + 1 \equiv 0 \pmod{2^{n+1}} \tag{2}\label{eq2A}$$

The first condition doesn't occur since it was stated $x \neq y$, and you have $|x - y| \lt 2^{n+1}$. The second one can't be true either since $x + y + 1 \gt 0$ and, with $x, y \le 2^n - 1$, you have $x + y + 1 \le (2^n - 1) + (2^n - 1) + 1 = 2^{n+1} - 1$.

This shows all of the values generated will be unique.