Teste de Divisibilidade Usando Conversão de Bases

Há muitos anos eu havia escrito uma pequena função para fazer conversão de bases sem ifs. Mais recentemente, mostrei como o teste de divisibilidade por 3 ou 9 pode ser generalizado para todos os números usando a base+1.

Resolvi juntar as duas coisas e escrever um teste genérico de divisibilidade usando esses dois conceitos e ainda mostrando que a soma dos dígitos pode ser feita com o módulo apenas.

Sobre o módulo, considere o número 324. Para determinar se é múltiplo de 3, podemos trabalhar com módulo 3.

 3 + 2 + 4 = 9
 3%3 + 2%3 + 4%3 => 0 + 2 + 1 = 3
 

Então, isso significa que podemos trabalhar com números menores, o que pode ser útil quando estamos fazendo contas com lápis e papel ou quando o computador está trabalhando em números muito grandes.

use strict;

sub to_base {
  my $n=shift;
  my $base=shift;
  reverse 
    map { int(($n%($base**($_+1)))/($base**$_)) }
      0..int(log($n)/log($base));
}

sub is_divisible {
  my ($n, $d)=@_;
  my $t=0;
  
  map { $t=($t + $_ % $d) % $d } to_base($n, $d+1);
  return $t==0;
}

my $is_divisible=is_divisible(5603, 13);
print "5603 => $is_divisible\n";   

5603 => 1

De fato, 5603 = 13 * 431.

Alterei a antiga função to_base() para retornar um array dos valores dos dígitos. A função original usava o alfabeto para ampliar a variedade de dígitos.