🔢 mathematics

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

Cet article présente un algorithme amélioré pour compter les permutations de $\mathbb{Z}/n\mathbb{Z}$ avec des sommes partielles distinctes, calculant spécifiquement les résultats pour $n=20$ et $n=22$ , tout en établissant une bijection avec une suite connue qui permet la dérivation de nouveaux termes.

Auteurs originaux : Quinn Baker, Amy Feaver

Publié 2026-07-27

📖 4 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Quinn Baker, Amy Feaver

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous soyez à une fête immense où chaque personne porte un numéro unique sur son t-shirt, allant de 0 jusqu'à une limite spécifique. L'hôte veut disposer les invités en une seule file pour une photo, mais il y a une règle délicate : au fur et à mesure que vous décomptez les nombres rencontrés, vous devez tenir un cumul des nombres que vous avez vus jusqu'à présent. La règle est la suivante : chaque fois que vous ajoutez une nouvelle personne à votre cumul, le nouveau total doit être un nombre que vous n'avez pas encore vu dans toute la file. Si vous atteignez un total que vous avez déjà compté, la file est brisée et la photo est gâchée. Ce n'est pas seulement un jeu de fête ; c'est un casse-tête profond dans le monde des mathématiques appelé « théorie des groupes », qui traite spécifiquement de la manière dont nous pouvons ordonner des nombres en cercle (comme les heures sur une horloge) afin que nos totaux cumulés ne se répètent jamais avant d'avoir utilisé chaque nombre exactement une fois. Les mathématiciens s'intéressent à cela car cela les aide à comprendre les structures cachées de symétrie et d'ordre dans l'univers, et trouver ces files spéciales est étonnamment difficile, comme essayer de trouver une aiguille précise dans une botte de foin qui change constamment de forme.

Cet article porte sur une équipe de mathématiciens qui a trouvé une façon beaucoup plus intelligente de résoudre ce casse-tête du « total cumulé » pour certains types de cercles numériques. Ils se sont concentrés sur des cercles ayant un nombre pair d'emplacements, comme une horloge de 20 heures ou de 22 heures. Par le passé, pour découvrir combien de files valides existent pour ces cercles, les ordinateurs devaient vérifier presque toutes les dispositions possibles une par une. C'était comme essayer de trouver une bonne photo en demandant à chaque combinaison possible de personnes de se mettre en ligne, ce qui prend un temps infini et devient impossible à mesure que la fête s'agrandit. Les auteurs, Baker et Feaver, ont introduit un nouvel algorithme qui agit comme un videur super intelligent. Au lieu d'attendre la fin de la file pour voir si la photo est gâchée, ce videur vérifie le total cumulé après chaque arrivée de personne. Dès que le videur voit un total qui est déjà apparu, il arrête immédiatement la croissance de cette file. Ils réalisent que si une file courte est brisée, alors chaque file longue commençant par ce même début brisé est également vouée à l'échec. En coupant ainsi ces « mauvaises » branches tôt, ils économisent un temps massif.

En utilisant cette méthode efficace, l'équipe a calculé le nombre exact de files valides pour des cercles de 20 et 22 emplacements. Ils ont découvert que pour un cercle de 20 emplacements, il existe exactement 5 074 931 072 façons d'organiser les invités. Pour un cercle de 22 emplacements, le nombre bondit à un chiffre colossal de 298 557 044 000. Ces nombres étaient si grands qu'ils ont dû être vérifiés indépendamment par un autre mathématicien, Bert Dobbelaere, pour s'assurer qu'ils étaient corrects. L'article prouve également un lien fascinant entre ces files de « total cumulé » et un autre concept appelé « ensembles de différences », montrant que compter l'un revient exactement à compter l'autre. Cette preuve leur permet d'utiliser les propriétés de l'un pour résoudre l'autre, doublant ainsi leur efficacité.

Les auteurs sont très confiants dans ces chiffres car ils sont dérivés d'une preuve mathématique rigoureuse et d'une recherche informatique qui élimine systématiquement les options impossibles. Cependant, ils précisent avec prudence que, bien que leur méthode soit la plus rapide connue pour compter ces arrangements, le problème reste incroyablement difficile. À mesure que le nombre d'emplacements sur le cercle augmente, le nombre de dispositions possibles croît si vite que même leur videur intelligent ne peut plus suivre indéfiniment. Ils suggèrent que le ratio des files valides par rapport à toutes les files possibles diminue de plus en plus, chutant d'environ dix fois pour chaque étape supplémentaire de taille. Bien qu'ils n'aient pas trouvé de formule magique pour prédire la réponse pour n'importe quelle taille instantanément, leur travail prouve qu'en étant astucieux sur le moment où arrêter la recherche, nous pouvons repousser les limites de nos connaissances bien plus loin. Ils nous laissent avec l'idée que la meilleure voie à suivre pourrait être de trouver davantage de ces « raccourcis intelligents » pour mapper quelques solutions connues vers toutes les autres, mais pour l'instant, leur nouvel algorithme est l'outil le plus puissant dont nous disposons pour compter ces chefs-d'œuvre mathématiques.

Résumé Technique : Un algorithme plus efficace pour trouver le nombre de permutations de $\mathbb{Z}/n\mathbb{Z}$ avec des sommes partielles distinctes

Énoncé du Problème
Cet article traite de l'énumération de permutations spécifiques au sein du groupe additif des entiers modulo $n$ ( $\mathbb{Z}/n\mathbb{Z}$ ), où $n$ est un entier pair. Le problème central consiste à compter le nombre de permutations $\sigma = (\sigma_0, \sigma_1, \dots, \sigma_{n-1})$ telles que l'ensemble des sommes partielles (ou « factorielles » dans le contexte du groupe) soient toutes distinctes. Plus précisément, l'article se concentre sur la séquence A141599 de l'Encyclopédie des séquences en ligne (OEIS), qui compte le nombre de « ensembles de différences » pour les permutations de $\mathbb{Z}/2k\mathbb{Z}$ avec des différences distinctes.

Une permutation possède des différences distinctes si l'ensemble des valeurs $d_i \equiv \sigma_i - \sigma_{i-1} \pmod n$ pour $1 \le i \le n-1$ contient chaque élément non nul de $\mathbb{Z}/n\mathbb{Z}$ exactement une fois. Les auteurs notent que de telles permutations n'existent que lorsque $n$ est pair. Le défi computationnel réside dans le fait que le nombre total de permutations ( $n!$ ) croît de manière factorielle, rendant l'énumération par force brute infaisable pour des $n$ plus grands.

Méthodologie
Les auteurs proposent un algorithme de retour sur trace (backtracking) récursif qui améliore considérablement les approches de force brute précédentes en élagant l'espace de recherche précocement. La méthodologie repose sur trois piliers principaux :

Bijection entre Ensembles de Différences et Séquençages :
L'article établit une bijection formelle (Théorème 1) entre les « ensembles de différences avec des différences distinctes » et les « séquencages » de $\mathbb{Z}/n\mathbb{Z}$ . Un séquencement est défini comme une permutation où les sommes partielles $s(\sigma, i) = \sum_{j=0}^i \sigma_j$ sont toutes distinctes. La preuve démontre qu'un ensemble de différences $D_\tau = (d_1, \dots, d_{n-1})$ peut être associé à un séquencement $\sigma = (0, d_1, \dots, d_{n-1})$ , et vice versa. Cela permet aux auteurs de compter les séquencements plutôt que de compter directement les ensembles de différences.
Réduction de Symétrie par Multiplication :
En s'appuyant sur le Lemme 2, les auteurs utilisent la propriété selon laquelle si $\sigma$ est un séquencement et $r$ est un entier premier avec $n$ ( $\gcd(r, n) = 1$ ), alors le produit élément par élément $(r\sigma_0, r\sigma_1, \dots, r\sigma_{n-1})$ est également un séquencement. Cela permet à l'algorithme de calculer les séquencements pour une « branche » spécifique (permutations commençant par $0, 1$) et de multiplier ce compte par la fonction totient d'Euler $\phi(n/d)$ pour rendre compte des autres branches, plutôt que de les calculer individuellement.
Élagage de Branche Récursif (Algorithme 2) :
Le cœur du nouvel algorithme est une recherche récursive qui construit des permutations partielles. Contrairement aux méthodes de force brute précédentes qui validaient des permutations complètes, cet algorithme maintient un état de « sommes partielles » (partials).
- Logique d'élagage : Si l'ajout d'un nouvel élément à la permutation partielle résulte en une somme partielle déjà vue (ou égale à 0 prématurément), la branche est immédiatement abandonnée.
- Efficacité : Cela empêche l'algorithme d'explorer les $(n-k)!$ permutations qui étendraient une séquence partielle invalide. Par exemple, dans $\mathbb{Z}/20\mathbb{Z}$ , la séquence partielle $(0, 1, 19)$ produit une somme partielle de 0 à l'indice 2, ce qui est invalide ; l'algorithme rejette alors toute cette branche, économisant ainsi $17!$ appels potentiels à un validateur.

Contributions Clés

Nouveaux termes pour OEIS A141599 : En utilisant l'algorithme amélioré, les auteurs ont calculé les 10e, 11e et 12e termes de la séquence (correspondant à $n=20, 22, 24$ $n = 20, 22, 24$ ). Les valeurs sont :
- $n=20$ : 5 074 931 072
- $n=22$ : 298 557 044 000
- $n=24$ : 21 224 961 132 544
  Les 10e et 11e termes ont été vérifiés indépendamment par Bert Dobbelaere.
Unification Théorique : L'article fournit une preuve rigoureuse de la bijection entre les ensembles de différences et les séquencages, unifiant les résultats classiques (Gilbert, Gordon) avec l'approche computationnelle actuelle.
Optimisation Algorithmique : L'introduction de la recherche récursive par branche avec terminaison précoce basée sur les collisions de sommes partielles représente la méthode la plus efficace connue à ce jour pour ce problème de comptage spécifique.

Résultats et Analyse de Données
L'article présente des données (Tableaux 1 et 2) comparant le nombre de séquencements au nombre total de permutations ( $n!$ ) pour des $n$ pairs allant jusqu'à 22. Les résultats indiquent que le ratio de séquencements par rapport au total des permutations diminue strictement et rapidement à mesure que $n$ augmente, chutant d'environ un ordre de grandeur à chaque étape. Pour $n=22$ , le ratio est d'environ $2,66 \times 10^{-10}$ .

Cette preuve empirique soutient l'efficacité de la stratégie d'élagage. Comme les séquencements valides sont extrêmement rares au sein de l'espace de toutes les permutations, la génération et la validation de permutations complètes sont inefficaces. L'approche récursive, qui élimine immédiatement les chemins partiels invalides, s'aligne sur la rareté observée.

Signification et Revendications
Les auteurs affirment que leur algorithme est le plus efficace connu à ce jour pour calculer les termes de la séquence A141599. Ils soutiennent que bien que la complexité temporelle reste super-polynomiale (probablement pire que l'exponentielle mais meilleure que $O(n!)$ ), la technique d'élagage offre une « amélioration stricte » par rapport aux méthodes de force brute en évitant de gaspiller de la puissance de calcul sur des branches invalides.

L'article conclut modestement que les améliorations futures de l'algorithme de comptage sont probablement limitées à moins que de nouvelles transformations mathématiques ne puissent être identifiées. Plus précisément, ils suggèrent que les progrès futurs pourraient dépendre de l'identification d'un ensemble complet de transformations (au-delà de la multiplication par des entiers premiers avec $n$ ) capables de mapper un petit ensemble de séquencings connus vers l'ensemble complet pour un $n$ donné, contournant ainsi potentiellement le besoin d'une recherche exhaustive. Cependant, ils ne proposent pas de telles transformations dans ce travail, notant que l'approche récursive actuelle est l'état de l'art pour résoudre le problème tel qu'il est défini.

Articles similaires