Secuencia de Tribonacci módulo X

Question

La secuencia de Tribonacci satisface

$$T(n) = T(n-1) + T(n-2) + T(n-3)$$

con $T(0)=0$ , $T(1)=1$ , $T(2)=1$ . Necesito calcular $T(y) \mod 10000$ para $y > 2^{40}$ .

¿Cómo puedo hacer esto más rápido? Sé que esto es periódico en $(\mathbb{Z}/10000\mathbb{Z})^3$ pero no puedo encontrar el período.

¿Alguna sugerencia? Mi programa necesita mucho tiempo para calcular tales $T(y)$ .

Answer 1

Llame a $U(n) = (T(n),T(n+1),T(n+2))$ . La relación de recurrencia significa que para todo n $U(n+1) = f(U(n))$ donde $f$ es la transformación lineal que envía $(a,b,c)$ a $(b,c,a+b+c)$ .

Por lo tanto, para calcular $T(n)$ en lugar de calcular cada $T(i)$ para cada i, se puede calcular simplemente la transformación lineal $f^n$ aplicarlo a $U(0) = (0,1,1)$ para conseguir $U(n) = (T(n),T(n+1),T(n+2))$ .

Para calcular $f^{2^{40}}$ modulo 10000, escribir $f$ como una matriz con coeficientes en $\mathbb{Z}/10000\mathbb{Z}$ y cuadrarlo 40 veces.

Answer 2

Tienes razón en que la secuencia es periódica, y su período es menor que $(10^4)^3$ .

El siguiente pseudocódigo calculará la periodicidad. El argumento $m$ es el número respecto al cual se toma el módulo.

def TribonacciPeriod(m):
    a = 1; b = 1; c = 2 // manually do one iteration
    n = 1
    while (a != 0 or b != 1 or c != 1):
        tmp = (a + b + c) mod m
        a = b; b = c; c = tmp
        n += 1
    return n

Se garantiza que esto termine y devuelva un valor menor que $m^3$ .