🔢 mathematics

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

Este artigo apresenta um algoritmo aprimorado para contar permutações de $\mathbb{Z}/n\mathbb{Z}$ com somas parciais distintas, calculando especificamente resultados para $n=20$ e $n=22$ , ao mesmo tempo em que estabelece uma bijeção com uma sequência conhecida que permite a derivação de novos termos.

Autores originais: Quinn Baker, Amy Feaver

Publicado 2026-07-27

📖 4 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Quinn Baker, Amy Feaver

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está em uma festa enorme onde todos têm um número único em suas camisetas, variando de 0 a um limite específico. O anfitrião quer organizar os convidados em uma única fila para uma foto, mas há uma regra complicada: conforme você caminha pela fila, deve manter uma contagem acumulada dos números que viu até agora. A regra é que, toda vez que você adiciona uma nova pessoa à sua contagem, o novo total deve ser um número que você não viu antes em toda a fila. Se você atingir um total que já contou, a fila é quebrada e a foto é arruinada. Isso não é apenas um jogo de festa; é um enigma profundo no mundo da matemática chamado "teoria dos grupos", especificamente lidando com como podemos ordenar números em um círculo (como as horas em um relógio) de modo que nossas somas acumuladas nunca se repitam até que tenhamos usado cada número exatamente uma vez. Matemáticos se importam com isso porque ajuda a entender as estruturas ocultas de simetria e ordem no universo, e encontrar essas linhas especiais é surpreendentemente difícil, como tentar encontrar uma agulha específica em um palheiro que muda de forma constantemente.

Este artigo é sobre uma equipe de matemáticos que encontrou uma maneira muito mais inteligente de resolver este enigma da "soma acumulada" para certos tipos de círculos numéricos. Eles se concentraram em círculos com um número par de espaços, como um relógio com 20 ou 22 horas. No passado, para descobrir quantos tipos de linhas válidas existem para esses círculos, os computadores tinham que verificar quase todas as arranjos possíveis um por um. Isso era como tentar encontrar uma boa foto perguntando a cada uma das combinações possíveis de pessoas para ficarem na fila, o que leva uma eternidade e se torna impossível conforme a festa fica maior. Os autores, Baker e Feaver, introduziram um novo algoritmo que age como um segurança superinteligente. Em vez de esperar até o fim da fila para ver se a foto foi arruinada, este segurança verifica a soma acumulada após cada pessoa se juntar. Assim que o segurança vê um total que já apareceu, ele interrompe imediatamente o crescimento dessa linha. Eles percebem que, se uma linha curta é quebrada, então toda linha longa que começa com aquele mesmo início quebrado também está fadada ao fracasso. Ao cortar esses "ramos ruins" precocemente, eles economizam uma quantidade massiva de tempo.

Usando este método eficiente, a equipe calculou o número exato de linhas válidas para círculos de 20 e 22 espaços. Eles descobriram que, para um círculo de 20 espaços, existem exatamente 5.074.931.072 maneiras de organizar os convidados. Para um círculo de 22 espaços, o número salta para impressionantes 298.557.044.000. Esses números eram tão grandes que tiveram que ser verificados independentemente por outro matemático, Bert Dobbelaere, para garantir que estavam corretos. O artigo também prova uma conexão fascinante entre essas linhas de "soma acumulada" e outro conceito chamado "conjuntos de diferença", mostrando que contar um é exatamente o mesmo que contar o outro. Esta prova permite que eles usem as propriedades de um para resolver o outro, efetivamente dobrando sua eficiência.

Os autores estão muito confiantes nesses números porque eles são derivados de uma prova matemática rigorosa e de uma busca computacional que elimina sistematicamente as opções impossíveis. No entanto, eles são cuidadosos ao notar que, embora seu método seja a maneira mais rápida conhecida para contar esses arranjos, o problema ainda é incrivelmente difícil. À medida que o número de espaços no círculo aumenta, o número de arranjos possíveis cresce tão rápido que mesmo o seu segurança inteligente não consegue acompanhar para sempre. Eles sugerem que a proporção de linhas válidas em relação a todas as linhas possíveis diminui cada vez mais, caindo cerca de dez vezes para cada aumento de tamanho. Embora não tenham encontrado uma fórmula mágica para prever a resposta para qualquer tamanho instantaneamente, o trabalho deles prova que, ao sermos inteligentes sobre quando parar de procurar, podemos expandir muito mais os limites do que sabemos. Eles nos deixam com a ideia de que a melhor maneira de seguir em frente pode ser encontrar mais desses "atalhos inteligentes" para mapear algumas soluções conhecidas para todas as outras, mas, por enquanto, seu novo algoritmo é a ferramenta mais poderosa que temos para contar essas obras-primas matemáticas.

Resumo Técnico: Um Algoritmo Mais Eficiente para Encontrar o Número de Permutações de $\mathbb{Z}/n\mathbb{Z}$ com Somas Parciais Distintas

Enunciado do Problema
Este artigo aborda a enumeração de permutações específicas dentro do grupo aditivo de inteiros módulo $n$ ( $\mathbb{Z}/n\mathbb{Z}$ ), onde $n$ é um número inteiro par. O problema central envolve a contagem do número de permutações $\sigma = (\sigma_0, \sigma_1, \dots, \sigma_{n-1})$ tal que o conjunto das somas parciais (ou "fatoriais" no contexto do grupo) sejam todos distintos. Especificamente, o artigo foca na sequência A141599 da On-Line Encyclopedia of Integer Sequences (OEIS), que conta o número de "conjuntos de diferença" para permutações de $\mathbb{Z}/2k\mathbb{Z}$ com diferenças distintas.

Uma permutação possui diferenças distintas se o conjunto de valores $d_i \equiv \sigma_i - \sigma_{i-1} \pmod n$ para $1 \le i \le n-1$ contém cada elemento não nulo de $\mathbb{Z}/n\mathbb{Z}$ exatamente uma vez. Os autores observam que tais permutações só existem quando $n$ é par. O desafio computacional reside no fato de que o número total de permutações ( $n!$ ) cresce fatorialmente, tornando a enumeração por força bruta inviável para $n$ maiores.

Metodologia
Os autores propõem um algoritmo de retrocesso recursivo (recursive backtracking) que melhora significativamente as abordagens anteriores de força bruta ao podar o espaço de busca precocemente. A metodologia baseia-se em três pilares principais:

Bijeção entre Conjuntos de Diferença e Sequenciamentos:
O artigo estabelece uma bijeção formal (Teorema 1) entre "conjuntos de diferença com diferenças distintas" e "sequenciamentos" de $\mathbb{Z}/n\mathbb{Z}$ . Um sequenciamento é definido como uma permutação onde as somas parciais $s(\sigma, i) = \sum_{j=0}^i \sigma_j$ são todas distintas. A prova demonstra que um conjunto de diferença $D_\tau = (d_1, \dots, d_{n-1})$ pode ser mapeado para um sequenciamento $\sigma = (0, d_1, \dots, d_{n-1})$ , e vice-versa. Isso permite que os autores contem sequenciamentos em vez de conjuntos de diferença diretamente.
Redução de Simetria via Multiplicação:
Utilizando o Lema 2, os autores utilizam a propriedade de que, se $\sigma$ é um sequenciamento e $r$ é um inteiro coprimo a $n$ ( $\gcd(r, n) = 1$ ), então o produto elemento a elemento $(r\sigma_0, r\sigma_1, \dots, r\sigma_{n-1})$ também é um sequenciamento. Isso permite que o algoritmo compute sequenciamentos para um "ramo" específico (permutações começando com $0, 1$) e multiplique a contagem pela função totiente de Euler $\phi(n/d)$ para considerar outros ramos, em vez de computá-los individualmente.
Poda de Ramos Recursiva (Algoritmo 2):
O núcleo do novo algoritmo é uma busca recursiva que constrói permutações parciais. Diferente dos métodos de força bruta anteriores que validavam permutações completas, este algoritmo mantém um estado de "somas parciais" (partials).
- Lógica de Poda: Se adicionar um novo elemento à permutação parcial resultar em uma soma parcial que já foi vista (ou que seja igual a 0 prematuramente), o ramo é imediatamente abandonado.
- Eficiência: Isso evita que o algoritmo explore as $(n-k)!$ permutações que estenderiam uma sequência parcial inválida. Por exemplo, em $\mathbb{Z}/20\mathbb{Z}$ , a sequência parcial $(0, 1, 19)$ resulta em uma soma parcial de 0 no índice 2, o que é inválido; o algoritmo descarta todo este ramo, economizando $17!$ chamadas potenciais a um validador.

Principais Contribuições

Novos Termos para OEIS A141599: Usando o algoritmo melhorado, os autores calcularam o 10º, 11º e 12º termos da sequência (correspondentes a $n=20, 22, 24$ $n = 20, 22, 24$ ). Os valores são:
- $n=20$ : 5.074.931.072
- $n=22$ : 298.557.044.000
- $n=24$ : 21.224.961.132.544
  O 10º e o 11º termos foram verificados independentemente por Bert Dobbelaere.
Unificação Teórica: O artigo fornece uma prova rigorosa da bijeção entre conjuntos de diferença e sequenciamentos, unificando resultados clássicos (Gilbert, Gordon) com a atual abordagem computacional.
Otimização Algorítmica: A introdução da busca de ramos recursiva com terminação precoce baseada em colisões de somas parciais representa o método mais eficiente conhecido até o momento para este problema de contagem específico.

Resultados e Análise de Dados
O artigo apresenta dados (Tabelas 1 e 2) comparando o número de sequenciamentos com o número total de permutações ( $n!$ ) para $n$ pares até 22. Os resultados indicam que a razão entre sequenciamentos e o total de permutações diminui de forma estrita e rápida conforme $n$ aumenta, caindo aproximadamente uma ordem de magnitude a cada passo. Para $n=22$ , a razão é de aproximadamente $2,66 \times 10^{-10}$ .

Esta evidência empírica apoia a eficácia da estratégia de poda. Como os sequenciamentos válidos são extremamente esparsos dentro do espaço de todas as permutações, gerar e validar permutações completas é ineficiente. A abordagem recursiva, que elimina caminhos parciais inválidos imediatamente, alinha-se com a esparsidade observada.

Significância e Alegações
Os autores alegam que seu algoritmo é o mais eficiente conhecido até o momento para computar os termos da sequência A141599. Eles argumentam que, embora a complexidade de tempo permaneça superpolinomial (provavelmente pior que exponencial, mas melhor que $O(n!)$ ), a técnica de poda oferece uma "melhoria estrita" sobre os métodos de força bruta ao evitar o desperdício de computação em ramos inválidos.

O artigo conclui modestamente que melhorias futuras no algoritmo de contagem são provavelmente limitadas, a menos que novas transformações matemáticas possam ser identificadas. Especificamente, eles sugerem que o progresso futuro pode depender da identificação de um conjunto completo de transformações (além da multiplicação por inteiros coprimos) que possam mapear um pequeno conjunto de sequenciamentos conhecidos para o conjunto total para um determinado $n$ , potencialmente contornando a necessidade de busca exaustiva por completo. No entanto, eles não propõem tais transformações neste trabalho, observando que a abordagem recursiva atual é o estado da arte para resolver o problema conforme definido.

Mais como este