¿Cuál es el período de esta secuencia?

Question

Consideremos la relación de recurrencia:

$$x_{i+1}=p-1-((p \cdot i-1) \mod{x_i})$$

Si $p$ es primo y $x_0=1$ ¿cuál es el menor período de la secuencia resultante (eventualmente periódica)?

Mi opinión es que el período mínimo es igual a $\text{lcm}(p-1,...,2)$ pero sólo lo creo en raras ocasiones y no puedo reunir una cantidad convincente de pruebas numéricas.

Edición (19/1/17):

Supongamos que $p$ es compuesto. Debería $\text{gcd}(x_{i_0},p)$ sea mayor que uno para algunos $i_0$ entonces siempre es mayor que uno a partir de entonces. Así que encontrar un factor de $p$ se reduce a computar $x_i$ para cualquier tamaño de $i$ .

Los pocos experimentos que he realizado sugieren que esta secuencia siempre se resquebraja (de forma bastante ineficaz) $p$ . ¿Puede alguien encontrar un contraejemplo?

Answer 1

Tu suposición es correcta.

Podemos construir una tabla de $x_{i+1}$ con valores de $(p\cdot i-1)$ como el eje y y $x_i$ (el módulo) como eje x; considerando el ejemplo de $p=5$ que tenemos:

          mod
 pi-1    1 2 3 4

  4      4 4 3 4
  9      4 3 4 3
 14      4 4 2 2
 19      4 3 3 1
 24      4 4 4 4
 29      4 3 2 3
 34      4 4 3 2
 39      4 3 4 1
 44      4 4 2 4
 49      4 3 3 3
 54      4 4 4 2
 59      4 3 2 1
 64      4 4 3 4

Observe cómo $0 < x_i < p$ y cómo desde $p$ es primo, el período de cualquier columna, $x_i$ , será $x_i$ . Esto hace que sea fácil ver que el período de toda la tabla (antes de que las filas comiencen a repetirse) es efectivamente $\text{lcm} (1, ..., p-1)$ .

Para ver por qué esto representa el período de la secuencia en cuestión, considere el hecho de que $x_{i+1}$ será igual al ${x_i}^{th}$ número en el $i^{th}$ fila de la tabla anterior. Por ejemplo $x_3 = 3$ así que vamos al 3er elemento de la tercera fila (empezando por 14), y obtenemos $x_4 = 2$ . A continuación, pasamos al 2º elemento de la siguiente fila y obtenemos $x_5 = 3$ y así sucesivamente.

Teniendo en cuenta esto, está claro que el periodo será el lcm de cada columna que se visite al menos una vez (así que si se diera el caso de que el valor cambiara entre la 2ª y la 3ª columna, el periodo sólo sería 6). Sin embargo, es imposible que la secuencia no incluya cada número al menos una vez. Esto se debe a que para cualquier subconjunto de las columnas, debe haber al menos una fila que esté compuesta completamente por un valor que no esté entre esas filas. Como cada columna incluirá números que no están en el subconjunto, y como las columnas son todas coprimas (y si no, pueden representarse de forma equivalente por un conjunto de columnas coprimas), una combinación que sólo incluya estos números debe ocurrir al menos una vez. Esto significa que, independientemente del valor anterior, el siguiente tendrá que estar en una fila exterior.

Sólo soy un aficionado, y tengo poca experiencia en intentar expresar mis ideas con rigor; he intentado que mi explicación sea lo más clara posible, pero no dudes en pedir aclaraciones si ves algún fallo de lógica o algo difícil de entender.