Secuencias enfoque Criptográfico

[fzp]

Pues -una vez más- tengo que autocorregirme. Dije antes:

Así que en este segundo caso mi enfoque es el mismo que ya dije en mi primer mensaje: no existe forma (o al menos a mi no se me ocurre) de encontrar el término general de una sucesión de números naturales, aunque se sepa que corresponden a una fórmula polinómica.

Pues ahora he visto que sí que se puede. He estado dándole vueltas al asunto y me parece que sí que hay una forma. Aunque, éso si, nos tienen que dar un número mínimo de elementos de la sucesión de la fórmula polinómica, y ese número mínimo es: suponiendo que el máximo exponente de ese polinomio es "k" (n^k) nos tendrán que dar como mínimo k + 2 términos de la sucesión.

Desde luego no he conseguido la demostración general, pero he probado varios casos particulares y parece que sí que funciona. La cosa es que me dió por probar cosas en una hoja de cálculo, y me dió por por poner en una columna los términos de una sucesión, y al lado poner otra columna con las diferencias entre términos 2º-1º, 3º-2º, 4º-3º,... etc. Por ver si variban o no. Y luego seguí haciéndolo con columnas adyacentes respecto de la columna anterior. Y en todas se llega a una columna en que las diferencias entre términos (de la columna anterior) son una constante. Y cuando se llega a ese punto, el número de columnas que hemos tenido que hacer es siempre igual al máximo exponente del polinomio que da origen a la sucesión de números.

Voy a explicarlo mas detalladamente y luego pongo un ejemplo que se pueda seguir. El método es el siguiente. Yo lo he hecho con una hoja de cálculo -pero igual se podría programar-. Pones en una columna los términos de la sucesión que te han dado, haces una columna al lado (a la derecha) con las restas: 2º término - 1º término, 3º término - 2º término; y así sucesívamente. Y después repites la operación con otra columna nueva a la derecha de la misma forma: 3º término - 2º término, 4º término - 3º término, ... etc. Pues bien, llega un momento en que en la nueva columna que está haciendo todos los términos son iguales. Ahí es dónde encuentras el exponente máximo de tu polinomio (en n). Si has necesitado "k" columnas tu polinomio tendrá como exponente máximo (k-1); ésto es así debido a que hay un exponente 0. Entonces, si las constantes se producen en la columna 9ª quiere decir que tu polinomio tendrá como máximo exponente 8 (0,1,2...8). En general, si tienes "k+1" columnas, sabes que tu polinomio tiene exponentes entre 0,1,... k.

Una vez que has llegado a ese punto ya sabes que tu fórmula polinómica es del tipo:
a0*n^0 + a1*n^1+ a2*n^2+... +ak*n^k

A partir de ahí cómo puedes calcular todas las potencias de los números naturales (n = 1, 2, 3,...) puedes plantear un sistema de ecuaciones lineales c donde las incónitas son a0, a1, a2,... y los valores que hacen que se cumplan las ecuaciones son los valores que te han dado como términos de la sucesión.

Sé que así es un poco complicado, pongo un ejemplo.

He preparado una función polinómica  (4*n^5 - 3*n^2) que indico en la siguiente imagen:



En ella indico en la columna A los números naturales y en la columna B los términos de la sucesión (los que nos darían como datos: 1, 116, 945, 4048,...).

Pues bien a partir de esa columna B que nos dan como dato, nosotros hacemos una columna C donde escrimos las diferencias entre términos consecutivos: C3 = B3 - B2; C4 = B4 - B3; C5 = B5 - B4;...

Ahora volvemos a hacer lo mismo en una nueva columna D con respecto a los datos de la columna C:
D4 = C4 - C3; D5 = C5 - C4;...

Y así sucesívamente... ¿hasta cuando? hasta que una columna nos de una constante. En este caso la columna G ya nos da como resultado de las diferencias de la columna anterior un valor constante (480). Ahí paramos de hacer más columnas.

Pues bien como tenemos 6 columnas (contando desde la 1ª en que nos dieron los datos de la sucesión), quiere decirse que nuestro exponente máximo es 6 - 1 = 5. Ello es porque también hay un exponente 0. Por tanto nuestra fórmula polinómica tiene que ser del tipo:
sn = a0 + a1n^1 + a2n^2 + a3n^3 + a4n^4 + a5n^5
siendo sn el término general de la sucesión.

Entonces, como podemos calcular las distintas potencias de n^1, n^2,... para n=1, n=2,...
con 6 incógnitas (a0, a1, a2, a3, a4, a5) quiere decirse que podemos montar un sistema de 6 ecuaciones lineales con 6 incógnitas.

Eso lo pongo en la siguiente imagen:



En ella he expresado en forma matrical el sistema de ecuaciones lineales:
-en A24-A29 los nºs naturales
-en B23-G23 los exponentes (0-5)
-en B24-G29 la matriz de coeficientes del sistema (los productos de los nºs naturales por los exponentes)
-en H24-H29 las incógnitas
-en I24-I29 los valores que resuelven el sistema de ecuaciones... que a su vez son los que nos han dado como datos

Ahora la resolución del sistema es bastante fácil dado que Calc (LibreOffice) ofrece una función que nos da directamente la matriz inversa de otra dada. Esta matriz inversa nos la la Calc en B31-G36. Y ya no hay nada más que multiplicar esta matriz por la de los valores que resuelven el sistema (I24-I29), cosa que también Calc nos proporciona una función de matrices para hacerlo por nosotros.

El resultado está en I31-I36. Como puede verse los valores no son totalmente exactos. Es el problema de la resolución de matrices, que los errores de cálculo son acumulativos. Pero puede verse que los valores con exponentes -10, -11, -12 son prácticamente = 0. Y que nos queda entonces que los valores de los exponentes n^2 y n^5 son, respectivamente: -3 y 4. Como en la ecuación original de la que partimos.

Como digo, no tengo una demostración general de que ésto sea siempre así, pero en los casos particulares que he visto, funciona. Parece que que en cada columna de diferencias se van perdiendo los terminos de exponentes de mayor a menor hasta que en la última columna nos aparece el exponente 0 y éso da lugar a una constante. Pero ésto son sólo especulaciones mías.

El porqué nos tienen que dar al menos k+2 términos de la sucesión (siendo k el valor del exponente máximo. Pues porque tendremos exponentes desde 0 hasta k (k+1) y porque necesitaremos al menos un valor más para concluir que en la última columna de la derecha se repite el valor. Si sólo tuviéramos el primer valor donde aparece la constane no lo podríamos saber, necesitamos al menos un término más para saber que se repite y que, por tant, es constante.

EDITO: ya me he dado cuenta de porqué se van reduciendo los eponentes en cada columna a la derecha. Al restar un elelmento de su anterior estamos restando un polinomio de n con exponentes 0, 1, 2,..., k de otro (n+1) con los mismos coeficientes. Ello hace que estemos restando un término en ak*n^k de otro término ak*(n+1)^k. Pero, a su vez el término ak(n+1)^k puede escribirse cómo: ak*n^k + otro-polinomio-de-grado-(k-1). Con lo cual los términos ak*n^k se cancelan y por eso en la columna de la derecha solo quedarán exponentes (k-1). Al ir repitiendo en las sucesivas columnas de la derecha la misma operación, van desapareciendo los sucesivos exponente hasta quedar exponente 0 y por éso al final queda una constante, y las veces que hemos tenido que repetir la operación nos indica el exponente máximo del polinomio.