A caminhada dos primos que se recusa a caminhar
Comecei querendo só portar um script de primos em Python para o navegador e animar uma caminhada no plano. Esperava algo parecido com a espiral de Ulam: uma nuvem irregular, com estrutura, dessas que a gente fica olhando tentando enxergar padrão.
O que saiu foi uma fita diagonal de largura $\sqrt{2}$. Sempre. Em qualquer escala, com qualquer início.
Demorei um pouco para aceitar que não era bug. A regra que eu estava animando é matematicamente incapaz de produzir a imagem que eu esperava — e o motivo é bem mais interessante do que o desenho que eu queria.
A regra
> Um ponto se move num plano. A cada inteiro $n$, se $n$ for primo ele vira à esquerda; se for composto, vira à direita. Depois dá um passo à frente.
É a "caminhada aleatória dos primos", nome que já entrega parte do problema — ela não tem nada de aleatória, como vamos ver. Começamos na origem apontando para o Leste, e o passo básico é um giro de 90°.
Com o ângulo acumulado em radianos, a implementação cabe em três linhas:
ang += ehPrimo(n) ? passo : -passo; // primo = esquerda, composto = direita
x += Math.cos(ang);
y += Math.sin(ang);
Veja acontecer
Clique em iniciar. Os controles mudam o ângulo da curva, a faixa de $n$ e a velocidade — ao mexer em qualquer um deles a caminhada volta ao começo, e é preciso clicar em iniciar de novo. Ao chegar no último $n$, aparece tracejado o bounding box da trajetória, com suas dimensões. Deixe em 90° para ver o problema; os outros ângulos são o assunto da última seção.
| n atual | primos (esquerda) | compostos (direita) | distância da origem |
| — | — | — | — |
Os vinte primeiros passos
Antes de olhar a imagem grande, vale acompanhar a caminhada na mão. A última coluna é a soma $x+y$ — guarde ela.
| $n$ | tipo | curva | direção | posição | $x+y$ |
|---|---|---|---|---|---|
| 2 | primo | esquerda | ↑ Norte | (0, 1) | 1 |
| 3 | primo | esquerda | ← Oeste | (−1, 1) | 0 |
| 4 | composto | direita | ↑ Norte | (−1, 2) | 1 |
| 5 | primo | esquerda | ← Oeste | (−2, 2) | 0 |
| 6 | composto | direita | ↑ Norte | (−2, 3) | 1 |
| 7 | primo | esquerda | ← Oeste | (−3, 3) | 0 |
| 8 | composto | direita | ↑ Norte | (−3, 4) | 1 |
| 9 | composto | direita | → Leste | (−2, 4) | 2 |
| 10 | composto | direita | ↓ Sul | (−2, 3) | 1 |
| 11 | primo | esquerda | → Leste | (−1, 3) | 2 |
| 12 | composto | direita | ↓ Sul | (−1, 2) | 1 |
| 13 | primo | esquerda | → Leste | (0, 2) | 2 |
| 14 | composto | direita | ↓ Sul | (0, 1) | 1 |
| 15 | composto | direita | ← Oeste | (−1, 1) | 0 |
| 16 | composto | direita | ↑ Norte | (−1, 2) | 1 |
| 17 | primo | esquerda | ← Oeste | (−2, 2) | 0 |
| 18 | composto | direita | ↑ Norte | (−2, 3) | 1 |
| 19 | primo | esquerda | ← Oeste | (−3, 3) | 0 |
| 20 | composto | direita | ↑ Norte | (−3, 4) | 1 |
| 21 | composto | direita | → Leste | (−2, 4) | 2 |
Em sequência compacta, com E para esquerda e D para direita:
E E D E D E D D D E D E D D D E D E D D
São 8 esquerdas e 12 direitas — exatamente os 8 primos até 21.
Três coisas já saltam da tabela:
- Os eixos se alternam sem exceção. Nunca há dois passos horizontais em sequência, nem dois verticais.
- A coluna $x+y$ só assume os valores 0, 1 e 2. Nenhuma exceção — e isso não é sorte dos primeiros passos, como a figura da próxima seção mostra.
- Quatro compostos seguidos formam um quadrado fechado, quatro passos que não levam a lugar nenhum. O primeiro caso aparece logo depois do fim da tabela: os passos 25 a 28 saem de $(-1, 2)$ e voltam a $(-1, 2)$.
Vinte passos adiante, em $n = 41$, a caminhada está de volta na origem depois de percorrer 40 arestas.
O que a imagem revela
Rodando a animação, o desenho é uma fila de quadrados unidos pelos vértices, formando uma única linha reta a 45°. Não é impressão nem artefato de escala: todos os pontos visitados satisfazem $x + y \in \{0, 1, 2\}$. A trajetória inteira vive numa faixa diagonal de largura $\sqrt{2}$ — as três diagonais tracejadas na figura abaixo.
E isso se mantém em qualquer escala:
| $n$ | passos | bounding box | pontos distintos | pontos por passo |
|---|---|---|---|---|
| 100 | 99 | 8 × 8 | 25 | 25/99 = 25,253% |
| 1.000 | 999 | 27 × 27 | 81 | 81/999 = 8,108% |
| 5.000 | 4.999 | 41 × 41 | 123 | 123/4999 = 2,460% |
| 20.000 | 19.999 | 69 × 69 | 208 | 208/19999 = 1,040% |
| 100.000 | 99.999 | 338 × 338 | 1.014 | 1014/99999 = 1,014% |
Chamando de $L$ o lado da bounding box, o número de pontos distintos é $3L$ ou $3L+1$ em todas as linhas — as três diagonais e mais nada. A faixa nunca engorda; só estica. Dos 99.999 segmentos até $n = 100.000$, 98.986 caem sobre um ponto já visitado, e um deles é pisado 599 vezes. Cem mil passos desenham só 1.350 arestas distintas.
Por que é assim
Duas propriedades da regra, combinadas.
1. Os passos alternam obrigatoriamente entre horizontal e vertical. Toda curva é de $\pm 90°$, então a direção muda de paridade a cada número: se o passo $n$ foi horizontal, o passo $n+1$ é necessariamente vertical. Cada par de passos consecutivos é portanto um deslocamento diagonal $(\pm 1, \pm 1)$, de comprimento $\sqrt{2}$ — e a escada de quadrados é inevitável.
2. A direção não tem nada de aleatório. Sendo $\pi(n)$ a contagem de primos e $c(n)$ a de compostos até $n$, e numerando as direções como $0$ = Leste, $1$ = Norte, $2$ = Oeste, $3$ = Sul, a direção depois do passo $n$ é exatamente
$$d_n \equiv \big(\pi(n) - c(n)\big) \bmod 4.$$
Cada primo soma $+1$ e cada composto soma $+3$; como $3 \equiv -1 \pmod 4$, virar à direita é o mesmo que subtrair 1, e o acumulado vira $\pi - c$. Nos mesmos vinte passos da tabela lá de cima, a coluna da direção bate linha a linha — sem nenhuma consulta ao caminho já percorrido:
| $n$ | $\pi(n)$ | $c(n)$ | $\pi-c$ | $d_n$ | direção |
|---|---|---|---|---|---|
| 2 | 1 | 0 | 1 | 1 | ↑ Norte |
| 3 | 2 | 0 | 2 | 2 | ← Oeste |
| 4 | 2 | 1 | 1 | 1 | ↑ Norte |
| 5 | 3 | 1 | 2 | 2 | ← Oeste |
| 6 | 3 | 2 | 1 | 1 | ↑ Norte |
| 7 | 4 | 2 | 2 | 2 | ← Oeste |
| 8 | 4 | 3 | 1 | 1 | ↑ Norte |
| 9 | 4 | 4 | 0 | 0 | → Leste |
| 10 | 4 | 5 | −1 | 3 | ↓ Sul |
| 11 | 5 | 5 | 0 | 0 | → Leste |
| 12 | 5 | 6 | −1 | 3 | ↓ Sul |
| 13 | 6 | 6 | 0 | 0 | → Leste |
| 14 | 6 | 7 | −1 | 3 | ↓ Sul |
| 15 | 6 | 8 | −2 | 2 | ← Oeste |
| 16 | 6 | 9 | −3 | 1 | ↑ Norte |
| 17 | 7 | 9 | −2 | 2 | ← Oeste |
| 18 | 7 | 10 | −3 | 1 | ↑ Norte |
| 19 | 8 | 10 | −2 | 2 | ← Oeste |
| 20 | 8 | 11 | −3 | 1 | ↑ Norte |
| 21 | 8 | 12 | −4 | 0 | → Leste |
Nenhuma aleatoriedade, apesar do nome. E como os compostos dominam numa razão de quase 8 para 1 nessa faixa, a diferença $\pi(n) - c(n)$ decresce de forma quase monótona: a caminhada é essencialmente um giro horário constante, fechando um quadrado a cada 4 compostos. Os primos entram só como defeitos raros que deslocam a fase do ciclo.
Cada defeito desses empurra a caminhada um passo diagonal para fora do quadrado atual. Como o empurrão é sempre no mesmo sentido, o acúmulo aponta sempre na mesma diagonal — e é isso que produz a fita.
A conclusão que me custou a tarde: a degenerescência é da regra, não do código. Nenhum ajuste de implementação abre esse desenho, porque com apenas $\pm 90°$ e um sinal determinístico a caminhada não tem grau de liberdade para se espalhar.
O que abre a imagem
A propriedade (1) depende de o ângulo dividir 360° em quatro. Qualquer outro ângulo quebra a alternância de eixos e a faixa se solta. Com 20.000 passos:
| ângulo | bounding box | distância final da origem |
|---|---|---|
| 90° | 69 × 69 | 79,9 |
| 60° | 124 × 82 | 68,3 |
| 45° | 88 × 118 | 30,0 |
| 120° | 48 × 71 | 40,3 |
Vale trocar o ângulo no controle acima e ver a diferença — em 60° e 45° aparece a estrutura irregular que eu procurava desde o começo.
Se a intenção for manter os 90°, aí a mudança tem que ser na regra. A variante clássica é virar à esquerda nos primos e seguir reto nos compostos: assim os compostos deixam de fechar quadradinhos e passam a produzir os segmentos longos que dão forma ao desenho. É outra caminhada, mas é a que gera as imagens bonitas que circulam por aí.