Functions like $f(x)=2x+3$ and $f(x)=3^x-8$ have some very nice properties if it comes to congruences. In particular, if you pick any $n\in\Bbb{N}$ and write down $f(x)\mod n$, you'll see that it's a repeating pattern, with no numbers occuring more than once in each cycle.
A clearer, more formal definition due to Greg Martin:
A function $h$ defined on the positive integers is called faithfully periodic with period $q$ if it has the property $h(m)=h(n)$ if and only if $n\equiv m\pmod q$.
A function $f:\Bbb{N}\to\Bbb{Z}$ is now normal if for every modulus $k\geq 2$, the function $\pi_k\circ f$ is faithfully periodic, where $\pi_k:\Bbb{N}\to\Bbb{Z}/k\Bbb{Z}$ is the natural quotient map. Also, for every modulus $k\geq 2$, let $f_q(k)$ be the period of $\pi_k\circ f$.
I have not been able to find any normal functions which grow faster than a linear function, but slower than an exponential function, In particular normal functions $f(n)=O(n^\alpha)$ with $\alpha>1$
Question: Do there exist any such functions?
What I've proven so far
1) This is quite obvious, but if $f$ is a normal function with $f(0)=0$, then $\forall n,m\in\Bbb{Z}: f_q(n)\mid m\implies m\mid f(n)$
Proof: set $\pi_k\circ f=h_k$. cleary for all $k$, we have $h_k(0)=0$. Now $h_k(n)=0$ if and only if $f_q(k)\mid n$.
Some Intuition about why linear and exponential functions are normal
Short and simple: they can be defined as sequences $\{a_n\}_{n=1}^{\infty}$ in such a way that, for all $k\in\Bbb{N}$, we don't need to know the value of $n$ or $a_{n-1}$ to compute $a_n\pmod k$, we only need $a_{n-1}\pmod k$. To be clear, this is just my intuiton. I think it will be easy to prove that such functions are always normal, but not easy to prove that all normal functions 'look' like this.
I think a stronger result is given in the Perelli-Zannier paper I mention in the comments. A sequence of integers is "arithmetically periodic" if it is periodic modulo $p$ for all sufficiently large primes $p$.
Theorem. Let $f:{\bf N}\to{\bf Z}$ be arithmetically periodic, with period $r_p$ for prime $p>p_0$. Suppose there exists a set $J_p\subseteq{\bf Z}/p{\bf Z}$ such that $|J_p|=r_p$ and $$f({\bf N})\cap(a+p{\bf Z})\ne\emptyset{\qquad\rm whenever\qquad}a\in J_p$$ Then three cases can occur:
(i) $r_p$ is constant for large $p$, and $f$ is periodic.
(ii) $r_p=p$ for large $p$, and $f$ is a polynomial of degree 1.
(iii) There exists an integer $a$ and rational numbers $A$ and $B$ such that $f(n)=Aa^n+B$.
The paper is available from http://www.sciencedirect.com/science/article/pii/0022314X8290083X