sexta-feira, 25 de novembro de 2011

Diversões numéricas com SQL III

Todos os inteiros são produzidos por uma combinação única de potências de primos. O que interessa-me saber é quais números têm uma quantidade maior de primos na sua composição.

Comecei com uma pequena consulta para fatorar um único inteiro.

with integers as (select rownum as n from all_tables where rownum<100)
select n
from integers i1
where mod(168, n)=0 
      and n between 2 and 168-1 
      and not exists (select 1 
                      from integers i2 
                      where i2.n>1 
                            and i2.n<i1.n 
                            and mod(i1.n, i2.n)=0)
Parece Lisp, não? E 168 tem três primos na sua composição: 2, 3 e 7. Adicionando uma tabela, posso procurar os inteiros que tenham o maior número de fatores primos. Aproveitei também para acelerar a busca usando a raiz quadrada de cada inteiro como limitador.

with integers as (select rownum as n from all_tables where rownum<10000)
select count(i1.n), i3.n
from integers i1, integers i3
where mod(i3.n, i1.n)=0 
      and i1.n between 2 and sqrt(i3.n)
      and not exists (select 1 
                      from integers i2 
                      where i2.n>1 
                            and i2.n<=sqrt(i1.n)
                            and mod(i1.n, i2.n)=0)
group by i3.n
order by 1 desc
Nenhum inteiro menor que 10.000 tem mais que 5 fatores primos. O inteiro 7770, por exemplo, tem os fatores 2, 3, 5, 7 e 37.

Como os priminhos baixinhos estavam aparecendo muito, resolvi procurar apenas os inteiros cujos fatores primos sejam maiores que 10. Descobri, então, que apenas 1059 inteiros menores que 10.000 têm todos os fatores primos maiores que 10. O 7429, por exemplo, tem os fatores primos 17, 19 e 23. Além disso, nenhum desses 1059 tem mais que 3 fatores primos.

Nenhum comentário: