Primos na Espiral de Ulam

Uma das razões dos números primos serem tão legais se deve ao fato deles se comportarem de forma estranha. Eles parecem aleatórios.

Algumas vezes você tem longos espaços entre dois números primos e, de repente, como os ônibus, vêm dois de uma vez só. No entanto, no fundo no fundo, eles não são completamente aleatórios.

Um matemático Polonês chamado Stanislaw Ulam, que foi para os EUA pouco antes da Segunda Guerra Mundial, estava, depois da guerra, em 1963, assistindo uma apresentação de um trabalho chatíssimo e longo com um papel e uma caneta na mão e resolveu fazer a seguinte brincadeira para se distrair:

No centro do papel colocou o número 1 e foi fazendo uma espiral quadrada com a sequência, conforme a figura abaixo:
ulam1

Depois disso, começou a circular os números primos nesta espiral, conforme a figura a seguir:
ulam2

Ele ficou surpreso pelo fato dos números primos caírem em diagonais. Como todos os números primos, exceto o 2, são números ímpares e como as diagonais nesta espiral alternam entre pares e ímpares, não é surpresa que os números caiam em diagonais alternadas, mas que algumas diagonais tenham mais primos do que outras.

Pouco tempo depois ele resolveu fazer um programa usando o computador MANIAC II para imprimir pixels nos pontos primos (exatamente como eu fiz em vermelho no excel) e conseguiu fazer uma imagem com os números até 65.025 (255 x 255).

Aqui abro um parêntese para falar do MANIAC II.

Ele era um computador criado em 1957 com 4096 words de 48bits (24kbytes) de memória RAM em Magnetic-core Memory e 12288 words de 48bits (576kbytes) em Williams tubes. Em média, uma multiplicação neste computador demorava 180 microsegundos e uma divisão 300 microsegundos. Uma verdadeira eternidade para os tempos de hoje.

Voltando à espiral do Ulam, o que ele conseguiu com a impressão da matriz de 255 x 255 de pixels foi a confirmação do que ele havia visto com 100 números. Realmente há um padrão no qual os números primos aparecem em diagonais, com intervalos, é claro, e algumas diagonais parecem ter mais primos do que outras.

ulam-255x255

Todas as linhas nesta espiral obedecem à seguinte equação quadrática: 4x^2+bx+c

Por exemplo, a diagonal que começa no número 3 tem a seguinte equação: 4x^2-2x+1
3, 13, 31, 57, 91, … (Confira na imagem acima)

Na prática, há uma hipótese de que estas diagonais podem servir para procurarmos números primos grandes, já que algumas diagonais têm mais primos do que outras diagonais. Melhor dizendo, algumas equações quadráticas têm mais chance de retornar números primos do que outras.

Um exemplo de diagonal com 40 números primos em sequência é a seguinte: x^2-x+41 que gera a seguinte sequência de 40 números primos:

41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601 (O 41o número é igual a 41^2 e, portanto, não é primo)

As diagonais com as maiores densidades de números primos conhecidas são a belezuras abaixo:

x^2 + x + 3399714628553118047

e (desculpe, não cabe na tela)

x^2 + x + 332518109806968781031500852571295088573128477514981900349983874538507313

O que interessa nisto tudo, é que, parece que, há fórmulas com mais densidade de primos do que outras (isso ainda não foi provado) e isto pode ajudar a resolver outros problemas, como a hipótese de Goldbach (que diz que todos os números pares maiores do que 2 podem ser expressados pela soma de dois números primos) ou a hipótese da existência de infinitos números primos gêmeos.

Como não poderia faltar, eu fiz uma implementação em javascript para mostrar esse grid, só que em vez de 255 x 255, o grid que eu fiz é de 1000×1000. O resultado está neste link. Obviamente você pode aumentar o tamanho do canvas para gerar coisas grandes, como essa de 25.000.000 de números (5000 x 5000) que eu fiz usando o mesmo código (Clica que aumenta).

ulam-5000x5000

 

Edição das 11:50 (Não podia faltar o código Python. O @jbvsmo depois dirá que está lento….)

#!/usr/bin/env python
import sys,math
import Image
 
size = int(sys.argv[1])
 
def sieveGen(siz):
    l = [2,3,5,7,11,13,17,19,23,29]
    if (siz < 31):
        return l
    for i in xrange(31,siz,2):
        isP = True
        rT = math.sqrt(i)
        for j in l:
            if i%j == 0:
                isP = False
                break
            if j>rT:
                break
        if isP:
            l.append(i)
    return l
 
mySieve = sieveGen(size)
 
 
def isPrime(n):
    if (n == 1):
        return False
    if (n < size):
        return (n in mySieve)
    isP = True
    sqrtN = math.sqrt(n)
    for j in mySieve:
        if (n%j)==0:
            return False
        if (j>sqrtN):
            return True
    return True
 
 
 
 
def spiral(N):
    im = Image.new("RGB", (N, N), "white")
    pix = im.load()
    red = (255,0,0)
    if(N%2):
        x = y = ((N-1)/2)
    else:
        x = y = (N/2)
    N2 = N*N
    dx = 1
    dy = 0
 
    val = 1
    amp = 1
    c = 0
 
    while (val <= N2):
        mvd = 0
        while ((mvd < amp) and (val <= N2)):
            if isPrime(val):
                pix[x-1,y-1] = red
            x += dx
            y += dy
            mvd += 1
            val += 1
 
        c += 1
        if (c == 2):
            c = 0
            amp += 1
 
        if (dx == 1):
            dx,dy = 0,1
        else:
            if (dy == 1):
                dx,dy = -1,0
            else: 
                if (dx == -1):
                    dx,dy = 0,-1
                else:
                    if (dy == -1):
                        dy,dx = 0,1
    im.transpose(Image.FLIP_TOP_BOTTOM).save("ulam.png")
 
spiral(size)

Modernizando as forças armadas com tecnologia

No próximo dia 2 de Julho completar-se-ão 69 anos da partida dos primeiros homens brasileiros para lutar na segunda guerra mundial. Apesar de serem apenas uma gota num oceano de gente que lutou na segunda guerra mundial, estes 25.334 homens deixaram suas famílias, suas casas e até o Flamengo para lutar pela liberdade. Mas voltamos a este assunto depois.

Começo aqui uma série de 4 posts, este será provavelmente o mais longo, falando da necessidade de modernizar nossas forças armadas. Começo pela maior delas o Exército.

Os últimos 10 anos produziram um enorme sucateamento do exército brasileiro, humilhado a tropa e fazendo com que poucas pessoas aspirassem à vocação militar e o desejo de servir o país (ao contrário muitos desejaram se servir do país mamando num cargo público depois de investir num concurso.). Analisando a situação do exército vemos que há várias áreas que necessitam de investimento e dou abaixo alguns exemplos.

Infantaria: “Infantaria és das armas a rainha, por ti daria a vida minha, és a eterna majestade das linhas combatentes…“, assim começa o hino da infantaria, no entanto a realidade é bem diferente. A infantaria não necessita no momento tanto de equipamentos, mas de treinamento. Um soldado precisa efetuar pelo menos 1000 disparos ao ano para manter a proficiência no uso do equipamento, precisa ter exercícios militares constantes e treinamentos em habilidades especiais. Como já se comentou em muitos locais todos os militares no campo de batalha precisam portar pistola. Do contrário os que portam pistola são facilmente identificáveis como oficiais e passam a ter um enorme x na testa para atiradores de elite inimigos.

Cavalaria: Apesar de ser uma das áreas do exército que tem menos atraso, a cavalaria precisa encontrar um substituto para os blindados Leopard e adquirir mais lançadores de foguetes Astros 2020.

Artilharia: Aqui há necessidade de modernização urgente. Principalmente no que tange a defesa anti-aérea. O Brasil precisa adquirir baterias modernas, S-300 Russo ou Patriot. Não podemos manter a política de zero defesa anti-aérea.w

Comunicações: Tecnologia e Internet. Hoje o Brasil tem capacidade zero de engajar numa guerra eletrônica. Se você entrar num quartel sentirá vontade de doar aquele Pentium IV velho que tem guardado em casa. Guerra eletrônica, rede segura de comunicações entre quarteis e instalações militares, comunicação pessoal segura são algumas das necessidades desta área.

Aviação do Exército: atualmente o exército brasileiro tem pouco mais de 80 helicópteros sendo que boa parte não está 100% em condições operacionais. Enquanto a FAB conseguiu adquirir 12 helicópteros de ataque MI-35 o exército não tem nenhum destes. Toda a parte de suporte a divisão paraquedista (que ainda é pequena) depende do apoio da FAB.

Como dizia no começo, no próximo dia 2 de Julho completar-se-ão 69 anos da partida dos primeiros homens brasileiros para lutar na segunda guerra mundial. Apesar de serem apenas uma gota num oceano de gente que lutou na segunda guerra mundial, estes 25.334 homens deixaram suas famílias, suas casas e até o Flamengo para lutar pela liberdade.

José Perácio era um centroavante, ídolo no Botafogo e depois no Flamengo. Após ser campeão carioca pelo Flamengo em 42-43 e jogar parte do campeonato de 44, Perácio foi voluntário para ir combater o Nazismo na Europa. Perácio não morreu em combate, o Flamengo foi tri-campeão e em 1945, após a guerra Perácio voltou a defender o Flamengo.

Muitos destes homens foram para a Europa cantando a canção abaixo, que me deixa arrepiado ao pensar nas circunstâncias e eu me pergunto: será que o Neymar faria o mesmo?


Qual é o maior número que existe?

Suponhamos que estão reunidos quatro amigos numa mesa de bar, um médico, um advogado (os outros estão de olho nas suas carteiras…), um matemático e um engenheiro de computação. Depois de muitas cervejas, para decidir quem paga a conta eles fazem a seguinte disputa: “em quinze segundos, quem escrever o maior número não paga”.

Antes que o advogado garfasse eles escrevendo o maior número que todo mundo escreveu mais 10%, ele costumava cobrar “10 purça” nos seus negócios com o governo, o pessoal estabeleceu algumas regras: não vale escrever algo que não seja calculável (assim elimina o truque do advogado), nem escrever coisas não numéricas como infinito, \aleph_0, etc.

Cada um pegou seu guardanapo e deram a largada.

O advogado escreveu 10000000000000000000000000000 e acabou o tempo.

O médico, um pouco mais sabedor de matemática escreveu 10^{10000000000000000000000000} e acabou o tempo.

O matemático escreveu 10^{10^{10^{10^{10^{10^{10}}}}}} e acabou o tempo.

E o cara da computação escreveu A(100,100), onde A é a função de Ackerman.

Não preciso dizer quem ganhou …

A função de Ackerman é definida para números inteiros maiores ou iguais a 0 pela seguinte descrição:

A(m,n) = n + 1 se m = 0
A(m,n) = A(m-1,1) se m > 0 e n = 0
A(m,n) = A(m-1,A(m,n-1)) se m>0 e n>0

Ou em Python de forma simples:

def A(m,n):
    if m==0:
       return n+1
    if n==0:
       return A(m-1,1)
    return A(m-1,A(m,n-1))

Esta inocente função produz resultados brutalmente gigantes rapidamente. A(4,4) = 2^2^2^2^2^2^2 – 3

Se você quiser ter uma idéia do dano causado por isto vá no seu python e digite: 2**2

A seguir digite: 2**2**2

Depois digite 2**2**2**2

Se fizer isto mais uma vez vai comer toda sua memória e não vai terminar o cálculo.

A(100,100) é um número tão gigante que nós nem temos bytes suficientes no mundo para representá-lo.

Portanto o advogado, o médico e o matemático pagaram as bebidas do cara da computação. Não sabiam eles, que no próximo encontro, iriam pagar de novo, pois o cara da computação sabia uma função ainda mais brutal que a de Ackerman.

Se você quiser saber mais sobre este assunto leia o artigo: “Who Can Name the Bigger Number?.”

numbers

Coréia do Norte e as lições da II guerra mundial

Na sua magistral obra sobre a segunda guerra mundial, o prêmio nobel de literatura e primeiro ministro britânico, Sir Winston Churchill dedica o primeiro volume ao que ele chama de “Preparativos para o desastre“.

Os preparativos para o desastre são uma interessante tese de que a segunda guerra mundial tem sua responsabilidade compartilhada com o pacifismo bocó (aqui eu entrego a minha idade…). Pacifista bocó é todo aquele que sonha com a paz não como um bem, mas como uma forma de se livrar da responsabilidade de garantir a paz mais duradoura.

Um adágio latino afirma, si vis pacem, para bellum; se queres a paz, preparas-te para a guerra. Todos os que defendemos a pátria através das diversas forças armadas queremos a paz, mas sabemos que para tê-la temos que estar preparados para o combate.

Isto acontece agora na península da Coréia. Como já foi falado neste blog, aliás conheci este blog e me ofereci para escrever nele após este texto que cito, é bem provável que a Coréia do Norte não tenha meios para usar as cerca de oito ogivas nucleares que se acredita que possua. A retórica norte-coreana, liderada pelo gordinho Kim, é mais jogar para torcida que uma retórica que visa atos concretos.

Acontece que o mundo não para agora em 2013 com Kim voltando para seu Playstation 3 e o mundo indo tratar de seus negócios depois de mais uma guerra evitada. Se a guerra que Kim consegue hoje é no Battlefield apenas, é provável que em três ou quatro anos ele tenha meios de lançar suas armas nucleares em alvos americanos. Aí pode ser que ele não se contente com ameaçar e depois de criar confusão voltar para seu videogame. Pode ser que ele resolva jogar um jogo de verdade.

Além de Kim outros observam com atenção a dança de Obama e outros líderes. Em concreto o Irã. A depender de como fique a vida de Kim depois desta confusão Ahmadinejad pode achar que é um bom negócio enfrentar os EUA. Os aiatolás podem se convencer de vez que ter armas nucleares é um passe livre para nunca mais serem incomodados pelos EUA.

Da mesma forma que quando Hitler invadiu a zona desmilitarizada do Reno em 1936, anexou a Áustria em 1938 e ainda no mesmo ano tomou os Sudetos, diante o olhar passivo dos aliados, que até 1939 teriam condições de encerrar o III Reich; agora Kim pode ser removido do poder, talvez em quatro anos isto custe uma real guerra nuclear.

Não é possível aceitar agora algo que não seja uma desmilitarização da Coréia do Norte, mesmo que custe uma guerra agora. É melhor uma guerra com um país que tem ogivas mas não tem como entrega-las que uma guerra com uma potência nuclear faminta.

Chegou o momento de tomar os controles do Playstation de Kim Jong-Un. Não é um direito, é um dever.

Si vis pacem, para bellum

Nota do Zeletron: General Patton é o pseudonimo de um oficial das forças armadas que vai escrever de tempos em tempos no Zeletron sobre assuntos de tecnologia ligada a defesa. General Patton como todos os outros autores representa apenas suas próprias opiniões.

Coreia do Norte ameaça atacar os EUA com armas nucleares. E daí?

Eu nasci nos últimos anos da Guerra Fria e enquanto passava as férias em Angra dos Reis, meu tio e minha tia, que trabalhavam com energia nuclear, gostavam de nos explicar como funcionava uma bomba atômica, como era o processo de fusão e fissão nuclear. Naqueles anos, um pouco antes de Mikhail Sergeyevich Gorbachev, vivíamos ainda sob a constante ameaça de uma guerra nuclear.

Quem nasceu depois da guerra fria pode achar esquisito o medo que tínhamos da guerra atômica e do espanto que hoje tive ao ler a notícia de que a Coreia do Norte afirmou estar pronta para atacar os EUA com armas nucleares. Durante a guerra fria falar algo assim era declarar guerra. Hoje os EUA nem deram muita importância ao assunto.

Um amigo de infância que enveredou por carreira de humanas ligou e perguntou: Você acha que isto pode acontecer? Eu respondi a ele e agora detalho um pouco mais.

Pode, mas é altamente improvável pelas razões que vão a seguir.

1) A Coréia do Norte não tem provavelmente como atingir os EUA. É fato que a Coreia do Norte conseguiu colocar um objeto em órbita. Mas daí a ter um ICBM (intercontinental balistic missile) funcionando vai uma distância razoável. O que pode acontecer é que eles joguem a bugiganga nuclear deles para cima e acertem em algum lugar dos EUA, mas daí a dizer que vai acertar em Washington vai uma boa distância.

2) A Coréia do Norte consegue acertar talvez o Havaí com o míssil Musudan-1, mas convenhamos que não é uma coisa que vá lhes ajudar em nada a não ser fazer um novo Pearl Harbor.

3) A Coréia do Norte é louca mas não é burra. Uma das consequências de um ataque nuclear é que o contra-ataque é garantido. É um dos pilares do Mutual Assured Destruction que garantiu a paz durante a guerra fria.

4) É importante notar que China e Rússia, que tem armas atômicas que funcionam, não vão curtir muito um míssil norte coreano que pode estar desgovernado com armas atômicas. Também não vão gostar muito do contra-ataque dos americanos que transformaria Pyongyang e redondezas num grande deserto.

E o que o Kim Jong-un ganha com a bravata? Por enquanto ele ganhou mais sanções e corte de comida que os americanos forneciam como ajuda humanitária. Talvez seja um jogo de cena para manter o poder, talvez seja uma maluquice que lhe custe o poder.

Imagem do Dailymail

É possível alguém “hackear” a eleição do Papa?

Com a gentil permissão do autor, reproduzimos aqui, traduzido para o português o texto do famoso especialista em segurança Bruce Schneier.  Uma versão anterior deste ensaio foi publicada na CNN e é uma expansão do ensaio que Bruce Schneier escreveu no conclave de 2005. O original deste artigo pode ser encontrado no site do autor. Caso você queira saber mais sobre o conclave indicamos este outro site com um resumo.

Conclave 2013

Enquanto o Colégio de Cardeais se prepara para eleger um novo papa, as pessoas que trabalham com segurança tem me perguntado sobre o mecanismo de eleição. Como funciona, e quão difícil seria hackear a votação?

As regras para as eleições papais estão imersas na tradição. João Paulo II modificou-as em 1996, e Bento XVI deixou as regras praticamente intocadas. A “Universi Dominici Gregis sobre a vacância da Sé Apostólica e a eleição do Romano Pontífice” é surpreendentemente detalhada.

Todos os cardeais com menos de 80 são sujeitos ativos para votar. Esperamos, neste conclave, 117 para votar (Nota do Tradutor: a estimativa no dia de hoje é de 115). A eleição tem lugar na Capela Sistina, dirigida pelo Cardeal Camerlengo da Igreja. A cédula é inteiramente baseada em papel, e toda a contagem dos votos é feita à mão. Os votos são secretos, mas todo o resto do procedimento é aberto aos presentes.

Primeiro, há a fase de pré-escrutínio

“Pelo menos duas ou três” cédulas de papel são dadas a cada cardeal, presumivelmente para que um cardeal tenha uma ou outra sobressalente caso de ele cometa um erro. Em seguida, nove gerentes do processo são selecionados aleatoriamente dentre os cardeais: três “escrutinadores” que contam os votos; três “revisores” que verificar os resultados dos escrutinadores, e três “Infirmarii” que recolhem os votos daqueles que estão doentes demais para estar na capela. Diferentes conjuntos de gerentes são escolhidos aleatoriamente para cada votação.

Cada cardeal, incluindo os nove gerentes do processo daquela eleição, escrevem seu escolhido para Papa em uma cédula retangular “na medida do possível com uma letra de que não possa ser identificada como o sua.” Ele, então, dobra o papel longitudinalmente e o segura no ar para que todos vejam.

Quando todos tiverem escrito o seu voto, a fase de escrutínio da eleição começa. Os cardeais se dirigem ao altar um por um. No altar há um cálice grande, com uma patena – uma rodela de metal rasa usada para guardar hóstias durante a Missa – cobrindo o cálice. Cada cardeal coloca sua ficha dobrada sobre a patena. Então ele pega a patena e desliza seu voto dentro do cálice.

Se um cardeal não pode caminhar até o altar, um dos escrutinadores – à vista de todos – faz isso por ele.

Se algum cardeal está demasiado doente para ir à capela, os escrutinadores dão aos Infirmarii uma caixa lacrada com uma ranhura, e os três Infirmarii juntos vão recolher os votos. Se, ainda assim, um cardeal está doente demais para escrever, ele pede a um dos Infirmarii para fazer isso por ele. Na volta a caixa é aberta, e as cédulas são colocados na patena e no cálice, uma de cada vez.

Quando todas as cédulas estão no cálice, o primeiro escrutinador sacode-o várias vezes para misturá-las. Em seguida, o terceiro escrutinador transfere as cédulas, uma por uma, a partir do primeiro cálice para o outro, contando-as no processo. Se o número total de cédulas não está certo, as cédulas são todas queimadas e os votos começam novamente.

Para contar os votos, cada cédula é aberta, e o voto é visto por cada escrutinador, chegando ao terceiro este lê em voz alta. Cada escrutinador escreve o voto numa folha de registro. Isto tudo é feito à vista de todos os cardeais.

O número total de votos que cada pessoa recebeu é escrito em uma folha de papel separada. Cédulas com mais de um nome (votos múltiplos) serão consideradas nulas, e suponho que o mesmo aconteça com as cédulas com nenhum nome escrito nelas (votos em branco). Cédulas ilegíveis ou ambíguas são muito mais prováveis de acontecer, e suponho que eles serão descartadas também.

Depois, há a fase de “pós-escrutínio” feita a contagem dos votos os escrutinadores determinam se há um vencedor. No entanto nós ainda não terminamos.

Após isto os revisores verificar todo o procedimento: cédulas, folhas de anotação, contagem, soma, tudo. E então, as cédulas são queimadas. É daí que a fumaça vem: branco, se um Papa foi eleito, preto se não – a fumaça preta é criada pela adição de água ou um produto químico especial nas cédulas.

Para ser eleito Papa é necessária uma maioria de dois terços dos votos mais um. Este é o ponto da legislação onde o Papa Bento XVI fez uma mudança. Tradicionalmente, uma maioria de dois terços, sempre foi exigida para a eleição. O Papa João Paulo II mudou as regras para que após cerca de 12 dias de infrutíferas votações, uma maioria simples fosse suficiente para eleger um Papa. Bento XVI reverteu essa regra.

Então agora a pergunta: quão difícil é “hackear” este processo?

Em primeiro lugar o sistema é completamente manual, o que impede qualquer tipo e forma de ataque tecnológico que podem atingir os atuais sistemas de votação mundo afora.

Em segundo lugar, o pequeno número de eleitores – todos se conhecem – isto torna impossível que uma pessoa de fora consiga interferir na votação de qualquer maneira. A capela é esvaziada e trancada antes de cada votação. Ninguém vai se vestir como um cardeal e esgueirar-se na Capela Sistina. Em suma, o processo de verificação dos eleitores é o melhor possível.

Um cardeal não pode colocar múltiplas cédulas quando ele vota. O complicado ritual patena e cálice garante que cada cardeal vote apenas uma vez – seu voto é visível – e também mantém uma mão na haste do cálice que contém os outros votos. Não que eles não tenham pensado sobre isso: Os cardeais estão em “sobrepeliz” durante a votação, a sobrepeliz tem mangas de renda translúcidas sob uma curta capa vermelha, isto faz com que truques manuais sejam muito mais difíceis. Além disso, provavelmente a soma seria errada.

As regras prevêem isto de outra forma: “Se durante a abertura das cédulas os escrutinadores encontrarem duas cédulas dobradas de tal maneira que elas pareçam ter sido feitas por um único eleitor, se esses votos têm o mesmo nome, eles são contados como um voto; se no entanto eles tem dois nomes diferentes, nenhum dos dois votos será computado, no entanto, em nenhum dos dois casos a sessão de votação é anulada “. Isso me surpreendeu, pois parece ser mais provável que isto aconteça apenas por acidente e resulte em que os votos de dois cardeais não sejam contados.

Cédulas de votações anteriores são queimadas, o que torna mais difícil utiliza-las para fraudar a urna. Mas há um detalhe pequeno: “Se, acontece uma segunda votação imediatamente após a primeira, as cédulas da primeira votação serão queimada apenas no final, juntamente com as da segunda votação.” Eu suponho que é assim para que haja apenas uma nuvem de fumaça para as duas votações, mas seria mais seguro queimar cada conjunto de cédulas antes da próxima rodada de votação.

Os escrutinadores são os que estão na melhor posição para modificar votos, mas é muito difícil. A contagem é feita em público, e há várias pessoas verificando cada passo. Seria possível que o primeiro escrutinador, se ele fosse bom em passes de mágica, trocar uma cédula de votação por outra antes de registrá-la. Ou para o terceiro escrutinador trocar as cédulas durante o processo de contagem. Fazer uma cédula grande faria este tipo de ataque mais difícil. Outra opção, seria controlar as cédulas em branco melhor, só distribuir uma para cada cardeal em cada votação. Eu suponho que como um cardeal pode mudar de idéia durante o processo de votação faz sentido a distribuição de mais de uma cédula.

Há tanta checagem e rechecagem que é praticamente impossível que um escrutinador anote errado os votos. E, uma vez que os escrutinadores são sorteados aleatoriamente em cada votação, a probabilidade de haver um conluio é extremamente baixo. Talvez uma forma de ataque fosse burlar o sistema de seleção de escrutinadores, que não está bem definido no documento. Manipular a seleção de escrutinadores e revisores parece um primeiro passo necessário para manipular a eleição.

Se existe alguma fragilidade possível no processo seria na contagem.

Não há nenhuma razão real para fazer uma precontagem, isto dá ao escrutinador que faz a transferência uma chance de trocar cédulas legítimas com outras que ele já havia colocado na manga. Agitar o cálice para randomizar as cédulas é inteligente, mas colocar as cédulas em uma bola de arame giratória seria mais seguro – embora menos reverente.

Eu gostaria também de acrescentar a exigência de usar algum tipo de luva branca para evitar que um escrutinador esconda um lápis ou caneta sob a ponta de suas unhas. No entanto a exigência de escrever por extenso o nome do candidato forneça já algum tipo de resistência contra este ataque.

Provavelmente, o maior risco é a complacência. O que pode parecer bonito na sua tradição e ritual durante a primeira votação, poderia facilmente tornar-se pesado e chato depois da vigésima votação, e há a tentação de pegar um ou outro atalho para economizar tempo. Se os cardeais fizerem isto, o processo eleitoral se torna mais vulnerável.

Na mudança do processo em 1996 se permitiu que os cardeais vão à capela para as votações e voltem para seus dormi voltam da capela para suas salas de dormitório, em vez de ser bloqueado na capela o tempo todo, como foi feito anteriormente. Isso torna o processo um pouco menos seguro, mas muito mais confortável.

É claro que, um dos Infirmarii podia fazer o que quisesse ao transcrever o voto de um dos cardeais doentes. Não há nenhuma maneira de evitar isso. No entanto se o cardeal enfermo estiver mais preocupado com isto, que com a privacidade, ele poderia pedir a todos os três Infirmarii que testemunhassem o que foi escrito na cédula.

Há também enormes empecilhos sociais, religiosos na verdade – para aquele que quiser fraudar o voto. A eleição ocorre em uma capela e em um altar. Os cardeais fazem um juramento ao colocar seus votos – mais um dissuasor. O cálice e patena são os instrumentos utilizados para celebrar a Eucaristia, o mais sagrado ato da Igreja Católica. E os escrutinadores são explicitamente exortados a não formar qualquer tipo de conspiração, ou fazer planos para influenciar a eleição, sob pena de excomunhão.

Outro importante risco de segurança no processo é a espionagem do mundo exterior. A eleição deve ser um processo completamente fechado, sem nenhum tipo de informação para o exterior, exceto o vencedor. No mundo de hoje com alta tecnologia, isto é muito difícil. As regras declaram explicitamente que “a capela deve ser protegida contra dispositivos de gravação e transmissão, com a ajuda de pessoas confiáveis com capacidade técnica comprovada.” Isso foi muito mais fácil em 2005 que vai ser em 2013.

Quais são as lições deste processo?

Primeiro, sistemas abertos conduzidos dentro de um grupo conhecido tornam a fraude eleitoral muito mais difícil. Cada passo do processo eleitoral é observado por todos, e todos se conhecem, isto torna muito difícil que alguém consiga encobrir alguma coisa.

Segundo, as eleições pequenas e restritas são mais fáceis de proteger. Este tipo de processo funciona para eleger um Papa ou um presidente de clube, mas fica rapidamente difícil numa eleição de grande escala. A única maneira de sistemas manuais funcionarem num grupo maior seria através de um mecanismo de pirâmide, com pequenos grupos reportando seus resultados obtidos manualmente para cima até chegar às autoridades centrais de tabulação.

E terceiro: Quando um processo de eleição é deixado para amadurecer ao longo de um par de milhares de anos, você consegue algo surpreendentemente bom.

Faça em casa sua Tomografia Computadorizada

A tomografia computadorizada foi uma das grandes revoluções da medicina no século XX. Tanto é assim que deu o prêmio nobel de Medicina ao engenheiro Godfrey Hounsfield em 1979 sendo que as primeiras tomografias para uso médico são de 1971.

Eu sei que no Brasil você não vai poder fazer sua toografia em casa porque não vai achar as peças, mas veja o que este rapaz fez em sua garagem e babe de inveja.

Feliz Natal – Lembrança de um leitor

Um leitor, Carlos, lembrou bem que não fizemos um post de Feliz Natal. Ele pergunta se virou politicamente incorreto desejar Feliz Natal.

Carlos, infelizmente em muitos lugares, principalmente aqui no Brasil se tem vergonha em ambientes não familiares de desejar um Feliz Natal e de se decorar os lugares com símbolos natalinos.

O motivo de fundo é que ser cristão e portanto lembrar que o Natal é o nascimento de Jesus Cristo, o Salvador, é “out” numa sociedade em que o pior crime que há é ser católico, homem, não gay e ter a pele branca. Dura veritas, sed veritas

Mas chega de mostrar coisas tristes.

Feliz Natal, Quadro B.E. Murillo

Desejamos a todos nossos leitores um Feliz Natal.

P.S. – Quem quiser, amanhã às 9:00 horário de Brasília assistir à benção Urbi et Orbi pode usar o novo Vatican Player: http://www.vatican.va/video/index.html

Números Lychrel e reminiscências do ensino fundamental

Era um sábado de calor no Rio de Janeiro no ano de 1987. Estávamos na sexta série do Colégio São Bento e a prof. Sandra Carelli percebendo que naquele dia não iríamos conseguir desvendar os mistérios da matemática de Papy, era o que se ensinava lá, mostrou-nos uma curiosidade matemática que nunca esqueci.

Suponha que você tem um número, por exemplo 124. Se você inverter os dígitos do número e somar com o número original é grande a possibilidade de obter um número palíndromo.

124 + 421 = 565

No entanto para alguns números a operação precisa ser repetida algumas vezes para obter um palíndromo: 279 por exemplo:

279 + 972 = 1251; 1251 + 1521 = 2772

Tendo captado nossa atenção ela prometeu um chocolate para quem achasse um número para o qual isto não funcionasse. Depois de muito tentar ela nos falou que um número para o qual isto não teria, a princípio, como se formar um palíndromo seria 196.

Quase 25 anos depois eu fui procurar sobre o assunto na Internet e descobri os chamados números de Lychrel. Os números de Lychrel seriam os que tem a mesma propriedade que 196. Embora nem mesmo 196 seja comprovadamente um número de Lychrel há outros candidatos como por exemplo: 295, 394, 493, 592, 689, 691, 788, 790, 879, 887, 978, 986

Abaixo, como homenagem a minha professora Sandra, vai um programa em Python para encontrar números de Lychrel.

#!/usr/bin/env python
def reverseNum(n):
        st = str(n)
        return int("".join([st[i] for i in xrange(len(st)-1,-1,-1)]))
 
def isPalindrome (n):
        st = str(n)
        rev = str(reverseNum(st))
        return st==rev
 
def isLychrel (n, num_interations):
        p = n
        for i in xrange(num_interations):
                if isPalindrome(p):
                        return i
                p = p + reverseNum(p)
        return -1
 
for i in xrange(1000):
        p = isLychrel(i,100)
        if (p < 0):
                print i,p

Para saber mais sobre os números de Lychrel e a busca por um palíndromo para 196 veja: http://www.p196.org

O massacre em Sandy Hook: algumas considerações

Ontem foi um dia triste nos EUA e isto repercutiu em todo o mundo. O massacre na escola em Connecticut trouxe tristeza e preocupação, mas também foi usado por oportunistas que, vampiros do sangue alheio, aproveitam uma situação trágica para vender suas idéias, no caso o desarmamento.

A constituição americana, em sua segunda emenda garante que os cidadãos tem o direito de ter armas. Sendo a primeira emenda a liberdade de expressão e de religião, ler algo logo em seguida como o que vai abaixo:

A well regulated militia being necessary to the security of a free state, the right of the people to keep and bear arms shall not be infringed

Nos mostra que é um direito que está nos fundamentos da sociedade americana. Você poderá dizer: que sociedade retrógada! E pode estar seguro que estará falando uma bobagem.

Sem contar a de San Marino, a constituição dos EUA é a mais antiga em vigor. Além das 10 emendas iniciais (1789) sofreu apenas mais 17 emendas desde que foi promulgada em 1788. Só em termos de comparação, o Brasil teve sete constituições sendo que a atual tem 250 artigos e já foi emendada 70 vezes. Portanto, pode-se inferir que a fidelidade aos fundamento do sonho americano:  direito à vida, à liberdade e à busca da felicidade estão bastante arraigados e não serão mudados por mais que a imprensa tupiniquim insista em dar pitacos sobre como eles deveriam viver.

Não digo que a sociedade americana seja perfeita, admiro a sociedade americana, mas ela tem muitos defeitos como em todos os lugares. O direito de ter armas não é um dos defeitos dela.

Você poderá dizer: se não houvesse armas não teria acontecido o massacre de ontem. Será? Ou então, se não houvesse armas liberadas haveria menos mortes. Não é bem assim que a coisa funciona; vamos ver?

Na Venezuela do ditador Chavez há 45 homicídios para cada 100.000 habitantes. No Brasil há 21 / 100k. Nos EUA há apenas 4.2 / 100k. No Brasil onde comprar uma arma legalmente é mais difícil que conseguir um doutorado houve em 2011 o maior número de homicídios no planeta: 40974!

Mas eu me desviei do tema. Queria fazer uma consideração sobre uma medida simples mas eficaz para reduzir massacres como este.

Muitos, senão todos, os indivíduos que fizeram massacres como este são psicopatas e/ou com um distúrbio narcisista de personalidade. Para eles, o grande ganho da matança é a publicidade que terão após a sua morte durante o massacre. Se cortarmos a divulgação de seus feitos, eles perdem um dos seus importantes motivos.

Então devemos proibir a imprensa de reportar estes eventos? Não! De forma alguma. Sou defensor da total liberdade de imprensa. No entanto, nada impede que cada veículo de comunicação pense numa política interna de dar a notícia sem destacar o assassino. Deixar ele no ostracismo, nem mencionar seu nome pode ser uma forma de evitar que outras pessoas perturbadas como ele busquem inspiração para fazer atos similares.

O massacre em Sandy Hook nos deve levar a pensar na formação dos adolescentes, em rezar pelas famílias afetadas, não em fazer proselitismo barato pregando o controle de armas sobre o cadáver de 20 crianças.

Foto Washington Post - Massacre Sandy Hook

P.S.: Aos leitores do blog: tenham claro que esta é minha opinião. Se você pensa diferente a área de comentários está aberta para você expor suas idéias e colocar argumentos favoráveis ou não à minha opinião.

Palavra do dia, Geocoding

Imagine que você tem um banco de dados grande de pontos de interesse (padarias, lojas, restaurantes, escolas, monumentos, museus, etc.) com as posições geográficas (latitude e longitude) de cada um e deseja saber qual deles está mais próximo de um certo endereço.

Sabendo a latitude e longitude do endereço, descobrir a distância em “linha reta”, na verdade é um arco, entre cada ponto é uma conta bem simples.

Distância entre duas coordenadas geográficas

Onde  e são respectivamente as latitudes dos dois pontos, é a diferença das longitudes e S é o arco que queremos descobrir. Para saber a distância em km, é preciso multiplicar o valor de S pelo raio da Terra, que, na média é igual a 6367,5km.

Por exemplo, suponhamos que quiséssemos saber a distância entre a Torre Eiffel (48.8582780, 2.2942540) e o museu do Louvre (48.86063610, 2.33760960) em Paris.

= 48.8582780˚ = 0.852737818rad
= 48.86063610˚ = 0.852778975rad
= (2.33760960 – 2.2942540) = 0.0433556˚ = 0.000756697969rad

cos(S) = sin(0.852778975) * sin(0.852737818) + cos(0.852778975) * cos(0.852737818) * cos(0.000756697969) = 0.99999987523

Srad = acos(0.99999987523) = 0.000499539793

Skm = 0.000499539793 * 6367.5 = 3.18km

Antes que me xinguem, esta conta não é muito precisa, visto que o raio da Terra não é constante e a Terra não é uma esfera, mas é uma boa aproximação e serve para podermos comparar distâncias.

Então o problema está resolvido, diria um leitor mais afoito. Infelizmente, não. A pergunta é: “Como eu sei que a posição da Torre Eiffel é (48.8582780, 2.2942540)?”

Para isso, precisamos saber como descobrimos a latitude e longitude de um certo endereço (Ex.: Av. Nações Unidas, 12.901, São Paulo, SP) ou local (Tour Eiffel) para podermos resolver o problema. A ação de converter um endereço em latitude e longitude é chamada de “Geocoding”

Algum esperto poderia dizer de gozação: “Ah, procura no Google!” e eu responderia que ele estava certo. O Google disponibiliza gratuitamente um serviço de Geocoding que resolve esse problema, mas tem algumas limitações. A maior delas é o limite de 2.500 buscas por dia, e também a restrição de ter que exibir o resultado da busca num mapa. O endereço de busca é o seguinte:

http://maps.googleapis.com/maps/api/geocode/json?address=[Endereço]&sensor=false

Existem outras soluções gratuitas, como o Bing Maps, o Mapbox e o OpenStreetMaps, dentre outras.

Este último é o único que realmente é gratuito e sem limites, se você quiser hospedar os dados num servidor próprio. O problema é que os dados e o sistema de Geocoding do OpenStreetMaps, chamado de Nominatim, do planeta inteiro ocupam aproximadamente 600GB de HD e sugerem um servidor com 32GB de RAM para rodar bem. Caso contrário, eles sugerem usar um serviço hospedado em sites de terceiros.

Eu encontrei no site da Mapquest, um serviço gratuito de Geocoding, baseado no Nominatim, que parece não ter as limitações do Google.

O endereço é http://open.mapquestapi.com/nominatim/#search_basic

Ainda não sei qual serviço vou usar no projeto que estou terminando, mas estou tendendo a usar este último.

E você? Já fez algum projeto usando Geocoding? Tem alguma dica para passar? Deixe seu recado nos comentários!

Quebrando o pau, matematicamente

Quando estudei na PUC-Rio havia uma matéria chamada Modelos Probabilisticos ministrada pelo pessoal da Telecom, que era conhecida por suas provas criativas.

Numa destas provas havia uma questão cujo enunciado é o que vai abaixo e serve como nossa leitura de final de semanamatem:

“Suponha que você quebre um palito num ponto aleatório do comprimento dele, escolha o maior pedaço e quebre novamente de forma aleatória. Qual é a probabilidade de você formar um triângulo com os três pedaços?”

Antes de sair procurando alopradamente no Google, não havia o Google ainda em 1996 quando fazia esta matéria, note que este problema é ligeiramente distinto do “three stick triangle problem”, neste nosso você escolhe para a segunda quebra o maior pedaço o que é diferente de quebrar um pedaço de pau em 3 pedaços diretamente.

Há duas formas de resolver este problema, uma forma computacional, que não era o caso na época, e uma forma analítica. A forma analítica é interessante porém exige um conhecimento matemático mais aprofundado. Já a forma computacional está disponível para qualquer um que saiba programar como mostramos no script Python abaixo.

from random import random
 
def isTriangle (a,b,c):
        lista = [a,b,c]
        lista.sort()
        if (lista[2] < (lista[1]+lista[0])):
                return True
        else:
                return False
 
def breakRule():
        p = random()
        if (p < 0.5):
                a = p
                p1 = random()
                b = (1-p) * p1
                c = (1-p) - b
        else:
                a = (1.0 - p)
                p1 = random()
                b = p * p1
                c = p - b
        return isTriangle (a,b,c)
 
sim = 0
nao = 0
 
for i in xrange(100000):
        if breakRule():
                sim += 1
        else:
                nao += 1
 
print "Número de vezes que deu certo: %d"%sim
print "Número de vezes que deu errado: %d"%nao
print "Probabilidade: %f"%(float(sim))/(sim+nao)

Agora a forma analítica de resolver.

Considerando a régua como tendo comprimento 1, vamos dividir o problema em duas partes que são simétricas. Na primeira parte a quebra ocorreu no ponto n (0 < n < 0.5) até 50% do comprimento da régua. Desta forma a segunda quebra não pode ocorrer, para respeitar a desiguldade triangular:

 

A < B + C

onde A é o comprimento do maior pedaço, nos trechos:

[n;\frac{1}{2}] ; [1 - (\frac{1}{2} - n);1]

Como pode-se ver na figura abaixo:

Desta forma, ao quebrar uma vez a régua no ponto n < 0.5 a probabilidade de formar um triângulo é dada por:

P_t(n) = \frac{n}{1-n}

Portanto a probabilidade de formar um triângulo é:

\int\limits_0^\frac{1}{2} P_t(n)dn = \int\limits_0^\frac{1}{2} \frac{n}{1-n}dn

Resolvendo a integral temos:

\log{2} - \frac{1}{2} = 0.193147

Como falamos que eram dois problemas simétricos a probabilidade de formar um triângulo é:

2 (\log{2} - \frac{1}{2}) = 0.386294

Que é o valor obtido pela nossa simulação.

Sete Leituras para o Domingo – (IX)

1) Do New York Times uma análise de que: talvez ser cauteloso ao entrar no mercado Mobile seja uma excelente política. Um artigo que deve ser lido.


Daniel Rosenbaum for The New York Times

 

2) O que aconteceria se um meteorito de 30 metros de diâmetro viajando a velocidade da luz colidisse com a Terra? Veja esta resposta no What-If desta semana.

3) O Nokia Lumia 920 vem aí e segundo a Nokia ele é indestrutível. Aproveite para ver o vídeo da tortura do aparelho.

4) O poder do Windows Phone 8 continua sendo louvado pelo mundo afora.

5) Cinco teorias para a recente queda brusca nos preços das ações da Apple (AAPL). O que a eleição de Obama tem que ver com isso?

6) Não é relacionado à tecnologia mas alguma coisa sobre os quase onze anos de cana que o Zé Dirceu pegou não poderia faltar. Reinaldo Azevedo comenta o Ius Sperniandi do chamado chefe da quadrilha.

7) E por falar em cadeia o Wikihow tem um artigo com 11 dicas para passar o tempo na cadeia. Que tal imprimir e mandar para Zé Dirceu, Genoíno, Delúbio, etc.