Ela tem esse nome por conta do conceito de harmônicas, em música. Imagine prender uma corda de piano a um tamanho 1, depois a metade do tamanho, 1/3 do tamanho, etc.
É um resultado conhecido desde Bernoulli, no séc XVII, que a série harmônica diverge: o somatório dos termos tende a infinito.
A prova dos livros de matemática consiste em comparar com uma série conhecidamente divergente:
1/2 + 1/2 + 1/2 + …
Se eu somar o número 1/2 infinitamente, claramente a série vai divergir.
A série harmônica é maior do que a série divergente acima, basta rearranjar os termos. A figura acima ilustra as operações envolvidas.
Embora a série harmônica divirja, ela o faz muito lentamente.
Um programinha de 4 linhas em Python, para 1000 termos:
harmonic=0 for i in range(1,1001): harmonic += 1/i print(harmonic)
Para 1000 termos, a soma dá 7,48.
Para 1 milhão de termos, a soma dá 14,39.
A soma dos primeiros 1043 termos é menor do que 100, segundo a Wikipedia, cujo link consta abaixo e tem outras informações interessantes.
É como a tartaruga do conto de Esopo: parece que nunca vai chegar lá, mas lenta e consistentemente, sempre cruza a linha de chegada!
“O Escaravelho Dourado” é um pequeno conto, do escritor americano Edgar Allan Poe, publicado em 1843.
O enredo narra a história de William Legrand, supostamente picado por um escaravelho dourado. Seu servo Júpiter teme que Legrand fique louco, e com a ajuda do narrador anônimo, partem para uma aventura que envolve uma mensagem criptografada e um tesouro escondido.
Sem mais delongas, os aventureiros se depararam com a seguinte mensagem.
A primeira informação é que a mensagem está em inglês. O narrador cita que, tendo decifrado inúmeras mensagens criptogradas, é essencial saber qual a linguagem em que este está escrito.
A seguir, ele faz uma contagem dos caracteres existentes.
Em Python, podemos utilizar um set para listar os caracteres únicos, como mostra o código a seguir.
O caractere ‘8’ aparece 33 vezes, seguido pelo caractere ‘;’, 26 vezes. Em inglês, “e” é a letra mais comum, então um bom chute é considerar ‘8’ -> ‘E’. Vou utilizar maiúsculas para indicar a string trocada.
A seguir, o narrador nota que a cadeia de strings ‘;48’ aparece com grande frequência no texto, e o último caractere é “E”.
O ‘THE’ é um artigo bastante comum na língua inglesa, de modo que as substituições ‘;’ -> ‘T’, ‘4’ -> ‘H’ parecem ser um bom chute.
Allan Poe para por aí, dizendo que o resto segue a mesma lógica, e realmente não é difícil. Por exemplo, ‘9INUTE)’ significa ‘MINUTES’; pelo contexto de direção, ‘NORTHEA)T’ significa ‘NORTHEAST’ e assim por diante.
Como está sem pontuação e espaço, estes devem ser inseridos:
“A good glass in the Bishop’s hostel in the Devil’s seat — forty-one degrees and thirteen minutes — northeast and by north — main branch seventh limb east side — shoot from the left eye of the death’s-head — a bee-line from the tree through the shot fifty feet out.'”
[Um bom vidro no hotel do bispo na cadeira do diabo – quarenta e um graus e treze minutos nordeste quadrante norte – tronco principal sétimo galho lado leste – atirai do olho esquerdo da caveira – uma linha de abelha da árvore através o tiro cinqüenta pés distante.]
Esta é uma cifra de substituição simples, onde cada palavra é trocada por um caracter específico. Sabendo o dicionário, é possível cifrar e decifrar uma mensagem. Cifras deste tipo são conhecidas desde o Império Romano, e são muito frágeis, bastando um ataque de contagem e força bruta, como demonstrados no conto. Atualmente, há métodos de chave assimétrica como o RSA, extremamente mais avançados. Porém, na época de Allan Poe, este era o melhor que existia, e o conto do “Escaravelho dourado” ajudou a popularizar a ciência da criptografia.
Em post anterior, vimos uma prova visual do Pequeno Teorema de Fermat.
Neste post, vamos ilustrar o mesmo raciocínio, mas para mostrar porque o mesmo teorema não funciona quando os números envolvidos não são primos entre si.
O teorema diz que p | n^p – n, para p primo.
Exemplo. n = 3 e p = 5. n^p – n = 3^5 – 3 = 240, e 240 é divisível por 5.
Contra exemplo. n = 2 e p = 4. n^p – n = 2^4 – 2 = 14, e 14 não é divisível por 4 (para o teorema funcionar, p deve ser primo em relação a n).
Vamos visualizar o caso n =2 e p =4.
Há duas combinações de cor única:
Há quatro combinações com 1 azul e 3 brancos. Note o mesmo comportamento descrito anteriormente, de poder fazer um colar e ir girando a cada conta. A repetição só se dá quando girar todas as contas.
De modo similar, há quatro combinações com 3 azuis e 1 branco.
Porém, com 2 azuis e 2 brancos, há uma diferença.
O primeiro grupo de 4 forma um colar que precisa de 4 giros para retornar ao início.
Porém, o grupo da direita precisa de apenas 2 giros para retornar à mesma posição. Isso porque há repetição do padrão de cores, e há repetição porque 2 (cores) e 4 (posições) têm divisor comum (2).
Isso “quebra” a formação de grupos de 4, demonstrando o motivo do pequeno Teorema de Fermat não ser válido para n e p com divisores comuns.
Portanto, essa é a forma de visualizar o importante Pequeno Teorema de Fermat.
O Pequeno Teorema de Fermat é uma das joias da Teoria dos Números, e é utilizada, por exemplo, em testes de primalidade para a criptografia moderna.
Ela diz que p | n^p – n, para p primo.
Exemplo. n = 3 e p = 5. n^p – n = 3^5 – 3 = 240, e 240 é divisível por 5.
Exemplo. n = 4 e p = 3. n^p – n = 4^3 – 4 = 60, e 60 é divisível por 3.
Contra exemplo. n = 2 e p = 4. n^p – n = 2^4 – 2 = 14, e 14 não é divisível por 4 (para o teorema funcionar, p deve ser primo em relação a n).
Não confundir com o Grande Teorema de Fermat, aquele que ficou famoso por demorar 300 anos para ser resolvido. O matemático Pierre de Fermat dizia ter a prova na cabeça, mas não cabia no rodapé do livro que ele estava anotando.
O Pequeno Teorema de Fermat tem uma prova combinatória / visualização muito bonita.
A primeira observação é que n^p é uma fórmula muito conhecida em análise combinatória. Por exemplo, se p=3 posições (as três bolinhas abaixo) e n = 4 cores, n^p indica o número de combinações de cores para pintar as três bolinhas de forma diferente (onde a ordem importa).
A segunda observação. Há n = 4 cores únicas, então se eu pintar as p = 3 bolinhas apenas com uma cor, tenho 4 possibilidades.
Assim, n^p – n = 4^3 – 4 = 60 combinações possíveis de todas as cores para pintar 3 bolinhas, tirando as cores únicas.
Vamos ver as combinações de duas cores. Há 36 formas de colorir as três contas, usando as 4 cores combinadas duas a duas.
O argumento aqui é que, naturalmente, as cores se juntam em grupos de tamanho p.
Imagine cada coluna como se fosse um colar. Se eu amarrar o topo da linha com a base, tenho um círculo. Tenho que girar cada conta p vezes para ela se repetir, porque p é primo entre si com n – não vai haver uma combinação da mesma cor sem girar p posições.
Para combinações de três cores, vide esquema abaixo.
Há 24 formas de colorir as três contas, usando as 4 cores combinadas três a três.
Portanto 24 combinações 3 a 3, mais 36 combinações 2 a 2, mais 4 combinações únicas dá 64 combinações possíveis (igual a 4^3). Tirando as 4 combinações únicas, as outras combinações naturalmente formam grupos de periodicidade p = 3.
Em post seguinte, vou mostrar um contra-exemplo visual, para ilustrar como dois números divisíveis entre si provocam uma repetição, e assim as combinações não se agrupam naturalmente em múltiplos de p.
Trilha sonora: Louis Armstrong – What a Wonderful World
Compartilhando algumas boas fontes de Advanced Analytics e AI que utilizo, e solicito ajuda de vocês, para indicar outros links legais e pessoas a seguir.
O Exponential View envia um newsletter com gráficos extremamente bonitos e análises diversas. https://www.exponentialview.co/
Na plataforma Medium, é possível ler e escrever sobre temas de interesse. Esses artigos são reunidos em revistas, com uma excelente curadoria de conteúdo. https://medium.com/
Instituições: A brasileira SOBRAPO (https://sobrapo.org.br/) e a americana Informs (https://www.informs.org/) são referência em eventos e publicações de Pesquisa Operacional, um pouco mais tradicionais. Já a Association For The Advancement Of Artificial Intelligence é voltada à IA https://www.aaai.org/.
Sobre Quantum computing:
O Qiskit é a linguagem da IBM sobre o tema. Esta também promove Desafios e Escola de Verão. https://qiskit.org/
Scott Aaronson é um dos maiores especialistas do mundo no assunto, e escreve um blog de altíssimo nível técnico. https://www.scottaaronson.com/blog/
Para fechar, é claro, sigam o meu blog de Ideias Técnicas com uma pitada de filosofia: https://ideiasesquecidas.com/
A expressão a seguir fornece uma aproximação da raiz (a + b), quando b<<a (b muito menor que a):
Dá para interpretar facilmente a aproximação, pensando em áreas.
A raiz quadrada de a é o lado do quadrado que tem área a.
Suponha que queremos a raiz de a + b, e o quadrado a seguir tenha exatamente as dimensões desejadas.
Como fazer para encontrar o valor desconhecido x?
Se a área verde é igual a b, metade dela será b/2, e essa área é aproximadamente igual a raiz(a) * x, desprezando a “quina” que não faz parte do retângulo.
Assim, temos x = b/(2*raiz(a)), e a dedução da fórmula citada.
Note que o erro equivale à parte em vermelho do diagrama.
E o erro será menor tanto quanto b for menor do que a.
Um dos resultados mais belos da Matemática é a prova de Euclides, sobre a infinitude dos números primos, escrita há mais de 2.300 anos atrás.
Um número é primo se pode ser dividido apenas por 1 e por si mesmo, sem deixar resto.
A prova é por contradição. Primeiro Euclides supôs que o número de primos fosse finito: {p1, p2, …, pN}.
Para ilustrar, suponha que o conjunto de todos os primos seja formado apenas pelos três primeiros, {2, 3, 5}:
A seguir, Euclides afirmou que existe pelo menos um primo maior do que todos os primos finitos conhecidos: p1p2…*pN +1, ou seja, o produto de todos os primos + 1. Tal número não é divisível por nenhum dos primos anteriores, já que restaria 1 na divisão.
No caso do exemplo, tal número seria igual a 2 * 3 * 5 + 1 = 31.
Visualizando, o novo primo não é divisível por 2:
Nem por 3:
Nem por 5:
Sempre vai restar 1 na divisão.
Portanto, como sempre é possível encontrar esse primo adicional para um conjunto de primos finito, a conclusão é a de que o conjunto dos números primos é infinito.
Você precisa fazer login para comentar.