non-sequential sequence function

Question

if i remember correctly (i had one workshop on numerics years ago, sorry for my lack of knowledge) there is a way to create some sort of hash function that gives you a non sequential sequence. This would create a table like:

| x | fn(x) |
| 1 |     4 |
| 2 |     6 |
| 3 |     1 |
| 4 |     5 |
| 5 |     2 |
| 6 |     3 |

Is it possible to create such a function with relatively simple math?

To give an insight into "what is it this guy need": I have a system that internally uses an incremental id (starts with 0, ends with n) and i want it to generate a random id (public id) from that. This random id thou should not be higher than n because the id's should be kept small in the start. The generated id would have not only numbers but also characters a-z. So with having 4 digits for the public id, n would be ( 10 + 26 )^4 => 1679616 right? So i need that function to work for n to m where n is 0 and m is 1679616.

Answer 1

Generally the term "hash" means that you want your sequence to be essentially random, ideally without duplicates. So it looks like you want your "random" sequence to be a random permutation of 1 to n. The best way to do this would be to get random bits, say by using the least significant digit of a measurement like wind speed or temperature. Pseudo-random number generators can also do what you want: If you have a pseudo-random number generator that can generate numbers between 1 and a large number N (you can multiply pairs or triplets of values to get up to large N), then you use this as a black box to generate a random number between 1 and n, and then generate a random number between 1 and n-1, etc., to get indices for swaps to generate a (pseudo)-random permutation that is your function to define your sequence. One of the earliest pseudo-random number generators was the linear congruential generator http://en.wikipedia.org/wiki/Linear_congruential_generator which is easy to understand mathematically, but the Mersenne twister is much better and is what's used in many programming languages today.

Answer 2

Suppose there are $n$ numbers in your sequence ($n=6$ in your example). Choose some positive integer $a$ such that gcd$(a,n)=1$. Then we define $$f(x)=ax\pmod{n}$$

This uses a term from modular arithmetic; what it means is that $f(x)$ is the remainder when we divide $ax$ by $n$.

The reason you want gcd$(a,n)=1$ is to avoid collisions; if $a,n$ had a common factor there would be several $x$'s that get sent to the same place. Another benefit of this condition is that there must be another integer $b$ such that $ab\equiv 1\pmod{n}$. This allows us to compute the inverse of $f(x)$ via $$g(x)=bx\pmod{n}$$ These are inverses, i.e. $g(f(x))=x$. Hence given an element of the range of $f(x)$, we can compute which $x$ got sent there.