Já investiguei vários tipos de sistemas numéricos, mas há um que é bastante diferente dos outros, porque não há uma maneira direta para converter para outras bases.
Uma consequência do Teorema Chinês dos Restos é que podemos representar um número como um conjunto de restos. A única exigência é a de que os números da nossa base sejam primos entre si.
Por exemplo, se eu usar 2 e 3 como uma base, posso representar todos os números até 6. O 1 eu represento com a tupla (1,1), o 2 com (0,2), o 3 com (1,0), o quatro com (0,1), o 5 com (1,2).
Seu eu usar apenas números primos até 8 bits (são 53 primos), posso representar números até o seguinte:
64266330917908644872330635228106713310880186591609208114244758680898150367880703152525200743234420230.
Esse monstro de 101 dígitos necessitaria 334 bits para ser representado num computador. Entretanto, com o uso da aritmética modular, posso fazer muitas operações de apenas 1 byte. Repare que 53*8=424 bits, então não é espaço que é economizado, mas sim complexidade das operações.
Claro que produzir o resultado no final exige uma complicação adicional.
Adição e subtração são definidos assim:
(A + B) mod C = (A mod C + B mod C) mod C
(A - B) mod C = (A mod C - B mod C) mod C
Então, podemos ir somando números aos poucos e por partes até chegar a uma soma realmente grande sem nunca ter que operar com um número grande. Infelizmente, em algum momento será preciso converter para uma base mais prática para visualizar o resultado. Um algoritmo relativamente eficiente é o de Algoritmo de Garner, mas eu vou descrever uma forma de reconstruir o resultado que também nos ensina um pouco sobre esse tipo de base.
Dada uma base formada por (3,11,17), que podemos usar para representar números de 0 até 561 (3*11*17), e um número representado pelos restos (2,4,1), vamos procurar começando pelo primeiro número a satisfazer x%17=1, que é 18. Se formos somando 17, em algum momento vamos encontrar um número que, além de ter resto 1 para 17, terá resto 4 para 11. Ou seja, queremos resolver (18+(x*17))%11=4. Este número é 103. A partir de 103, precisamos encontrar um número que também tenha resto 2 para 3. Podemos pular de 187 em 187 (11*17). Ou seja, precisamos resolver (103+(x*187))%3=2. E isso nos leva a 290.
O que isso nos ensina? Os restos se repetem de 3 em 3, de 11 em 11, de 17 em 17, de 3*11 em 3*11, de 3*17 em 3*17, e de 11*17 em 11*17.
Agora vou introduzir os números afortunados. Um número afortunado é o menor inteiro que, somado a um primorial resulta num primo.
Se tivermos uma base de restos baseada em primos, sabemos que todos os casos em que nenhum dos restos for 0 é um candidato a primo. Por exemplo, vamos ver a base (2,3):
| n | n%2 | n%3 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 0 | 2 |
| 3 | 1 | 0 |
| 4 | 0 | 1 |
| 5 | 1 | 2 |
Os dois restos são diferentes de 0 com n=1 ou com n=5, que é primo. Claro que, numa base com mais elementos, um candidato a primo pode ser apenas um múltiplo de um primo que não está na base. O que é importante ressaltar é que o padrão de restos se repete. Então, quando estamos tratando de números maiores de 2*3, não temos como saber precisamente de qual número se trata: temos que viver dentro do universo de 0 a 5.
| n | n%2 | n%3 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 0 | 2 |
| 3 | 1 | 0 |
| 4 | 0 | 1 |
| 5 | 1 | 2 |
| 6 | 0 | 0 |
| 7 | 1 | 1 |
| 8 | 0 | 2 |
| 9 | 1 | 0 |
| 10 | 0 | 1 |
| 11 | 1 | 2 |
Se ignorarmos o 1, todos os casos em que nenhum dos restos é 0 representam primos.
O primeiro primo depois de 6 é 7, mas esse não conta, porque é necessário somar apenas 1 a 6. O próximo é 11 e o número afortunado, neste caso, é 5, que é primo. Dado que os restos da representação de 11 têm que ser iguais aos restos da representação de 5 (porque a diferença é 6), seria até surpreendente encontrar um caso em que o número afortunado não fosse primo.
Mas isso não é prova suficiente, porque poderia acontecer, numa base muito maior, que o número afortunado fosse múltiplo de um primo que não está no primorial (ou na base de resíduos, se preferir).
