Números Feios - I

Visitando o site de problemas da Universidad de Valladolid (UVA), encontrei um problema que me chamou atenção por dois aspecto. Inicialmente pelo nome, "Ugly Numbers". Pensei comigo, que propriedades teriam esses números para serem chamados de feios? Depois pela simplicidade da descrição. Pensei de novo, o que será que um problemas tão simples assim tem de atraente?

Vejamos a descrição do problema de no. 136 do site da UVA.

Ugly Numbers
Ugly numbers are numbers whose only prime factors are 2, 3 or 5.
The sequence: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... shows the first 11 ugly numbers. By convention, 1 is included.

Write a program to find and print the 1500'th ugly number.

Input Output
There is no input to this program. Output should consist of a single line as shown below, with replaced by the number computed.

Sample output
The 1500'th ugly number is .

Chamou-me ainda atenção o alto número de submissões, atualmente 31872, versus o percentual de submissões aceitas: 25.7%, das quais apenas 69.5% tiveram sucesso. Afinal, a solução parece simples e direta.

O que ocorre na verdade é que a solução ingênua é muito dispendiosa. Consome bastante tempo.

Bom, resolvi explorar um pouco sobre soluções em Haskell para o problema e vi que ele apresentava a oportunidade de fazermos um tour por algumas facilidades da linguagem.

A primeira versão, a bem ingênua, considera que os números feios formam uma lista, cujos elementos são oriundos da lista infinita [1.. ] e que satisfazem a propriedades de terem como únicos fatores primos os números 2, 3 e 5.

Assim, a primeira providência é definir a lista de números feios:

feios = [x | x<-[1..], feio x]

a segunda é definir o predicado feio x,

feio x = reduz (reduz (reduz x 2) 3) 5 == 1

Para tanto precisou-se construir uma função auxiliar, reduz x n, cuja finalidade é extrair de um número x as potências de um outro dado n.

reduz x n = if mod x n == 0 then reduz (div x n) n else x

agora, como temos uma lista como todos os feios, se desejamos conhecer o numero feio de ordem 1500, basta pedir ao sistema que determine, usando a operação de indexação (!!). O feio de ordem 1500 pode ser descrito por: feios!!1499, certo?

Podemos usar para outros feios também:

> feios!!0
1
(283 reductions, 525 cells)
> feios!!10
15
(5582 reductions, 8081 cells)
> feios!!100
1600
(662585 reductions, 962977 cells)
> feios!!200
16384
(6168873 reductions, 8984262 cells, 9 garbage collections)
>feios!!500
944784
(387151581 reductions, 568449819 cells, 577 garbage collections)

Veja que já começou a ficar complicado para o ambiente WinHugs. O esforço já está grande. Imagine se pedirmos feios!!1499.

Bom, disto podemos concluir que nossa solução ingênua não é muito boa.

Apesar disso, podemos aproveitar os ganhos que tivemos.

a) A função feio x, pode ser usada para verificar se um dado número é feio ou não, independente da função feios, o que ilustra bem o estilo da linguagem. Cada função pode ser usada independente.

> feio 944784
True
(1765 reductions, 2561 cells)
> feio 859963392
True
(2952 reductions, 4291 cells)

este último exemplo, é o feio de ordem 1500. Só para verificar se é feio ou não, até que o avaliador dá conta com facilidade.

b) A função feios, serve para obter não apenas o k-ésimo elemento, mas qualquer outro feio que desejarmos.

c) Podemos obter a lista do n primeiro feios. Na verdade, usando as funções take n e drop n podemos pegar qualquer pedaço da lista. Esta facilidade é possivel graças ao uso do conceito de lista infinita. Não precisamos saber antecipadamente quantos elementos iremos querer, isto é determinado em tempo de avaliação de uma expressão.

> take 10 feios
[1,2,3,4,5,6,8,9,10,12]
(278 reductions, 391 cells)
> take 10 (drop 10 feios) -- do 11 ao 20-éssimo
[15,16,18,20,24,25,27,30,32,36]
(451 reductions, 602 cells)

d) A função reduz, que nos serviu para para construir a feio x, serve na verdade para ser usada em outras situações. Como por exemplo, para verificar se um número é uma potência de outro.

> reduz 1024 3 == 1 -- 1024 é uma potência de 3?
False
(110 reductions, 152 cells)
> reduz 1024 2 == 1 -- 1024 é uma potência de 2?
True
(1189 reductions, 1697 cells)

Bom, podemos dar outros usos à função reduz, mas por enquanto ficamos assim.

Antes de terminar esta postagem, cabe ainda um comentário sobre a origem da inconveniência computacional introduzida pela especificação que foi aqui apresentada.
Podemos observar que para cada numero inteiro positivo precisamos verificar se ele satisfaz à condição de pertencer ou não aos feios. Assim, mesmo para aqueles que não são feio, precisamos fazer as reduções. A quantidade de feios é bem pequena em relação ao demais. No caso no número feio de 0rdem 1500, ele é o número 859.963.392 , quase 1 bilhão. Ou seja, para encontrar o número feio da ordem desejada foi necessário analisar cerca de 1 bilhão de números (10^9). Se para testar cada número gastarmos 0,001 seg precisaremos de 10^6 seg para encontrar o número desejado.