Ermitteln längsten Wiederholungszyklus in einer Dezimal-Erweiterung

Question

Heute bin ich auf this article about decimal expansion gestoßen und ich wurde sofort inspiriert, meine Lösung auf Project Euler Problem 26 zu überarbeiten, um diese neuen Kenntnisse der Mathematik für eine effektivere Lösung (kein Brute Forcing) aufzunehmen. Kurz gesagt besteht das Problem darin, den Wert von d im Bereich von 1-1000 zu finden, der die Länge des sich wiederholenden Zyklus im Ausdruck "1/d" maximieren würde.

ohne weitere Annahmen über das Problem zu machen, die weiter die effecienty zur Lösung des Problems verbessern konnte habe ich beschlossen, mit

10^s=10^(s+t) (mod n) 

zu bleiben, die mir für jeden Wert von D ermöglicht die längste wiederholenden Zyklus zu finden (t) und der Ausgangspunkt für den Zyklus (die Zyklen).

Das Problem ist der exponentielle Teil der Gleichung, da dies extrem große Werte erzeugt, bevor sie durch Verwendung von Modulus reduziert werden. Kein ganzzahliger Wert kann mit diesen großen Werten umgehen, und die Gleitkommadatentypen scheinen falsch zu berechnen.

Ich verwende diesen Code zur Zeit:

Private Function solveDiscreteLogarithm(ByVal D As Integer) As Integer 
Dim NumberToIndex As New Dictionary(Of Long, Long)() 
Dim maxCheck As Integer = 1000 

For index As Integer = 1 To maxCheck 
    If (Not NumberToIndex.ContainsKey((10^index) Mod D)) Then 
     NumberToIndex.Add((10^index) Mod D, index) 
    Else 
     Return index - NumberToIndex((10^index) Mod D) 
    End If 
Next 

Return -1 
End Function 

die an einem gewissen Punkt berechnen "(10^47) mod 983" in 783 ergibt, die nicht das korrekte Ergebnis ist. Das richtige Ergebnis hätte 732 sein sollen. Ich nehme an, dass es liegt, weil ich integrale Datentypen verwende und es Überlauf verursacht. Ich versuchte stattdessen, double zu verwenden, aber das gab noch seltsamere Ergebnisse.

Was sind meine Optionen?

Answer 1

Anstatt^zu benutzen, um Ihre Kräfte zu tun, würde ich eine for-Schleife mit Multiplikation machen und dann die Mod der Zahl, wie Sie gehen, indem Sie eine Bedingung verwenden, um zu überprüfen, ob die berechnete Zahl größer ist als die Mod. Dies hilft, die Zahlen kleiner und innerhalb der Reichweite deiner Mod-Nummer zu halten.

Answer 2

Ich gebe Ihnen einen Tipp von meiner eigenen Lösung dazu.

Mit jeder Dezimal-Erweiterung des Bruches erhalten Sie einen Rest, der, wenn er mit der aktuellen Dezimalstelle multipliziert wird, eine ganze Zahl ist. Da dieser Rest alles ist, was Sie benötigen, um die nächste Dezimal-Erweiterung zu bestimmen, können Sie damit Vorhersagen über die nachfolgende Erweiterung treffen.

Answer 3

Siehe meinen Beitrag für diese andere Frage, getting the nth digit of a fraction, können Sie einige nützliche Hinweise darauf finden, was Sie versuchen sollten. (Methinks die Antwort ist die größte Primzahl weniger als 1000.) (Korrektur: die größte Primzahl oder Carmichael number weniger als 1000.)