He aquí una secuencia fija $n \in \mathbb{N}$ :
$$ j_{i+1} = (5 j_i + 1) \pmod{ 2^n} $$
Esta regla de actualización puede simplificarse:
$$ j_{i} = \frac{5^i - 1}{4} \pmod{ 2^n}$$
Se puede verificar fácilmente lo anterior mediante prueba por inducción.
Ahora cuando empiezas con $j_1 = 1$ se acabarán generando todos los números del intervalo $[2, 2^i]$ y luego vuelve a 0 (en cuyo caso el término posterior vuelve a ser 1).
Escribí un rápido programa python para verificar esto:
ctr = 1
j = 1
exp = 20 # This is the n in 2^n
while j:
j = ((5*j) + 1) % 2**exp
ctr += 1
print("{} elements found.".format(ctr))Y hasta exp = 25 esto funciona. Ejecutando lo anterior nos da 1048576 elements found .
Tengo un poco de conocimiento en teoría de grupos, y por lo que parece esto es similar a la intuición de grupos cíclicos. Sin embargo, no se me ocurre una explicación plausible de por qué esto es cierto. ¡Cualquier ayuda será muy apreciada!
EDITAR:
También quería comprobar que efectivamente no había duplicados, así que utilicé un hashset para comprobar hasta $2^{16}$ elementos.
ctr = 1
j = 1
exp = 16
seen = set([1])
while j:
j = ((5*j) + 1) % 2**exp
ctr += 1
if j in seen:
print("DUPLICATE FOUND")
seen.add(j)
print("{} elements found.".format(ctr))Y parece que tampoco había duplicados.
