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.

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.

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.

Terceira volta

Educação, disse Einstein, é o que nos resta após termos esquecido tudo o que nos ensinaram na escola. Tendo me formado há mais anos do que eu gostaria de mencionar, posso agora seguramente estimar o que terá sobrado das cadeiras que cursei no Instituto de Informática da UFRGS.

Há muito tempo eu tinha a certeza de que algo faltava no curso e após ler um texto de Richard Feynman sobre a educação no Brasil, pude perceber claramente que era a realidade. Alguns exemplos estão claros na minha memória. Em primeiro lugar, a insistência no modelo OSI e nos detalhes da sintaxe do ASN.1 nas aulas de redes. Em segundo, as aulas de autômatos sem nenhuma menção às expressões regulares (lendo o Mastering Regular Expressions, finalmente compreendi o papel de NFAs e DFAs). Em terceiro, o professor de Sistemas Operacionais que nos propôs escrever um montador antes mesmo de mencionar o Lex e o Yacc (e no ano anterior à cadeira de compiladores). Nem preciso entrar no mérito de cadeiras como "Computador e Sociedade".

Obviamente, o propósito do curso não era ensinar informática. No entanto, algum mérito deve ter tido o curso, porque eu dificilmente o trocaria por outro no estado (não descarto a possibilidade de que seja apenas empáfia acadêmica). E o que restou após quatro anos de matérias e tarefas abstratas e aparentemente sem benefícios práticos foi a habilidade de enfrentar problemas novos e em áreas que não domino. Normalmente, a isso dar-se-ia o nome técnico de picaretagem, mas garanto que os egressos da UFRGS o fazem com muita propriedade e com as devidas referências bibliográficas.

Mesmo assim, acho que o currículo deveria ser reformado radicalmente. É preciso tirar a ilusão de que as matérias têm algum valor prático. Nos meus anos de faculdade, brincava-se sobre a cadeira de Corte e Costura para Processamento de Dados. Ela não serve, porque tem valor prático.

Acho que o Instituto de Informática precisa de cadeiras verdadeiramente abstratas, inúteis e arbitrariamente complicadas. Proponho estudos como Lacumetria Antropométrica (medição de lagos usando partes do corpo humano como unidade). Ou então Filatelia Computacional (estudo de selos com referências à informática). Finalmente, a minha favorita, a Kleroterionologia (estudo dos aparelhos usados pelos gregos antigos em suas eleições). Tenho certeza que a SBC compreenderá!

Quantum Countdown Sort

O Countdown Sort já foi otimizado e agora entra para o reino quântico!

O módulo Quantum::Superpositions agrega dois operadores ao Perl: all e any. Eles recebem como parâmetro uma lista que é comprimida para um único valor que é a sobreposição de todos os valores da lista original. Então, magicamente, podemos realizar operações e comparações simultâneas sobre todos os valores de uma lista.

Fundamentalmente, o Countdown Sort é simples. Ele percorre uma lista de números positivos, subtraindo 1 de cada valor; cada vez que a subtração resultar em 0, o elemento original correspondente é adicionado à lista ordenada.

Com a sobreposição quântica, podemos simplificar substancialmente o código. Quanto a melhorar o desempenho, teremos que esperar um computador quântico.

use Quantum::Superpositions;

sub quantum_countdown_sort {
  my @unsorted=@_;
  my @sorted=();
  my $d=0;
  
  while($#sorted<$#unsorted) {
    push(@sorted, $d) if any(@unsorted)-$d==0;
    $d++;
  }
  
  return @sorted;
}

E um pequeno teste confirma que a rotina realmente funciona:

print join ',', quantum_countdown_sort 10,25,2,30,0,1,11;
0,1,2,10,11,25,30

O nome do método já garante a seriedade do pesquisador!

IIN

Os economistas têm uma infinidade de índices para avaliar as economias, mas eu quero propor um novo. Creio que o melhor medidor do potencial econômico de uma nação seria o Índice da Incompetência Nacional.

Há um bom tempo eu venho elaborando esta idéia; recentemente mudei-me e precisei de vários prestadores de serviços e graças à incompetência generalizada deles, pude completar a idéia para o meu índice.

Em primeiro lugar, há a dimensão da pontualidade. Não é que tenham dificuldade em acertar o horário, é que muitos não conseguem sequer chegar no dia combinado!

Em segundo lugar (e acho que essa é uma das dimensões mais importantes do IIN) está a espetacular dificuldade de comunicação. Eles não são capazes de avisar que vão atrasar-se dois dias. Tampouco são capazes de enumerar as peças que devemos comprar ou as ações que devemos tomar com 48h de antecedência. Tampouco são capazes de compreender frases simples, como "pinte esta parede de azul" ou "não vou estar aqui à tarde".

E a incompetência não está restrita ao aspecto gerencial de suas profissões. Os prestadores de serviços esquecem suas ferramentas (tanto de trazê-las como de levá-las), deixam obras inacabadas (e perigosas, como vazamentos de gás) e danificam tudo que está ao redor do seu ponto focal. A sujeira que deixam para trás é insignificante perto da má qualidade da execução.

Se olharmos aos países vizinhos, veremos que há países com economias menos diversificadas e com menor produção de tecnologia, mas cujos padrões de vida são significativamente melhores. Refiro-me ao Chile, ao Uruguai e à Argentina. A única explicação que tenho a dar é que o IIN deles deve ser muito menor.

Epidemia

Eu vasculho os logs do meu sistema e encontro ocorrências sempre em grupos de duas ou três. De quando em vez, são quatro ou cinco. Minha primeira conclusão é que as pessoas estão premindo os botões duas vezes, mas os intervalos de tempo são relativativamente grandes entre os registros repetidos (trinta segundos ou dois minutos).

Pode ser uma epidemia de transtorno obsessivo-compulsivo. Aparentemente, o transtorno está relacionado a um QI mais alto e, curiosamente, nosso país tem uma incidência alta. Infelizmente, os argentinos têm mais ainda. Talvez seja sobre esse tipo de coisa que Gödel quebrava a cabeça: ter muito TOC é bom ou ruim? Definitivamente, não consigo decidir.

Além disso, não há nada para fazer. Se meus usuários estivessem abusando do duplo-clique (já vi quem fizesse um quádruplo clique), eu poderia desabilitar o botão depois do primeiro clique. Talvez eu possa adicionar um contador à página: você já fez isso 9 vezes. Mas não quero que fiquem, ademais, paranoicos.

Por enquanto, vou lavar as mãos.