🔢 mathematics

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

Este artículo presenta un algoritmo mejorado para contar permutaciones de $\mathbb{Z}/n\mathbb{Z}$ con sumas parciales distintas, calculando específicamente los resultados para $n=20$ y $n=22$ , al tiempo que establece una biyección con una secuencia conocida que permite la derivación de nuevos términos.

Autores originales: Quinn Baker, Amy Feaver

Publicado 2026-07-27

📖 4 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Quinn Baker, Amy Feaver

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás en una fiesta masiva donde cada persona tiene un número único en su camiseta, que va desde el 0 hasta un límite específico. El anfitrión quiere organizar a los invitados en una sola fila para una foto, pero hay una regla complicada: a medida que caminas por la fila, debes llevar una cuenta acumulada de los números que has visto hasta el momento. La regla es que cada vez que sumas a una nueva persona a tu cuenta, el nuevo total debe ser un número que no hayas visto antes en toda la fila. Si alcanzas un total que ya habías contado, la fila se rompe y la foto se arruina. Esto no es solo un juego de fiesta; es un rompecabezas profundo en el mundo de las matemáticas llamado "teoría de grupos", específicamente relacionado con cómo podemos ordenar números en un círculo (como las horas en un reloj) de modo que nuestras sumas acumuladas nunca se repitan hasta que hayamos usado cada número exactamente una vez. A los matemáticos les importa esto porque ayuda a comprender las estructuras ocultas de simetría y orden en el universo, y encontrar estas líneas especiales es sorprendentemente difícil, como intentar encontrar una aguja específica en un pajar que cambia de forma constantemente.

Este artículo trata sobre un equipo de matemáticos que encontró una forma mucho más inteligente de resolver este rompecabezas de la "suma acumulada" para ciertos tipos de círculos numéricos. Se centraron en círculos con un número par de espacios, como un reloj con 20 horas o 22 horas. En el pasado, para averiguar cuántas líneas válidas existen para estos círculos, las computadoras tenían que revisar casi todas las combinaciones posibles una por una. Esto era como intentar encontrar una buena foto preguntando por cada combinación posible de personas para que se pusieran en fila, lo cual toma una eternidad y se vuelve imposible a medida que la fiesta se hace más grande. Los autores, Baker y Feaver, introdujeron un nuevo algoritmo que actúa como un portero superinteligente. En lugar de esperar hasta el final de la fila para ver si la foto se arruina, este portero revisa la suma acumulada después de que cada persona se une. Tan pronto como el portero ve un total que ya ha aparecido, detiene inmediatamente el crecimiento de esa línea. Se dan cuenta de que si una línea corta está rota, entonces cada línea larga que comience con ese mismo inicio roto también está destinada al fracaso. Al cortar estos "malos" ramales tempranamente, ahorran una cantidad masiva de tiempo.

Usando este método eficiente, el equipo calculó el número exacto de líneas válidas para círculos con 20 y 22 espacios. Encontraron que para un círculo de 20 espacios, hay exactamente 5,074,931,072 formas de organizar a los invitados. Para un círculo de 22 espacios, el número salta a la asombrosa cifra de 298,557,044,000. Estos números eran tan grandes que tuvieron que ser verificados independientemente por otro matemático, Bert Dobbelaere, para asegurar que fueran correctos. El artículo también demuestra una conexión fascinante entre estas líneas de "suma acumulada" y otro concepto llamado "conjuntos de diferencia", mostrando que contar uno es exactamente lo mismo que contar el otro. Esta prueba les permite usar las propiedades de uno para resolver el otro, duplicando efectivamente su eficiencia.

Los autores están muy seguros de estos números porque se derivan de una prueba matemática rigurosa y una búsqueda computacional que elimina sistemáticamente las opciones imposibles. Sin embargo, son cuidadosos al notar que, aunque su método es la forma más rápida conocida para contar estos arreglos, el problema sigue siendo increíblemente difícil. A medida que el número de espacios en el círculo aumenta, el número de posibles arreglos crece tan rápido que incluso su portero inteligente no puede seguir el ritmo para siempre. Sugieren que la proporción de líneas válidas respecto a todas las líneas posibles se vuelve cada vez más pequeña, disminuyendo aproximadamente diez veces por cada paso de aumento de tamaño. Aunque no han encontrado una fórmula mágica para predecir la respuesta para cualquier tamaño instantáneamente, su trabajo demuestra que, al ser ingeniosos sobre cuándo detener la búsqueda, podemos expandir los límites de lo que sabemos mucho más allá de lo anterior. Nos dejan con la idea de que el mejor camino a seguir podría ser encontrar más de estos "atajos inteligentes" para mapear algunas soluciones conocidas a todas las demás, pero por ahora, su nuevo algoritmo es la herramienta más poderosa que tenemos para contar estas obras maestras matemáticas.

Resumen Técnico: Un Algoritmo Más Eficiente para Hallar el Número de Permutaciones de $\mathbb{Z}/n\mathbb{Z}$ con Sumas Parciales Distintas

Planteamiento del Problema
Este artículo aborda la enumeración de permutaciones específicas dentro del grupo aditivo de los enteros módulo $n$ ( $\mathbb{Z}/n\mathbb{Z}$ ), donde $n$ es un entero par. El problema central consiste en contar el número de permutaciones $\sigma = (\sigma_0, \sigma_1, \dots, \sigma_{n-1})$ tales que el conjunto de las sumas parciales (o "factoriales" en el contexto del grupo) sean todas distintas. Específicamente, el artículo se centra en la secuencia A141599 de la Enciclopedia On-Line de Secuencias de Enteros (OEIS), que cuenta el número de "conjuntos de diferencias" para permutaciones de $\mathbb{Z}/2k\mathbb{Z}$ con diferencias distintas.

Una permutación tiene diferencias distintas si el conjunto de los valores $d_i \equiv \sigma_i - \sigma_{i-1} \pmod n$ para $1 \le i \le n-1$ contiene cada elemento no nulo de $\mathbb{Z}/n\mathbb{Z}$ exactamente una vez. Los autores señalan que tales permutaciones solo existen cuando $n$ es par. El desafío computacional radica en que el número total de permutaciones ( $n!$ ) crece factorialmente, lo que hace que la enumeración por fuerza bruta sea inviable para $n$ grandes.

Metodología
Los autores proponen un algoritmo de retroceso recursivo (backtracking) que mejora significativamente los enfoques previos de fuerza bruta al podar el espacio de búsqueda de forma temprana. La metodología se basa en tres pilares principales:

Biyectiva entre Conjuntos de Diferencias y Secuenciaciones:
El artículo establece una biyección formal (Teorema 1) entre los "conjuntos de diferencias con diferencias distintas" y las "secuenciaciones" de $\mathbb{Z}/n\mathbb{Z}$ . Una secuenciación se define como una permutación donde las sumas parciales $s(\sigma, i) = \sum_{j=0}^i \sigma_j$ son todas distintas. La demostración muestra que un conjunto de diferencias $D_\tau = (d_1, \dots, d_{n-1})$ puede mapearse a una secuenciación $\sigma = (0, d_1, \dots, d_{n-1})$ , y viceversa. Esto permite a los autores contar secuenciaciones en lugar de conjuntos de diferencias directamente.
Reducción de Simetría mediante Multiplicación:
Aprovechando el Lema 2, los autores utilizan la propiedad de que si $\sigma$ es una secuenciación y $r$ es un entero coprimo con $n$ ( $\gcd(r, n) = 1$ ), entonces el producto elemento a elemento $(r\sigma_0, r\sigma_1, \dots, r\sigma_{n-1})$ también es una secuenciación. Esto permite al algoritmo calcular secuenciaciones para una "rama" específica (permutaciones que comienzan con $0, 1$) y multiplicar el conteo por la función de Euler $\phi(n/d)$ para dar cuenta de otras ramas, en lugar de computarlas individualmente.
Poda de Ramas Recursiva (Algoritmo 2):
El núcleo del nuevo algoritmo es una búsqueda recursiva que construye permutaciones parciales. A diferencia de los métodos de fuerza bruta anteriores que validaban permutaciones completas, este algoritmo mantiene un estado de "sumas parciales" (partials).

Lógica de Poda: Si añadir un nuevo elemento a la permutación parcial resulta en una suma parcial que ya ha sido vista (o que es igual a 0 prematuramente), la rama se abandona inmediatamente.
Eficiencia: Esto evita que el algoritmo explore las $(n-k)!$ permutaciones que extenderían una secuencia parcial inválida. Por ejemplo, en $\mathbb{Z}/20\mathbb{Z}$ , la secuencia parcial $(0, 1, 19)$ produce una suma parcial de 0 en el índice 2, lo cual es inválido; el algoritmo descarta toda esta rama, ahorrando $17!$ llamadas potenciales a un validador.

Contribuciones Clave

Nuevos Términos para OEIS A141599: Utilizando el algoritmo mejorado, los autores calcularon los términos 10, 11 y 12 de la secuencia (correspondientes a $n=20, 22, 24$ $n = 20, 22, 24$ ). Los valores son:
- $n=20$ : 5,074,931,072
- $n=22$ : 298,557,044,000
- $n=24$ : 21,224,961,132,544
  Los términos 10 y 11 fueron verificados independientemente por Bert Dobbelaere.
Unificación Teórica: El artículo proporciona una prueba rigurosa de la biyección entre conjuntos de diferencias y secuenciaciones, unificando los resultados clásicos (Gilbert, Gordon) con el enfoque computacional actual.
Optimización Algorítmica: La introducción de la búsqueda de ramas recursiva con terminación temprana basada en colisiones de sumas parciales representa el método más eficiente conocido hasta la fecha para este problema de conteo específico.

Resultados y Análisis de Datos
El artículo presenta datos (Tablas 1 y 2) comparando el número de secuenciaciones con el número total de permutaciones ( $n!$ ) para $n$ pares hasta 22. Los resultados indican que la relación de secuenciaciones respecto al total de permutaciones disminuye de forma estricta y rápida a medida que $n$ aumenta, cayendo aproximadamente un orden de magnitud con cada paso. Para $n=22$ , la relación es aproximadamente $2.66 \times 10^{-10}$ .

Esta evidencia empírica respalda la eficacia de la estrategia de poda. Debido a que las secuenciaciones válidas son extremadamente escasas dentro del espacio de todas las permutaciones, generar y validar permutaciones completas es ineficiente. El enfoque recursivo, que elimina las rutas parciales inválidas de inmediato, se alinea con la escasez observada.

Significancia y Reivindicaciones
Los autores afirman que su algoritmo es el más eficiente conocido hasta la fecha para computar los términos de la secuencia A141599. Argumentan que, si bien la complejidad temporal sigue siendo superpolinómica (probablemente peor que exponencial pero mejor que $O(n!)$ ), la técnica de poda ofrece una "mejora estricta" sobre los métodos de fuerza bruta al evitar el desperdicio de computación en ramas inválidas.

El artículo concluye modestamente que las mejoras futuras en el algoritmo de conteo son probablemente limitadas a menos que se identifiquen nuevas transformaciones matemáticas. Específicamente, sugieren que el progreso futuro podría depender de la identificación de un conjunto completo de transformaciones (más allá de la multiplicación por enteros coprimos) que puedan mapear un conjunto pequeño de secuenciaciones conocidas al conjunto completo para un $n$ dado, evitando así potencialmente la necesidad de una búsqueda exhaustiva por completo. Sin embargo, no proponen tales transformaciones en este trabajo, señalando que el enfoque recursivo actual es el estado del arte para resolver el problema tal como se define.

Más como este