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.

quinta-feira, 24 de novembro de 2011

Diversões numéricas com SQL II

Nenhuma diversão numérica seria completa se os primos não aparecessem. Então, resolvi logo descobrir se é possível selecioná-los.

with integers as (select rownum as n 
                  from all_tables 
                  where rownum<100)
select n 
from integers i1
where i1.n>1 
      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)
Parece bom. E com isso podemos procurar relações interessantes, como primos gêmeos.

select n, previous from (
  with integers as (select rownum as n 
                    from all_tables 
                    where rownum<100)
  select n, lag(n, 1, n) over (order by n) previous 
  from integers i1
  where i1.n>1 
        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)
) where n=previous+2
Usando a função lag(), podemos selecionar todas as duplas de primos separados por apenas um inteiro. Com isso, descobri que 3001 e 2999 são primos gêmeos, assim como 9001 e 8999.

quarta-feira, 23 de novembro de 2011

Diversões numéricas com SQL

Contar com SQL é fácil; achar uma utilidade custou-me um pouco. Comecei com uma consulta bastante simples para contar em base 2.

with bits as (select rownum-1 as bit from all_tables where rownum<3)
select b1.bit, b2.bit
from bits b1, bits b2
O resultado é uma tabela bastante simples, com os quatro números possíveis de dois dígitos binários.

A primeira aplicação (embora redundante, porque o Oracle já me oferece alternativa) é a de converter números para a base 16 (que é uma tarefa bastante comum na minha ponta da internet).

Minha nem tão elegante solução é esta:

select byte1||byte2 from (
  with bytes as (select decode(rownum-1, 
                        least(rownum-1,9), to_char(rownum-1), 
                        chr(rownum-1+65-10)) as byte 
                 from all_tables where rownum<17)
  select b1.byte byte1, b2.byte byte2, rownum-1 valor
  from bytes b1, bytes b2
) where valor=68
A consulta produz, conforme esperado, o valor 44.