Meu problema é este: eu tenho uma grande seqüência de números. Eu sei que, depois de algum ponto, ela se torna periódica - isto é, existem números k no começo da sequência, e então há mais números que se repetem para o resto da sequência. Como exemplo para tornar isso mais claro, a sequência pode ser assim: [1, 2, 5, 3, 4, 2, 1, 1, 3, 2, 1, 1, 3, 2, 1, 1, 3 , ..., onde k é 5 e m é 4, e o bloco de repetição é então [2, 1, 1, 3]. Como fica claro neste exemplo, posso repetir bits dentro do bloco maior, portanto, não ajuda apenas procurar as primeiras instâncias de repetição.

No entanto, eu não sei o que k ou m são - meu objetivo é pegar a sequência [a_1, a_2, ..., a_n] como entrada e saída da sequência [a_1, ..., a_k, [a_ (k +1), ..., a_ (k + m)]] - basicamente truncando a seqüência mais longa listando a maioria dela como um bloco repetitivo.

Existe uma maneira eficiente de fazer esse problema? Além disso, provavelmente mais difícil, mas mais ideal computacionalmente - é possível fazer isso quando eu gerar a sequência em questão, de modo que eu tenha que gerar uma quantidade mínima? Eu olhei para outras questões semelhantes neste site, mas todas elas parecem lidar com seqüências sem o começo de bits não repetitivos, e muitas vezes sem ter que se preocupar com repetição interna.

Se isso ajuda / seria útil, eu também posso entender por que estou olhando para isso e para o que vou usá-lo.

Obrigado!

EDITS: Primeiro, eu deveria ter mencionado que eu não sei se a seqüência de entrada termina exatamente no final de um bloco repetido.

O problema do mundo real no qual estou tentando trabalhar é escrever uma expressão agradável de forma fechada para expansões de frações contínuas (CFEs) de irracionais quadráticas (na verdade, o CFE negativo). É muito simples gerar quocientes parciais * para estes CFEs em qualquer grau de precisão - no entanto, em algum momento a cauda do CFE para um irracional quadrático se torna um bloco repetitivo. Eu preciso trabalhar com os quocientes parciais neste bloco de repetição.

Meus pensamentos atuais são os seguintes: talvez eu possa adaptar alguns dos algoritmos sugeridos que funcionam a partir do direito de trabalhar com uma dessas seqüências. Alternativamente, talvez haja algo na prova de porque os irracionais quadráticos são periódicos que me ajudarão a ver por que eles começam a se repetir, o que me ajudará a criar alguns critérios fáceis de serem verificados.

* Se estou escrevendo uma expansão de fração continuada como [a_0, a_1, ...], refiro-me aos a_i's como quocientes parciais.

Algumas informações básicas podem ser encontradas aqui para os interessados:http://en.wikipedia.org/wiki/Periodic_continued_fraction