Números Feios - II

Por certo a expectativa é a obtenção mais conveniente para o problema dos números feios. Mas por enquanto, vamos retardar um pouco este desfecho. Vamos aproveitar a oportunidade para saborear um pouco uma estratégia muito interessante na resolução de problema. Segundo George Polya, após resolver um problema devemos buscar generalizações.
Me ocorreu portanto explorar esta estratégia a partir da função que verifica se um dado número satisfaz a propriedade de pertencer ao conjunto dos feios. Como vimos isto foi obtido com o apoio de uma outra função, reduz x n.

feio x = reduz (reduz (reduz x 2) 3) 5 == 1
reduz x n = if mod x n == 0
then reduz (div x n) n
else x

Pode-se observar aqui que verficar se x é feito foi realizado por verificar se a composição da aplicação de reduz x1 2, seguida de reduz x2 3, seguida de reduz x3 5, produz o valor 1.

Podemos generalizar então a função feio x para que possamos verificar se um número é redutível por uma lista qualquer de números. Vamos chamá-la de fprimos.

fprimos n [ ] = n
fprimos n (x:xs) = if n < x
then fprimos n xs else
fprimos (reduz n x) xs

Vejamos alguns exemplos de uso:

> fprimos 1000 [2,3,5]
1
> fprimos 10009 [2,3,5]
10009
> fprimos 100092 [2,3,5]
8341
> fprimos 944784 [2,3,5]
1
> fprimos 859963392 [2,3,5]
1
> fprimos 1048576 [2]
1

O último exemplo acima mostra um outro uso, a de verificar se um número é potência de um determinado fator primo. No caso, como se sabe, o número 1.048.576 é a potência 20 do fator 2.

COmo isso, podemos fazer uma nova versão da função feio, usando agora a função fprimos.

feio' x = fprimos x [2,3,5] == 1

E aqui temos alguns exemplos de uso.

> feio' 859963392
True
> feio' 1024
True
> feio' 1026
False
> feio' 859963392
True
> feio' 1985
False
> feio 1985 == feio' 1985
True

Nova questões sobre generalização podem surgir, tal como:

Como podemos usar a função fprimos para verificar se um número é primo?