Bestimmung des längsten sich wiederholenden Zyklus in einer dezimalen Erweiterung

Question

Heute traf ich auf dieser Artikel über die Dezimalentwicklung und ich war sofort inspiriert, meine Lösung zu überarbeiten Projekt Euler-Problem 26 um dieses neue mathematische Wissen für eine effizientere Lösung (kein Brute-Forcing) einzubeziehen. 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 in dem Ausdruck "1/d" maximieren würde.

Ohne weitere Annahmen über das Problem zu treffen, die die Effizienz der Problemlösung weiter verbessern könnten, beschloss ich, bei der folgenden Lösung zu bleiben

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

die es mir ermöglicht, für jeden Wert von D den längsten sich wiederholenden Zyklus (t) und den Startpunkt des Zyklus (s) zu finden.

Das Problem ist der eksponentiale Teil der Gleichung, da dieser extrem große Werte erzeugt, bevor sie durch die Verwendung von Modulus reduziert werden. Kein Integralwert kann diese großen Werte verarbeiten, und die Fließkommadatentypen scheinen falsch zu rechnen.

Ich verwende derzeit diesen Code:

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 irgendwann "(10^47) mod 983" berechnet, was zu 783 führt, was nicht das richtige Ergebnis ist. Das korrekte Ergebnis hätte 732 lauten müssen. Ich nehme an, dass es daran liegt, dass ich ganzzahlige Datentypen verwende und dies zu einem Überlauf führt. Ich habe versucht, stattdessen double zu verwenden, aber das ergab noch seltsamere Ergebnisse.

Welche Möglichkeiten habe ich also?

Answer 1

Anstatt ^ zu verwenden, um Ihre Potenzen zu tun, würde ich eine for-Schleife mit Multiplikation und dann die mod der Zahl, wie Sie gehen, indem Sie eine bedingte zu überprüfen, ob die Zahl berechnet ist größer als die mod. Dies hilft, die Zahlen kleiner zu halten und innerhalb des Bereichs der Mod-Zahl.

Answer 2

Ich gebe Ihnen einen Hinweis auf meine eigene Lösung für dieses Problem.

Bei jeder dezimalen Erweiterung des Bruchs erhält man einen Rest, der, wenn man ihn mit der aktuellen Dezimalstelle multipliziert, eine ganze Zahl ist. Da dieser Rest alles ist, was Sie brauchen, um die nächste Dezimalentwicklung zu bestimmen, können Sie ihn verwenden, um Vorhersagen über die folgende Entwicklung zu machen.

Answer 3

Siehe meinen Beitrag zu dieser anderen Frage, Ermittlung der n-ten Stelle eines Bruchs finden Sie vielleicht einige nützliche Hinweise, was Sie ausprobieren können. (Ich glaube, die Antwort ist die größte Primzahl kleiner als 1000.) (Korrektur: die größte Primzahl oder Carmichael-Nummer weniger als 1000).