segunda-feira, abril 12, 2010

A Divisibilidade de Números Imensos por Números Pequenos

A questão da divisibilidade é algo que conhecemos desde que aprendemos a dividir. Nos processadores modernos costuma ser rápido e simples testar a divisibilidade de um número por outro, desde que os números não ultrapassem a capacidade da unidade lógica aritmética. O que fazer, entretanto, quando queremos testar a divisibilidade por onze de um número de 1000 dígitos?

Um Pouco de Teoria

Dizemos que um número inteiro é divisível por outro, quando o resto da divisão do primeiro pelo segundo é zero. O resto (também chamado de módulo) é definido matematicamente pela expressão

a = qd + r

condicionada a

0 ≤ r < d

onde a e d são números naturais (inteiros, positivos ou negativos ou, no caso de a, nulo). q é o quociente e r é o resto.

Uma forma tradicional de anotar o cálculo do resto é usar um operador mod:

r = a mod d

Na linguagem C e suas descendentes (como C++, Java, C#, etc) o operador mod é representado por %.

Existe todo um estudo matemático desta operação. Para este post vamos nos concentrar na seguinte propriedade:

(a+b) mod d = ((a mod d) + (b mod d) mod d

É uma especie de distributiva, porém surge um "mod d" a mais. Intuitivamente percebemos que a soma dos dois primeiro mod pode resultar em um valor acima de d, daí a necessidade desta operação a mais.

No nosso caso vamos nos concentrar na situação em queremos testar se um número c é divisível por d. Se tivermos que c = a+b e a mod d = 0, percebemos pela propriedade acima que c será divisível se e somente se b for divisível por d. A nossa aplicação prática será descartar os dígitos mais significativos de c quando soubermos que eles são sempre divisíveis por d.

As linguagens de programação atuais costumam trabalhar com inteiros (com sinal) de 32 bits. Isto significa que é possível calcular de forma rápida e direta o resto da divisão de números até 2.147.483.647. Como diz uma piada recorrente no Daily WTF, em sistema embarcados a coisa pode ser diferente.

Vamos ao métodos para os números de 2 a 13. Não vou justificar os casos mais complicados, os links no final trazem mais detalhes.

Divisibilidade Por Dois

Esta é muito fácil. Como dez é divisível por dois, basta examinar o dígito menos significativo. Se examinarmos o número em binário, o bit menos significativo é zero se (e somente se) o número é divisível por dois. Isto pode ser testado com uma operação AND binária ("& 0x01 == 0" na linguagem C).

Divisibilidade Por Três

Talvez você tenha aprendido esta regra no primário: um número é divisível por três se, e somente se, a soma dos seus dígitos for divisível por três. Você pode repetir esta regra até chegar a um número pequeno suficiente. Por exemplo

a soma dos dígitos de 162594 é 27
a soma dos dígitos de 27 é 9
9 é divisível por 3, logo 27 é divisível por 3, logo 162594 é divisível por 3.

Divisibilidade Por Quatro

Podemos usar um truque semelhante ao da divisibilidade por dois. 100 é divisível por 4, logo testamos apenas os dois dígitos menos significativos. Em binário, basta testar se os dois bits menos significativos são zero ("& 0x03 == 0").

Divisibilidade Por Cinco

Mais uma vez, dez é divisível por cinco, portanto basta testar o último dígito. Simplesmente verifique se ele é 0 ou 5.

Divisibilidade Por Seis

Como 6 = 2 x 3 e 2 e 3 são primos entre si, um número é divisível por seis se, e somente ser, for divisível por 2 e por 3.

Divisibilidade Por Sete

Retire o último dígito. Subtrai do número restante o dobro do dígito retirado. O número original será divisível por 7 se, e somente se, o resultado for divisível. Repita à vontade.

Por exemplo, pegando o número 5705

570 - 2*5 = 560
56 - 2*0 = 56
56 é 7 x 8, portanto 5705 é divisível por 7

Divisibilidade Por Oito

Seguindo a mesma lógica que para 2 e 4: 1000 é divisível por oito, examine os três últimos dígitos, os três bits menos significativos precisam ser zero ("& 0x07 == 0").

Divisibilidade Por Nove

De forma semelhante ao três, um número é divisível por nove se, e somente se, a soma dos seus dígitos for divisível por nove.

Divisibilidade Por Dez

Se e somente se o último dígito for zero.

Divisibilidade Por Onze

Comece no primeiro dígito e vá somando os dígitos alternados. Repita começando do segundo. Se o valor absoluto da diferença entre as duas somas for divisível por onze, o número é divisível por onze (e vice versa). Se você quiser, pode somar do fim para o começo.

Tomando como exemplo 174529

(1+4+2) - (7+5+9) = 7 - 21 = -14

Como 14 não é divisível por 11, 174529 também não é.

Divisibilidade Por Doze

Como 12 = 4 x 3 e 4 e 3 são primos entre si, um número é divisível por doze se, e somente ser, for divisível por 4 e por 3.

Divisibilidade Por Treze

A regra é parecida com a da divisibilidade por sete. Retire o último dígito. Subtrai do número restante nove vezes o dígito retirado. O número original será divisível por 13 se, e somente se, o resultado for divisível. Repita à vontade.

Pegando 845 como exemplo

84 - 9*5 = 39 = 3 x 13, portanto 845 é divisível por treze.

Links

http://technocosm.org/chaos/divisibility.html
http://mathforum.org/k12/mathtips/division.tips.html

Nenhum comentário: