Fórmula de forma cerrada para la recursión de mods repetidos

Question

Estoy buscando una fórmula de forma cerrada para la recursión:

$$x_1=0$$ Para $n\ge2$

$$x_n= x_{n-1}+k\mod n$$

es decir, para $k=5$ ,

$$x_1=0, x_2=1, x_3=0, x_4=1, x_5=1, x_6=0, x_7=5$$

Answer 1

Me parece que encontrar una fórmula cerrada (en un sentido tradicional) para este tipo de problema es bastante difícil, y tal vez infructuoso (ya que la fórmula puede no ser eficientemente computable).

Pero podemos hacer lo siguiente, no sé si esto ayuda (voy a ser esquemático y con un punto de vista ordinal, centrado en las secuencias como sistemas dinámicos):

Supongamos que $n$ es ya mucho mayor que $k$ y que $x_n=0$ . Entonces, durante un tiempo, los siguientes términos de la secuencia se van a comportar como una progresión aritmética habitual (es decir, $x_m=k(m-n)$ ), hasta que la secuencia, debido a su progresión por $k$ , atrapa de nuevo el tamaño de $m'$ con su progresión por $1$ . Entonces la operación del resto se comportará de manera no trivial y "reiniciará" la secuencia, produciendo un número entre $0$ y $k-1$ para $x_{m'}$ .

Así que una buena pregunta es: Dado $n$ ¿podemos encontrar $m'$ es decir, ¿podemos predecir cuándo se reiniciará la secuencia? Sí podemos. Llamemos $next(n,k)$ al primer índice $i$ tal que la secuencia $a_i:=k\cdot i$ es igual o superior a la secuencia $b_i:=n+i$ ; entonces mientras $a_i$ cubre la primera $n$ elementos en $n/k$ pasos, $b_i$ cubre $n/k$ elementos más, que están cubiertos por $a_i$ en $(n/k)/k$ pasos, etc. De ahí que $$next(n,k)=\lceil n\cdot \sum_{i=0}^\infty\frac1{k^i}\rceil = \lceil\frac{kn}{k-1}\rceil.$$

Por lo tanto, hasta que $next(n,k)$ que se calcula eficientemente, la secuencia se comporta como una progresión aritmética habitual, y luego se reinicia (calculamos el resto del término correspondiente de la secuencia módulo $next(n,k)$ ) y continúa hasta que el índice alcanza $next(next(n,k),k)$ o el mismo número menos $1$ dependiendo de si el resto es lo suficientemente grande como para saltarse un índice (es decir, cerca de $0$ o cerca de $k$ ).

---

Actualización: Estoy añadiendo un ejemplo específico debido a la petición del OP.

Supongamos que $k=3$ . Entonces $\displaystyle\sum_{i=0}^\infty\frac1{k^i}=\frac32$ que es el número que necesitamos para calcular el siguiente función.

Utilizando el truco indicado anteriormente para $n\leq k$ es un poco confuso si queremos entenderlo desde el principio, así que vamos a calcular hasta $n=4$ sólo a mano: $x_1=0, x_2=1, x_3=1, x_4=0$ .

Ahora tenemos $x_4=0$ , y podemos decir que en el índice 4 se ha reiniciado la progresión aritmética por 3, convenientemente a 0 (analizaremos otros casos en un momento).

Sabemos que desde $n=4$ en adelante, $x_n$ se comportará como una progresión aritmética habitual, hasta que $n$ golpea $next(4,3)=4\cdot\frac32 = 6$ , valor en el que se reinicia de nuevo. Entonces simplemente $x_5=3$ y $x_6=0$ , ya que empezamos con el valor $0$ (en $x_4$ ) y en realidad golpea un entero dentro de la siguiente función (porque el producto por $\frac32$ es un entero, no un medio entero).

Ahora comenzamos la progresión aritmética desde el valor $0$ en el índice 6 hasta el índice $next(6,3)=6\frac32=9$ que es entero y, por lo tanto, acertado, por lo que $x_7=3, x_8=6, x_9=0$ .

La siguiente progresión aritmética va desde $n=9$ hasta $next(9,3)=\lceil 9\frac32 \rceil = \lceil 13.5\rceil = 14$ , lo que significa que deberíamos tener $x_{13.5}=0$ y así $13$ es el último índice antes del reinicio (y $14$ la primera después del reinicio). Por lo tanto, $x_{10}=3, x_{11}=6, x_{12}= 9, x_{13}= 12$ y $x_{14}=1$ .

También podemos calcular directamente los valores en $n=13$ y $n=14$ para no tener que seguir toda la progresión: el reinicio no se produjo en el valor 0 porque el índice inicial era un número impar $n=2m+1$ esto implica que $next(n,3)=3m+2$ (índice en el que ya se ha producido el reinicio), y el valor en el índice $3m+1$ es sólo $3m$ (al pasar de $2m+1$ a $3m+1$ , en $m$ pasos y partiendo de 0, de modo que nuestra progresión aritmética por 3 crece hasta $3m$ ). Por lo tanto, hemos demostrado que si empezamos en 0 con el índice impar $2m+1$ entonces el valor en $next(n,3)=3m+2$ es $1$ (de $3m+3$ mod $3m+2$ ).

La siguiente progresión aritmética va desde $n=14$ a partir de 1, hasta $next(14,3)=21$ que termina también en el valor 1 (ya que $n=14$ es par). Por lo tanto, $x_{14}=1, x_{15}=4, x_{16}=7, x_{17}=10, x_{18}=13, x_{19}=16, x_{20}=19$ .

El siguiente va de $n=21$ (impar) a partir de 1, supuestamente hasta $next(21,3)=32$ pero el hecho de que empecemos en el índice impar más el hecho de que el valor inicial sea 1 complotan para hacer el reset un índice antes, en $n=31$ :

Comenzamos en el índice impar $n=2m+1$ con valor 1. Entonces $next(n,3)=3m+2$ como antes y el valor en $3m+1$ sería, como antes, $3m$ si se partiera de 0, pero como se parte de 1, su valor real es $3m+1$ que es 0 mod. $3m+1$ .

Los siguientes pasos no triviales en nuestros cálculos son $x_{31}=0$ (impar, comienza en 0), $x_{47}=1$ (impar, comienza en 1), $x_{70}=0$ (incluso, comienza en 0), $x_{105}=0$ (impar, comienza en 0), $x_{158}=1$ (incluso, comienza en 1), $x_{237}=1$ etc. Rellenamos los huecos con las respectivas progresiones aritméticas.

Answer 2

Es fácil ver que $$ x_n=((\ldots(k \mod 2+k) \mod 3+k) \mod 4) \ldots)\mod (n-1)+k) \mod n. $$ No estoy seguro de que exista una fórmula cerrada.