Prova visual da divergência da série harmônica

A série harmônica é dada por:

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!

Vide também:

https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)

Exercício – cifra de substituição simples

Aproveitando a onda do post anterior (https://ideiasesquecidas.com/2021/10/11/escaravelho-dourado-decifre-o-enigma-de-allan-poe-com-python/), segue um pequeno exercício.

Qual a mensagem abaixo, sabendo que é uma cifra de substituição simples, e está escrito em português brasileiro?

)%__#<]%-<;<]_<)%__#](<%;?<(?[<+%:?#?;[|*_?)?_)&<[)$<%@}??$-?$;?##<)+%:?$<%?$-?$;?)?_)&<[)+%:?:_@&<)?_)&<[)&%(-_;%?[))%?<>)_(;%)<%:([<$:<):%#%+%:?%*_?+%:?+<[)?(*_<$;%+%:?:(?):?(

Att

Escaravelho Dourado: decifre o enigma de Allan Poe com Python

“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.

53‡‡†305))6;4826)4‡.)4‡);80 6;48†8¶60))85;1‡(;:‡8†83(88) 5†;46(;8896?;8)‡(;485);5

2:‡(;49562(5-4)8¶8;40692

85);)6†8)4‡‡;1(‡9;48081;8:8‡1

;48†85;4)485†528806*81(‡9;48

;(88;4(‡?34;48)4‡;161;:188;‡?;

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.

strOriginal = "53‡‡†305))6;4826)4‡.)4‡);806;48†8¶60))85;1‡(;:‡8†83(88)5†;46(;8896?;8)‡(;485);5†2:‡(;49562(5-4)8¶8;4069285);)6†8)4‡‡;1(‡9;48081;8:8‡1;48†85;4)485†528806*81(‡9;48;(88;4(‡?34;48)4‡;161;:188;‡?;"

caracteres = set(strOriginal)

A seguir, podemos contar o número de vezes que cada caractere aparece na string, e imprimir o resultado:

dictCaract ={}

for ch in caracteres:
dictCaract[ch] = strOriginal.count(ch)

for i in sorted(dictCaract, key = dictCaract.get, reverse=True):
print(i, dictCaract[i])

Resultado:
8 33
; 26
4 19
‡ 16
) 16

13
5 12
6 11
( 10
1 8
† 8
0 6
2 5
9 5
: 4
3 4
? 3
¶ 2
. 1

-1

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.

Em Python, é só usar a função replace:

str2 = strOriginal.replace('8','E')
str2 = str2.replace(';','T')
str2 = str2.replace('4','H')

Resulta em:

53‡‡†305))6THE26)H‡.)H‡)TE06THE†E¶60))E5T1‡(T:‡E†E3(EE)5†TH6(TEE96?TE)‡(THE5)T5†2:‡(TH9562(5-H)E¶ETH0692E5)T)6†E)H‡‡T1(‡9THE0E1TE:E‡1THE†E5TH)HE5†52EE06*E1(‡9THET(EETH(‡?3HTHE)H‡T161T:1EET‡?T

Ainda bastante ininteligível, porém, um pouco mais familiar.

Pescando algumas palavras, há um trecho assim: ‘t(ee’, que pode ser ‘tree’, indicando a substituição ‘(‘ -> ‘R’.

O trecho fica:
the tree thr‡?3h the.

A palavra ‘through’ indica novas letras ‘O’, ‘U’ e ‘G’, representadas por ‘‡’, ‘?’ e ‘3’.

No Python, letra por letra (é possível por outros meios em massa, mas assim é mais didático).

str2 = str2.replace('(','R')

str2 = str2.replace('‡','O')
str2 = str2.replace('?','U')
str2 = str2.replace('3','G')

Resultando em:

5GOO†G05))6THE26)HO.)HO)TE06THE†E¶60))E5T1ORT:OE†EGREE)5†TH6RTEE96UTE)ORTHE5)T5†2:ORTH9562R5-H)E¶ETH0692E5)T)6†E)HOOT1RO9THE0E1TE:EO1THE†E5TH)HE5†52EE06*E1RO9THETREETHROUGHTHE)HOT161T:1EETOUT

Outras pistas:
†83(88, ou †egree,

Deixando clara a palavra ‘degree’, e a substituição ‘†’ por ‘D’.

Outro trecho parcialmente traduzido fica ”TH6RTEE‘, evidentemente ‘thirteen’, ‘6’ -> ‘I’ e ‘‘ -> ‘N’.

O início, ‘5GOOD’, indica o ‘5’ como ‘A’.

Colocando todas as pistas no Python, temos:

str2 = str2.replace('†','D')
str2 = str2.replace('6','I')
str2 = str2.replace('*','N')

str2 = str2.replace('5','A')

Texto parcialmente decifrado:

AGOODG0A))INTHE2I)HO.)HO)TE0INTHEDE¶I0))EAT1ORT:ONEDEGREE)ANDTHIRTEEN9INUTE)NORTHEA)TAND2:NORTH9AIN2RAN-H)E¶ENTH0I92EA)T)IDE)HOOT1RO9THE0E1TE:EO1THEDEATH)HEADA2EE0INE1RO9THETREETHROUGHTHE)HOT1I1T:1EETOUT

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.

Fechando a cifra:

str2 = str2.replace('0','L')
str2 = str2.replace(')','S')
str2 = str2.replace('2','B')
str2 = str2.replace('.','P')
str2 = str2.replace('¶','V')
str2 = str2.replace('1','F')
str2 = str2.replace(':','Y')
str2 = str2.replace('9','M')
str2 = str2.replace('-','C')

Resulta em:

AGOODGLASSINTHEBISHOPSHOSTELINTHEDEVILSSEATFORTYONEDEGREESANDTHIRTEENMINUTESNORTHEASTANDBYNORTHMAINBRANCHSEVENTHLIMBEASTSIDESHOOTFROMTHELEFTEYEOFTHEDEATHSHEADABEELINEFROMTHETREETHROUGHTHESHOTFIFTYFEETOUT

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.

Vide o código completo no Colab: https://colab.research.google.com/drive/1l1MztHdxUHdJl1yW4NZzn1heDUvoSoJJ?usp=sharing

Visite o meu blog pessoal https://ideiasesquecidas.com/

Conto ‘Golden Bug’, de Edgar Allan Poe https://poestories.com/read/goldbug

Conto em português, “O Escaravelho Dourado”

Teseu e o labirinto do Minotauro

Segue um presente de dia das crianças: um gerador de labirintos em Excel.

A minha filha do meio adora labirintos, mas os labirintos da banca de jornais são ou muito fáceis ou muito difíceis.

Com o gerador de labirintos, é possível criar no tamanho desejado:

O algoritmo utilizado é simples. Comece com um retângulo, escolha uma linha horizontal, uma vertical aleatórias, e crie duas saídas também aleatórias.

Repita nos quatro retângulos que sobraram, e assim sucessivamente.

O resto da macro é só para pintar as bordas.

Boa diversão!

Planilha para download: https://1drv.ms/x/s!Aumr1P3FaK7jn06fAdaS-_v1O6RB

Veja também:

https://ferramentasexcelvba.wordpress.com

Prova visual de soma de potências de quartos

A série 1/4 + 1/4^2 + 1/4^3 + 1/4^4 + … = 1/3 tem uma bela visualização, mostrada abaixo:

Considere só os quadrados azuis. As demais cores são para completar os 2/3 restantes.

Gif animado:

Para acessar o painel iterativo: https://asgunzi.github.io/Soma-quartos/index.html

Contraprova visual do Pequeno Teorema de Fermat

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.

Veja também:

Prova visual do 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

Código fonte do desenho das bolinhas no Github: https://github.com/asgunzi/Prova-Visual-Pequeno-Teor-Fermat

Veja também:

Fontes – Advanced Analytics e AI

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/

John D. Cook tem um blog e twitter de alto nível, sobre matemática e programação https://www.johndcook.com/blog/

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:

Para fechar, é claro, sigam o meu blog de Ideias Técnicas com uma pitada de filosofia: https://ideiasesquecidas.com/

Fiquem à vontade para sugerir outras fontes.

Senos de inteiros

Padrões interessantes surgem, quando plotamos a função seno para números inteiros [sin(1), sin(2), sin(3), …, sin(N)].

Painel interativo aqui:
https://asgunzi.github.io/Senos-inteiros/index.html

Para N = 500, aparecem alguns hexágonos.

Para N = 1000, fica mais evidente.

Para N = 2000:

Para N= 5000:

A mesma coisa, mas com o eixo X em escala logarítmica.

Achei bonito o padrão formado, e resolvi fazer os gráficos.

Este post é baseado em artigo de John Cook, referenciado abaixo.

Veja também:

Prova visual da aproximação de raiz (a + b)

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.

Veja também:

https://ideiasesquecidas.com/laboratorio-de-matematica

Números Triangulares

Números triangulares são aqueles que formam um triângulo, fazendo jus ao próprio nome.

1

3 = 1 +2

6 = 1 +2 + 3

10 = 1 +2 + 3 + 4

Fiz uma animaçãozinha para demonstrar. Para visualização interativa: https://asgunzi.github.io/NumerosTriangulares/

Cada número triangular é a soma da progressão geométrica 1+2+3+…+N, ou seja, podemos usar a fórmula da PG para calcular um número triangular qualquer.

Vide também:

Euclides e a prova visual dos primos

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.

Veja também:

https://ideiasesquecidas.com/2021/08/25/poligonos-e-conexoes/