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:
Postar um comentário