Resíduos Quadráticos

O resto da divisão de um quadrado por 100 só pode ter um de 22 valores distintos:

 {00,01,04,09,16,25,36,49,64,81,21,24,29,41,44,56,61,69,76,84,89,96} 

Isto acelera os testes feitos manualmente. Mas a base 100 só é realmente melhor para os humanos.

Uma verificação rápida das bases até 256, revela que algumas têm porcentagens menores de resíduos quadráticos:

80=>12 (15%)
96=>14 (14%)
112=>16 (14%)
120=>18 (15%)
144=>16 (11%)
160=>21 (13%)
168=>24 (14%)
176=>24 (13%)
180=>24 (13%)
192=>24 (12%)
208=>28 (13%)
216=>33 (15%)
224=>28 (12%)
240=>24 (10%)
252=>32 (12%)

256 tem apenas 44 (17%). Não é a melhor, mas simplifica bastante o teste: basta conferir o último byte.

Ampliando a busca para 2 bytes, aparecem alguns valores supreendentes cujos resíduos quadráticos cobrem apenas 2% das possibilidades.

Por exemplo, o mais próximo de 65.536 é 65.520=>1.344 (2%).

Se, por outro lado, contarmos os resíduos quadráticos das bases impares, encontramos 50% quando a base é um número primo, o que constitui uma forma diferente de identificar primos.