Mi problema es este: tengo una gran secuencia de números. Sé que, después de algún punto, se vuelve periódico, es decir, hay k números al principio de la secuencia, y luego hay m más números que se repiten para el resto de la secuencia. Como ejemplo para aclarar esto, la secuencia podría verse así: [1, 2, 5, 3, 4, 2, 1, 1, 3, 2, 1, 1, 3, 2, 1, 1, 3 , ...], donde k es 5 y m es 4, y el bloque que se repite es entonces [2, 1, 1, 3]. Como queda claro en este ejemplo, puedo repetir los bits dentro del bloque más grande, por lo que no ayuda buscar los primeros casos de repetición.

Sin embargo, no sé qué son k o m; mi objetivo es tomar la secuencia [a_1, a_2, ..., a_n] como entrada y generar la secuencia [a_1, ..., a_k, [a_ (k +1), ..., a_ (k + m)]] - básicamente truncando la secuencia más larga al enumerar la mayoría como un bloque que se repite.

¿Hay una manera eficiente de hacer este problema? Además, es probable que sea más difícil pero más ideal computacionalmente. ¿Es posible hacer esto cuando genero la secuencia en cuestión, de modo que tengo que generar una cantidad mínima? He mirado otras preguntas similares en este sitio, pero todas parecen lidiar con secuencias sin el bit inicial que no se repite, ya menudo sin tener que preocuparse por la repetición interna.

Si ayuda / sería útil, también puedo ver por qué estoy viendo esto y para qué lo usaré.

¡Gracias!

EDITOS: Primero, debería haber mencionado que no sé si la secuencia de entrada termina exactamente al final de un bloque repetido.

El problema del mundo real en el que estoy intentando trabajar es escribir una expresión bonita y de forma cerrada para expansiones de fracciones continuas (CFE) de irracionales cuadráticos (en realidad, la CFE negativa). Es muy simple generar cocientes parciales * para estos CFE con cualquier grado de precisión; sin embargo, en algún punto, la cola del CFE para un irracional cuadrático se convierte en un bloque que se repite. Necesito trabajar con los cocientes parciales en este bloque de repetición.

Mis pensamientos actuales son los siguientes: quizás pueda adaptar algunos de los algoritmos sugeridos que funcionan desde el derecho para trabajar con una de estas secuencias. Alternativamente, tal vez haya algo en la prueba de por qué los irracionales cuadráticos son periódicos que me ayudarán a ver por qué comienzan a repetirse, lo que me ayudará a encontrar algunos criterios fáciles de verificar.

* Si estoy escribiendo una expansión de fracción continua como [a_0, a_1, ...], me refiero a los a_i como cocientes parciales.

Aquí se puede encontrar información de fondo para aquellos interesados:http://en.wikipedia.org/wiki/Periodic_continued_fraction