Mein Problem ist folgendes: Ich habe eine große Folge von Zahlen. Ich weiß, dass es nach einiger Zeit periodisch wird - das heißt, es gibt k Zahlen am Anfang der Sequenz, und dann gibt es m weitere Zahlen, die sich für den Rest der Sequenz wiederholen. Um dies deutlicher zu machen, könnte die Sequenz folgendermaßen aussehen: [1, 2, 5, 3, 4, 2, 1, 1, 3, 2, 1, 1, 3, 2, 1, 1, 3 , ...], wobei k 5 und m 4 ist und der Wiederholungsblock dann [2, 1, 1, 3] ist. Wie aus diesem Beispiel hervorgeht, kann der größere Block sich wiederholende Bits enthalten, sodass es nicht hilfreich ist, nur nach den ersten Wiederholungen zu suchen.

Ich weiß jedoch nicht, was k oder m sind - mein Ziel ist es, die Folge [a_1, a_2, ..., a_n] als Eingabe zu nehmen und die Folge [a_1, ..., a_k, [a_ (k +1), ..., a_ (k + m)]] - Grundsätzlich wird die längere Sequenz abgeschnitten, indem der Großteil davon als Wiederholungsblock aufgeführt wird.

Gibt es einen effizienten Weg, um dieses Problem zu lösen? Wahrscheinlich schwieriger, aber rechnerisch idealer - ist es möglich, dies zu tun, während ich die fragliche Sequenz generiere, so dass ich eine minimale Menge generieren muss? Ich habe mir andere, ähnliche Fragen auf dieser Site angesehen, aber sie scheinen sich alle mit Sequenzen zu befassen, ohne dass ein nicht wiederholendes Bit anfängt, und oft ohne sich um interne Wiederholungen sorgen zu müssen.

Wenn es hilft / nützlich wäre, kann ich auch erklären, warum ich das betrachte und wofür ich es verwenden werde.

Vielen Dank!

EDITS: Zunächst hätte ich erwähnen sollen, dass ich nicht weiß, ob die Eingabesequenz genau am Ende eines wiederholten Blocks endet.

Das reale Problem, an dem ich zu arbeiten versuche, besteht darin, einen schönen Ausdruck in geschlossener Form für fortgesetzte Brucherweiterungen (CFEs) von quadratischen Irrationalen (eigentlich der negative CFE) zu schreiben. Es ist sehr einfach, Teilquotienten * für diese CFEs mit beliebiger Genauigkeit zu generieren. Irgendwann wird jedoch das Ende der CFE für ein quadratisches Irrational zu einem sich wiederholenden Block. Ich muss mit den Teilquotienten in diesem Wiederholungsblock arbeiten.

Meine aktuellen Gedanken sind folgende: Vielleicht kann ich einige der vorgeschlagenen Algorithmen von rechts anpassen, um mit einer dieser Sequenzen zu arbeiten. Alternativ gibt es vielleicht einen Beweis dafür, warum quadratische Irrationalwerte periodisch sind, der mir hilft, zu erkennen, warum sie sich wiederholen, und der mir hilft, einige einfache Kriterien zu finden, die ich überprüfen kann.

* Wenn ich eine fortgesetzte Brucherweiterung als [a_0, a_1, ...] schreibe, beziehe ich mich auf die a_i's als Teilquotienten.

Einige Hintergrundinformationen für Interessierte finden Sie hier:http://en.wikipedia.org/wiki/Periodic_continued_fraction