🔢 mathematics

A More Efficient Algorithm for Finding the Number of Permutations of $\mathbb{ZZ}/n\mathbb{ZZ}$ with Distinct Partial Sums

Diese Arbeit präsentiert einen verbesserten Algorithmus zur Zählung von Permutationen von $\mathbb{Z}/n\mathbb{Z}$ mit distinkten partiellen Summen, wobei spezifisch Ergebnisse für $n=20$ und $n=22$ berechnet werden, während gleichzeitig eine Bijektion zu einer bekannten Folge etabliert wird, die die Ableitung neuer Terme ermöglicht.

Ursprüngliche Autoren: Quinn Baker, Amy Feaver

Veröffentlicht 2026-07-27

📖 4 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Quinn Baker, Amy Feaver

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind auf einer riesigen Party, bei der jeder eine einzigartige Nummer auf seinem Hemd trägt, die von 0 bis zu einer bestimmten Grenze reicht. Der Gastgeber möchte die Gäste in einer einzigen Schlange für ein Foto anordnen, aber es gibt eine knifflige Regel: Während Sie die Schlange entlanggehen, müssen Sie eine laufende Summe der Zahlen führen, die Sie bisher gesehen haben. Die Regel besagt, dass jedes Mal, wenn Sie eine neue Person zu Ihrer Summe hinzufügen, die neue Gesamtsumme eine Zahl sein muss, die Sie in der gesamten Schlange noch nicht zuvor gesehen haben. Wenn Sie eine Gesamtsumme erreichen, die Sie bereits gezählt haben, ist die Schlange unterbrochen und das Foto ist ruiniert. Dies ist nicht nur ein Partyspiel; es ist ein tiefgründiges Rätsel in der Welt der Mathematik namens „Gruppentheorie“, das sich speziell mit der Art und Weise befasst, wie wir Zahlen in einem Kreis (wie die Stunden auf einer Uhr) anordnen können, sodass unsere laufenden Summen sich niemals wiederholen, bis wir jede einzelne Zahl genau einmal verwendet haben. Mathematiker interessieren sich dafür, weil es ihnen hilft, die verborgenen Strukturen von Symmetrie und Ordnung im Universum zu verstehen, und das Finden dieser speziellen Linien ist überraschend schwer, wie der Versuch, eine bestimmte Nadel im Heuhaufen zu finden, der ständig seine Form verändert.

In dieser Arbeit geht es um ein Team von Mathematikern, das einen viel klügeren Weg gefunden hat, um dieses „laufende Summen“-Rätsel für bestimmte Arten von Zahlenkreisen zu lösen. Sie konzentrierten sich auf Kreise mit einer geraden Anzahl von Plätzen, wie etwa einen Kreis mit 20 oder 22 Stunden. In der Vergangenheit mussten Computer, um herauszufinden, wie viele gültige Linien für diese Kreise existieren, fast jede mögliche Anordnung der Gäste einzeln überprüfen. Das war so, als würde man versuchen, ein gutes Foto zu finden, indem man jede einzelne mögliche Kombination von Menschen fragt, die in einer Schlange stehen soll, was ewig dauert und bei größeren Partys unmöglich wird. Die Autoren, Baker und Feaver, führten einen neuen Algorithmus ein, der wie ein superintelligenter Türsteher fungiert. Anstatt erst am Ende der Schlange zu warten, um zu sehen, ob das Foto ruiniert ist, prüft dieser Türsteher die laufende Summe nach jedem einzelnen Gast, der hinzukommt. Soblich der Türsteher eine Gesamtsumme sieht, die bereits aufgetreten ist, stoppt er sofort das Wachstum dieser Linie. Sie erkannten, dass, wenn eine kurze Linie unterbrochen ist, auch jede lange Linie, die mit demselben fehlerhaften Anfang beginnt, zum Scheitern verurteilt ist. Durch das vorzeitige Abschneiden dieser „schlechten“ Zweige sparen sie eine enorme Menge an Zeit.

Mit dieser effizienten Methode berechnete das Team die exakte Anzahl der gültigen Linien für Kreise mit 20 und 22 Plätzen. Sie fanden heraus, dass es für einen Kreis mit 20 Plätzen genau 5.074.931.072 Möglichkeiten gibt, die Gäste anzuordnen. Für einen Kreis mit 22 Plätzen springt die Zahl auf die gewaltige Zahl 298.557.044.000. Diese Zahlen waren so groß, dass sie von einem anderen Mathematiker, Bert Dobbelaere, unabhängig verifiziert werden mussten, um sicherzustellen, dass sie korrekt sind. Die Arbeit beweist auch eine faszinierende Verbindung zwischen diesen „laufenden Summen“-Linien und einem anderen Konzept namens „Differenzmengen“, wobei sie zeigt, dass das Zählen des einen exakt dasselbe ist wie das Zählen des anderen. Dieser Beweis ermöglicht es ihnen, die Eigenschaften des einen zu nutzen, um das andere zu lösen, was ihre Effizienz effektiv verdoppelt.

Die Autoren sind sehr zuversichtlich in diese Zahlen, da sie aus einem strengen mathematischen Beweis und einer Computersuche abgeleitet sind, die systematisch unmögliche Optionen ausschließt. Sie weisen jedoch vorsichtig darauf hin, dass ihre Methode zwar der schnellste bekannte Weg ist, um diese Anordnungen zu zählen, das Problem aber immer noch unglaublich schwierig ist. Wenn die Anzahl der Plätze auf dem Kreis steigt, wächst die Anzahl der möglichen Anordnungen so schnell, dass selbst ihr intelligenter Türsteher nicht ewig mithalten kann. Sie legen nahe, dass das Verhältnis von gültigen Linien zu allen möglichen Linien immer kleiner wird und mit jedem Schritt in der Größe um etwa den Faktor zehn sinkt. Obwohl sie keine magische Formel gefunden haben, um die Antwort für jede Größe sofort vorherzusagen, beweist ihre Arbeit, dass wir durch kluges Vorgehen beim Stoppen der Suche die Grenzen dessen, was wir wissen, viel weiter verschieben können. Sie lassen uns mit dem Gedanken zurück, dass der beste Weg nach vorn darin bestehen könnte, mehr dieser „smarten Abkürzungen“ zu finden, um einige bekannte Lösungen auf alle anderen abzubilden, aber für den Moment ist ihr neuer Algorithmus das leistungsfähigste Werkzeug, das wir haben, um diese mathematischen Meisterwerke zu zählen.

Technisches Resümee: Ein effizienterer Algorithmus zur Bestimmung der Anzahl der Permutationen von $\mathbb{Z}/n\mathbb{Z}$ mit distinkten Teilsummen

Problemstellung
Diese Arbeit befasst sich mit der Enumeration spezifischer Permutationen innerhalb der additiven Gruppe der ganzen Zahlen modulo $n$ ( $\mathbb{Z}/n\mathbb{Z}$ ), wobei $n$ eine gerade Ganzzahl ist. Der Kern des Problems liegt in der Zählung der Anzahl der Permutationen $\sigma = (\sigma_0, \sigma_1, \dots, \sigma_{n-1})$ , sodass die Menge der Teilsummen (oder „Fakultäten“ im Kontext der Gruppe) alle distinkt sind. Konkret konzentriert sich die Arbeit auf die Folge A141599 in der On-Line Encyclopedia of Integer Sequences (OEIS), welche die Anzahl der „Differenzmengen“ für Permutationen von $\mathbb{Z}/2k\mathbb{Z}$ mit distinkten Differenzen zählt.

Eine Permutation besitzt distinkte Differenzen, wenn die Menge der Werte $d_i \equiv \sigma_i - \sigma_{i-1} \pmod n$ für $1 \le i \le n-1$ jedes nicht-null Element von $\mathbb{Z}/n\mathbb{Z}$ genau einmal enthält. Die Autoren stellen fest, dass solche Permutationen nur existieren, wenn $n$ gerade ist. Die rechnerische Herausforderung besteht darin, dass die Gesamtzahl der Permutationen ( $n!$ ) faktoriell wächst, was eine Brute-Force-Enumeration für größere $n$ unmöglich macht.

Methodik
Die Autoren schlagen einen rekursiven Backtracking-Algorithmus vor, der durch das frühzeitige Beschneiden des Suchraums herkömmliche Brute-Force-Ansätze signifikant verbessert. Die Methodik stützt sich auf drei Hauptsäulen:

Bijektion zwischen Differenzmengen und Sequenzierungen:
Die Arbeit etabliert eine formale Bijektion (Theorem 1) zwischen „Differenzmengen mit distinkten Differenzen“ und „Sequenzierungen“ von $\mathbb{Z}/n\mathbb{Z}$ . Eine Sequenzierung ist definiert als eine Permutation, bei der die Teilsummen $s(\sigma, i) = \sum_{j=0}^i \sigma_j$ alle distinkt sind. Der Beweis zeigt, dass eine Differenzmenge $D_\tau = (d_1, \dots, d_{n-1})$ auf eine Sequenzierung $\sigma = (0, d_1, \dots, d_{n-1})$ abgebildet werden kann und umgekehrt. Dies ermöglicht es den Autoren, Sequenzierungen zu zählen, anstatt Differenzmengen direkt zu zählen.
Symmetriereduktion durch Multiplikation:
Unter Ausnutzung von Lemma 2 verwenden die Autoren die Eigenschaft, dass falls $\sigma$ eine Sequenzierung ist und $r$ eine ganze Zahl ist, die teilerfremd zu $n$ ist ( $\gcd(r, n) = 1$ ), das elementweise Produkt $(r\sigma_0, r\sigma_1, \dots, r\sigma_{n-1})$ ebenfalls eine Sequenzierung ist. Dies erlaubt dem Algorithmus, die Sequenzierungen für einen spezifischen „Zweig“ (Permutationen beginnend mit $0, 1$) zu berechnen und diesen Wert mit der Eulerschen Totientfunktion $\phi(n/d)$ zu multiplizieren, um andere Zweige zu berücksichtigen, anstatt diese einzeln zu berechnen.
Rekursive Verzweigung (Algorithmus 2):
Der Kern des neuen Algorithmus ist eine rekursive Suche, die partielle Permutationen konstruiert. Im Gegensatz zu bisherigen Brute-Force-Methoden, die vollständige Permutationen validierten, pflegt dieser Algorithmus einen Zustand von „Teilsummen“ (partials).

Pruning-Logik: Wenn das Hinzufügen eines neuen Elements zur partiellen Permutation zu einer Teilsumme führt, die bereits gesehen wurde (oder vorzeitig 0 ergibt), wird der Zweig sofort abgebrochen.
Effizienz: Dies verhindert, dass der Algorithmus die $(n-k)!$ Permutationen exploriert, die eine ungültige partielle Sequenz erweitern würden. Beispielsweise liefert die partielle Sequenz $(0, 1, 19)$ in $\mathbb{Z}/20\mathbb{Z}$ eine Teilsumme von 0 an Index 2, was ungültig ist; der Algorithmus verwirft diesen gesamten Zweig und spart damit $17!$ potenzielle Aufrufe an einen Validator.

Wesentliche Beiträge

Neue Terme für OEIS A141599: Unter Verwendung des verbesserten Algorithmus berechneten die Autoren den 10., 11. und 12. Term der Folge (entsprechend $n=20, 22, 24$ $n = 20, 22, 24$ ). Die Werte sind:
- $n=20$ : 5.074.931.072
- $n=22$ : 298.557.044.000
- $n=24$ : 21.224.961.132.544
  Der 10. und 11. Term wurden unabhängig von Bert Dobbelaere verifiziert.
Theoretische Vereinheitlichung: Die Arbeit liefert einen rigorosen Beweis für die Bijektion zwischen Differenzmengen und Sequenzierungen und vereinheitlicht klassische Ergebnisse (Gilbert, Gordon) mit dem aktuellen rechnerischen Ansatz.
Algorithmische Optimierung: Die Einführung der rekursiven Verzweigungssuche mit früher Terminierung bei Kollisionen der Teilsummen stellt die effizienteste bekannte Methode für dieses spezifische Zählproblem dar.

Ergebnisse und Datenanalyse
Die Arbeit präsentiert Daten (Tabellen 1 und 2), welche die Anzahl der Sequenzierungen mit der Gesamtzahl der Permutationen ( $n!$ ) für gerade $n$ bis zu 22 vergleichen. Die Ergebnisse zeigen, dass das Verhältnis von Sequenzierungen zu Gesamtpermutationen mit steigendem $n$ streng und schnell abnimmt und mit jedem Schritt um etwa eine Größenordnung sinkt. Für $n=22$ beträgt das Verhältnis etwa $2,66 \times 10^{-10}$ .

Diese empirische Evidenz stützt die Wirksamkeit der Pruning-Strategie. Da gültige Sequenzierungen innerhalb des Raums aller Permutationen extrem spärlich gesät sind, ist das Generieren und Validieren vollständiger Permutationen ineffizient. Der rekursive Ansatz, der ungültige partielle Pfade sofort eliminiert, korrespondiert mit der beobachteten Spärlichkeit.

Bedeutung und Ansprüche
Die Autoren behaupten, dass ihr Algorithmus der effizienteste bekannte ist, um die Terme der Folge A141599 zu berechnen. Sie argumentieren, dass die Zeitkomplexität zwar super-polynomiell bleibt (wahrscheinlich schlechter als exponentiell, aber besser als $O(n!)$ ), die Pruning-Technik jedoch eine „strikte Verbesserung“ gegenüber Brute-Force-Methoden darstellt, indem sie verschwendete Berechnungen auf ungültigen Zweigen vermeidet.

Die Arbeit schließt bescheiden mit der Feststellung, dass weitere Verbesserungen des Zählalgorithmus unwahrscheinlich sind, sofern keine neuen mathematischen Transformationen identifiziert werden können. Insbesondere deuten sie darauf an, dass künftige Fortschritte von der Identifizierung eines vollständigen Satzes von Transformationen abhängen könnten (über die Multiplikation mit teilerfremden Ganzen hinaus), die in der Lage wären, eine kleine Menge bekannter Sequenzierungen auf die gesamte Menge für ein gegebenes $n$ abzubilden, wodurch die Notwendigkeit einer exzessiven Suche potenziell vollständig umgangen werden könnte. Sie schlagen jedoch keine solchen Transformationen in dieser Arbeit vor und merken an, dass der aktuelle rekursive Ansatz den Stand der Technik für die Lösung des definierten Problems darstellt.

Mehr davon