Fatoração de Fermat

A soma dos números ímpares gera quadrados perfeitos: 1=1*1, 1+3=2*2, 1+3+5=3*3, 1+3+5+9=4*4, e assim por diante.

Além disso, todo número ímpar pode ser representado como a diferença entre dois quadrados (embora nem todas as diferenças de quadrados resultem num número ímpar).

Então, 16-1=15 ou 9-4=5, ou 25-16=9.

Fermat usou essa propriedade para fatorar inteiros. Dado um inteiro N ímpar, começamos pela raíz quadrada (a) e vamos procurando um valor b tal que a*a-N=b*b.

Dado que a soma da sequência de inteiros ímpares produz um quadrado perfeito, podemos usar isso para encontrar b.

Então, com 15, fazemos assim: 15+1=16. Essa é fácil: 16 é quadrado e 1 também. Isso nos dá que 15=(4-1)(4+1).

Vamos usar 39 como um exemplo mais difícil. 39+1+3+5+7+9=64 e (8-5)(8+5)=3*13=39.

Então encontramos soluções do tipo (b-c)(b+c) e c é o número de ímpares na sequência que somamos ao número que estamos tentando fatorar. No caso do número 39, acabamos passando por 49 e isso serviu para demonstrar como é mais fácil fatorar um número quando a solução está perto da raíz quadrada. Quanto mais longe (isto é, quanto mais distantes estiverem os fatores), mais difícil vai ser encontrar a solução.

Resíduos Quadráticos

O resto da divisão de um quadrado por 100 só pode ter um de 22 valores distintos:

 {00,01,04,09,16,25,36,49,64,81,21,24,29,41,44,56,61,69,76,84,89,96} 

Isto acelera os testes feitos manualmente. Mas a base 100 só é realmente melhor para os humanos.

Uma verificação rápida das bases até 256, revela que algumas têm porcentagens menores de resíduos quadráticos:

80=>12 (15%)
96=>14 (14%)
112=>16 (14%)
120=>18 (15%)
144=>16 (11%)
160=>21 (13%)
168=>24 (14%)
176=>24 (13%)
180=>24 (13%)
192=>24 (12%)
208=>28 (13%)
216=>33 (15%)
224=>28 (12%)
240=>24 (10%)
252=>32 (12%)

256 tem apenas 44 (17%). Não é a melhor, mas simplifica bastante o teste: basta conferir o último byte.

Ampliando a busca para 2 bytes, aparecem alguns valores supreendentes cujos resíduos quadráticos cobrem apenas 2% das possibilidades.

Por exemplo, o mais próximo de 65.536 é 65.520=>1.344 (2%).

Se, por outro lado, contarmos os resíduos quadráticos das bases impares, encontramos 50% quando a base é um número primo, o que constitui uma forma diferente de identificar primos.

Sobre Bases e Quadrados Perfeitos

O teste de divisibilidade por 3 ou 9 consiste em somar os dígitos e verificar se o resultado é múltiplo de 3 ou 9.

Por exemplo, 25 não é divisível por 3 ou 9, porque 2+5=7. Mas 3627 é, porque 3+6+2+7=18.

O interessante deste teste é que ele pode ser generalizado para outras bases. Ele funciona em base 10, porque 9 é 10-1 (e 3 divide 9). Em base 3, ele seria o teste do 2; em base 8, seria o teste do 7.

Vejamos os seguintes múltiplos de 7 em base 8:

• 14 => 16₈
• 21 => 25₈
• 28 => 34₈
• 49 => 61₈

Outro jogo interessante com bases é que o quadrado de n tem sempre a forma [n-1,1] na base n+1:

1*1=1 (base 2)
2*2=11 (base 3)
3*3=21 (base 4)
4*4=31 (base 5)
5*5=41 (base 6)
6*6=51 (base 7)
7*7=61 (base 8)
8*8=71 (base 9)
9*9=81 (base 10)
10*10=91 (base 11)
11*11=A1 (base 12)
12*12=B1 (base 13)
13*13=C1 (base 14)
14*14=D1 (base 15)
15*15=E1 (base 16)
16*16=F1 (base 17)
17*17=G1 (base 18)
18*18=H1 (base 19)
19*19=I1 (base 20)
20*20=J1 (base 21)

Não chega a surpreender, dado que n*n=(n+1)(n-1)+1.

Wordle

Wordle é a sensção do momento e com razão: o jogo é cativante. Ele surgiu em Outubro de 2021 e já existem inúmeras versões para todas as plataformas. Até mesmo os micros de 8 bits já têm suas versões.

Após jogar compulsivamente por alguns dias e chegar a uma tática bastante exitosa (iniciar sempre com as palavras AMBER e THUDS), resolvi analisar as palavras de 5 letras para entender melhor o problema.

Inicialmente, filtrei um dicionário para deixar apenas as palavras de 5 letras:

grep -Po "^[A-Za-z]{5}$" words.txt  | tr '[:upper:]' '[:lower:]'  > fives.txt

Depois analisei as frequências das letras:

fold -w 1 fives.txt  | sort | uniq -c | sort -nr
  12336 a
  10908 e
   8280 s
   7253 i
   7166 o
   7107 r
   6108 l
   5988 n
   5384 t
   4380 u
   3893 d
   3621 c
   3455 m
   3451 y
   3182 h
   2943 b
   2891 p
   2593 g
   2462 k
   1614 f
   1485 w
   1247 v
    760 z
    630 j
    459 x
    164 q
    
 

Então, filtrei as palavras com as 10 letras mais comuns:

grep -Po "^[aesiorlntu]+$" fives.txt  | wc -l
2089

São muitas, então filtrei as que não repetem letras:

grep -Po "^[aesiorlntu]+$" fives.txt  | grep -Ev '(.).*\1' | wc -l
888

Desta lista reduzida, podemos tirar algumas palavras interessantes. O desafio é selecionar duas palavras que juntas tenham as 10 letras mais frequentes.

join -j 2 best.txt best.txt \
 | grep a \
 | grep e \
 | grep s \
 | grep i \
 | grep o \
 | grep r \
 | grep l \
 | grep n \
 | grep t \
 | grep u \
 | sort | uniq | wc -l
2934

Tem muitas combinações de duas palavras com as 10 letras mais comuns em palavras de 5 letras, basta selecionar uma combinação. Por exemplo, "latin euros". O dicionário que escolhi talvez seja completo demais: ele inclui nomes próprios. Vasculhando um pouco, encontrei a dupla "nails route". Doravante, iniciarei as partidas com essa dupla.

Latin Euros vou guardar para o nome de meu grupo de Deep House Salsa.

Chave Naturalizada

Ao analisar um conjunto novo de tabelas, encontrei algo pouco usual: uma chave estrangeira que também é primária.

Esse mecanismo só pode representar uma relação 1:1 ou 1:0..1. Sim, seria possível colocar tudo numa só tabela, mas há motivos razoáveis para separar: controle de acesso para informações sensíveis, desempenho, e economia de espaço (no caso de uma relação 1:0..1) .

Imaginei que essa configuração tivesse um nome, mas não pude encontrar. Então, tive que inventar um: chave naturalizada.

Ela é naturalizada porque é estrangeira, mas é parte fundamental na tabela secundária por ser primária também.

Outras ideias que me ocorreram: 

• chave imigrante - descartada porque dá ideia de algo dinâmico;
• chave agente duplo - descartada porque dá a ideia de conflito ou traição;

Então, essa construção rara será doravante conhecida como chave naturalizada.

Como a Oracle rouba seu tempo

Tradicionalmente, a Microsoft tem a pior fama no reino da informática. Mas eu acho injusta essa posição. Acho que a Oracle deveria ser a campeã.

Apesar do histórico de práticas anticompetitivas, os produtos da Microsoft são razoáveis. Eles funcionam bem a maior parte do tempo.

A Oracle, entretanto, parece ter forjado um modelo de negócios a partir de bugs e manuais mal-escritos (ou simplesmente errados).

Nenhum software rouba tanto o meu tempo como os da Oracle.

Vou dar um exemplo que tem me ocupado nos últimos meses: o OAM - Oracle Access Manager. Em teoria, é um produto excelente (no marketing, a Oracle não economiza). O dia-a-dia, entretanto, é infernal.

O primeiro sinal de que a vida vai ser difícil começa logo na instalação. É preciso rodar um patch para o instalador funcionar. Não, o instalador não  deve ter sido testado. E não é que eu tenha usado um sistema operacional obscuro: usei o Oracle Linux Server 8.4.

$ java -jar fmw_12.2.1.4.0_idm.jar \\
  -prereqConfigLoc \\
  /tmp/31190532/prereq_metadata/oracle.as.install.oid.prerequisite/prereq

Então, para configurar uma regra de autenticação, encontrei uma sequência inacreditável de erros:

1. A sintaxe não é completamente descrita no manual;
2. O exemplo dado na documentação está errado desde a versão  11.1.2.2.0 (Doc ID 1928071.1);
   
3. Na versão 12.2.1.4, o parser tem bug, então é preciso desabilitar a verificação da sintaxe (Doc ID 2664614.1).

Nunca atribua à malícia o que pode ser adequadamente explicado pela burrice, diz a Navalha de Hanlon, mas eu, no meio da minha revolta e angústia por perder tanto tempo com esse tipo de erro, fico a pensar que é muito conveniente para vender suporte esse tipo de falha.

O que sugiro é que quem possa evite ao máximo essa empresa. Use Linux, use Postgresql. Não há motivo são para uma empresa entrar hoje na seara da Oracle.

Lições sobre Teletrabalho em 2020

Em 2020, minha casa virou um escritório e uma escola. Ela não estava preparada. Aos poucos fui adaptando, cometi alguns erros e achei algumas soluções. Abaixo, seguem as principais lições. 

1. A melhor rede usa cabos 

Wifi pode ser prático, mas não funciona bem com uso pesado de várias pessoas. Mesmo após segmentar a casa com redes em canais diferentes, a solução mais eficaz foi a de usar um Powerline. Além disso, só cabear a casa toda melhoraria a rede. 

2. Compre uma impressora laser com impressão duplex 

Eu fiquei dividido entre uma impressora laser com Wifi e uma com impressão duplex. Escolhi a que tem Wifi, mas a prática revelou que o duplex teria sido mais prático. De qualquer forma, é muito melhor que usar uma impressoa a jato de tinta. As impressoras da Brother são muito boas e funcionam com o Linux.

3. Memória, memória, memória 

Quando iniciei 2020, nenhuma máquina tinha mais que 4GB de RAM. Agora, as que estão em uso contínuo têm de 8GB a 12GB de RAM. O notebook mais antigo tem um processador Core 2 Duo e iniciou o ano com apenas 2GB de RAM. Adicionei mais 1GB e ele rodou o MS Teams muito bem durante o ano todo. Ele roda Ubuntu Mate e usa um SSD. Se fosse Windows com HD, não tenho certeza que teria o mesmo sucesso. Nenhum micro é muito novo (os principais têm um Core i3 540 e um Athlon II X2 270), mas com bastante memória eles funcionam perfeitamente bem apesar de já terem uma década. Os maiores consumidores de memória são os navegadores.

4. Como prolongar a vida de máquinas antigas

Minhas máquinas são antigas, mas servem às minhas necessidades muito bem. Para atingir um desempenho ótimo, elas precisaram de 3 coisas: memória, placas de vídeo, e drive SSD (ao menos para o Sistema Operacional). A placa de vídeo não precisa ser a mais moderna; pode ser a mais antiga disponível (exceto se a intenção for jogar). Um micro usa uma Geforce GT210 e outro usa uma Geforce GT710. Além disso, o SSD também não precisa ser muito grande, basta usá-lo apenas para o Sistema Operacional. Então, com cerca de R$650,00 (R$300,00 por uma placa de vídeo, R$200,00 por um SSD, e cerca de R$150,00 por um pente de 4GB de RAM) é possível transformar um micro antigo numa estação com bom desempenho. Com R$1.000,00 é possível comprar um micro novo, mas ele não vai ter o mesmo desempenho.

O reaproveitamento de máquinas com mais de 10 anos de uso mostrou como o desenvolvimento dos micros tem desacelerado. Em 2021 alguns micros clássicos estão completando 40 anos. Em 1981, muitas pessoas compravam micros com apenas 1KB ou 2KB de RAM. Em 1985, o Amiga 1000 foi lançado com 256KB de RAM. Atualmente, máquinas com 10 ou até 15 anos servem para a maior parte dos casos de uso doméstico.