Funciones como $f(x)=2x+3$ $f(x)=3^x-8$ tienen algunos muy agradable propiedades si se trata de congruencias. En particular, si se toma una $n\in\Bbb{N}$ y escriba $f(x)\mod n$, verás que es un patrón que se repite, con los números no se produzca más de una vez en cada ciclo.
Una más clara definición más formal debido a Greg Martin:
Una función de $h$ definida en los enteros positivos se llama fielmente periódica con período de $q$ si la propiedad ha $h(m)=h(n)$ si y sólo si $n\equiv m\pmod q$.
Una función de $f:\Bbb{N}\to\Bbb{Z}$ ahora es normal si para cada módulo de $k\geq 2$, la función de $\pi_k\circ f$ es fielmente periódico, donde $\pi_k:\Bbb{N}\to\Bbb{Z}/k\Bbb{Z}$ es el cociente mapa. También, para cada módulo de $k\geq 2$, vamos a $f_q(k)$ ser el período de $\pi_k\circ f$.
No he sido capaz de encontrar ninguna de las funciones normales que crecen más rápido que una función lineal, pero más lento que una función exponencial, En particular de las funciones normales $f(n)=O(n^\alpha)$ $\alpha>1$
Pregunta: ¿existen tales funciones?
Lo que he probado hasta ahora
1) Esto es bastante obvio, pero si $f$ es una función normal con $f(0)=0$, $\forall n,m\in\Bbb{Z}: f_q(n)\mid m\implies m\mid f(n)$
Prueba: set $\pi_k\circ f=h_k$. cleary para todos los $k$,$h_k(0)=0$. Ahora $h_k(n)=0$ si y sólo si $f_q(k)\mid n$.
Algunos Intuición acerca de por qué lineales y las funciones exponenciales son normales
Corto y sencillo: pueden ser definidas como secuencias de $\{a_n\}_{n=1}^{\infty}$ de tal manera que, para todos los $k\in\Bbb{N}$, no necesitamos saber el valor de $n$ o $a_{n-1}$ a calcular $a_n\pmod k$, sólo necesitamos $a_{n-1}\pmod k$. Para ser claros, esto es sólo mi intuiton. Creo que va a ser fácil probar que tales funciones son siempre normales, pero no es fácil de demostrar que las funciones normales 'look' como este.
