Farey-Sequenzmanipulation

Question

Daher bin ich sehr neu in Mathematica und mache derzeit ein Projekt, bei dem eine bestimmte Funktion der Farey-Brüche berechnet wird. Das ist ein Intervall gegeben$I: (0,\alpha)$Ich möchte die Anzahl der unterschiedlichen Paare berechnen $i$,$j$ st $i-j$ $\in I$in einer normalisierten Liste von Farey-Fraktionen. Der Normalisierungsfaktor ist hier$\frac{1}{|F_d-1|}$, wo $|F_d|$ist die Größe der Liste der Farey-Brüche mit Nenner d. Wenn beispielsweise der Nenner 5 ist, lautet die normale Liste der Farey-Brüche$FareySequence[5]$, während die normalisierte Liste ist $|F_d-1|(FareySequence[5])$.

Unten ist mein Versuch, die Anzahl der verschiedenen Paare zu zählen $i,j$ die Teil einer normalisierten Farey-Sequenz sind, so dass $i-j<1$, wo $i>j$. Hier zähle ich es basierend auf Brüchen mit dem Nenner 1000. Es gibt 304193 solcher Brüche. Ich habe einen Zähler verwendet, bei dem jedes Mal eine Zählung hinzugefügt wird, wenn ein Paar vorhanden ist, dessen Differenz kleiner als 1 ist. Jedes Mal, wenn ich ihn ausführe, wird das Programm jedoch nie ausgewertet. Jede Hilfe wäre dankbar.

count = 0

For[i = 1, i < 304193, i++,
 
For[j = 1, j < i, j++,
 
 if[(304193 FareySequence[1000, i]) - (304193 FareySequence[1000, 
        j]) < 1, count ++, count = count ]
  
]
 ]

Print[count]

Answer 1

Hier ist eine Lösung, die schnell funktioniert:

FareySequence[1000] ist nur 304193 Elemente lang, ausreichend kurz genug, um im Speicher gespeichert zu werden. Berechnen Sie die Sequenz also nur einmal und greifen Sie dann auf die Elemente zu, um die Geschwindigkeit zu erhöhen.

fs = 304193*FareySequence[1000];

Beachten Sie dann, dass die Elemente von FareySequence monoton ansteigen. Wenn Sie also das Element fs [[i]] und das vorhergehende Element nehmen, hat fs [[i-1]] einen Abstand Vater von 1 von f [[i]], den Sie nicht haben Sie müssen keines der Elemente früher in der Sequenz testen. Anstatt j von 0 bis i zu testen, testen Sie j von i-1 nach unten und brechen Sie jedes Mal ab, wenn Ihre Bedingung nicht erfüllt ist.

For[
 i = 1, i < 304193, i++,
 For[j = (i - 1), j > 0, j--,
  If[(fs[[i]] - fs[[j]]) < 1, count++, Break[]]
  ];
 ]

Print[count]

232074

Dies ist in knapp 2 Sekunden abgeschlossen.

Hier ist eine mathematischere ('funktionale') Lösung, die nicht sehr schnell funktioniert:

Zuerst eine Funktion schreiben , die eine Folge nimmt dann nutzt die TakeWhilegesamte Sequenz mit Ausnahme des letzten Elements mit dem letzten Element für den Vergleich und brechen , wenn die Differenz zwischen den beiden Elementen zu durchqueren ist größer als lim, Lengthzählt die Länge dieser Liste.

countBelowWithin[seq_, lim_:1] := 
  Length@TakeWhile[Reverse[Most[seq]], Last[seq] - # < lim &];

Verwenden Sie dann Table, um Teilsequenzen der vollständigen Sequenz zu nehmen und an zu übergeben countBelowWithin. Die resultierende Tabelle gibt die Anzahl der Elemente an, die die Kriterien für diese TotalTeilsequenz erfüllt haben. Fügen Sie also die Elemente für die Gesamtzahl der Elemente hinzu, die die Kriterien erfüllen.

With[
 {a = fs[[;; 10000]]},
 Total[
  Table[
   countBelowWithin[a[[;; i]]]
   , {i, 2, Length@a}
   ]
  ]
 ]

Ich benutze das With, um einen Teil der Sequenz fszu Testzwecken zu isolieren .

Sehr oft kann die funktionale Lösung schneller sein - in diesem Fall nicht. Es ist oft weniger fehleranfällig, da Sie in größeren Konzepten als in Indizes denken können. In diesem Fall müssten Sie wahrscheinlich etwas mehr darüber nachdenken, wenn Sie eine funktionale Lösung suchen, die in angemessener Zeit funktioniert.

Wenn Sie mehr in dem Lernen interessieren, gibt es eine Menge von Grundlagen in hier Partalso ...[[;;]], Table, TakeWhile. Ich würde anfangen, nur die Dokumente zu diesem Thema sowie die Links anderer Poster zu lesen.

Answer 2

Eher ein ausführlicher Kommentar als eine Antwort ...

Wenn Sie das Limit Ihres iIterators auf etwas Kleines reduzieren , z. B. 10anstatt 304193, scheint der korrigierte Code (" IF" statt " if") gut zu funktionieren.

Versuche Folgendes:

count = 0;
For[i = 1, i < 10, i++,
 For[j = 1, j < i, j++,
  If[
   (304193 *FareySequence[1000, i]) - (304193 * FareySequence[1000, j]) < 1,
   count++, count = count]]]
Print[count]

welche Ausgänge: 18

Es scheint, dass das Setzen der iterativen Grenze von iat 304193nur eine enorme Anzahl von Auswertungen in den verschachtelten ForSchleifen erzeugt.

Ich denke, Sie können Ihr Ergebnis in weitaus kürzerer Zeit durch "funktionale Programmierung" (die wahre Stärke von Mathematica) als durch iterative Schleifen erzielen.

Das einfache Zuordnen der IFAnweisung zu den entsprechenden Bereichen wird wahrscheinlich sehr schnell. Führen Sie dann eine separate "Zählung" der Instanzen durch, die Sie identifizieren möchten.

Ich werde später am Tag darüber nachdenken und zurückkommen, wenn noch niemand eine Antwort gegeben hat.