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)

Desenvolvendo para IPhone sem Objective-C (Parte 3/3)

Terminamos hoje nosso tutorial de desenvolvimento para IPhone sem usar Objective-C. Não vou mais pedir que você compre a App de US$ 0,99. Já me convenci de que você não fa-lo-á (curtiu a mesóclise?).

Hoje vamos ver o processo com a loja da Apple e antes de começar tenho que dar uma má notícia. Para se inscrever no Programa da Apple você precisa pagar 99 Obamas. Se você vai fazer apps boas vale a pena porque isto se paga rapidamente. Para se inscrever no programa você deve entrar em http://developer.apple.com/membercenter/ e completar o cadastro. No momento de escolher como quer se inscrever no IPhone Developer Program há duas opções Pessoa Física ou Empresa, como Pessoa Física a liberação é imediata, como empresa há bastante burocracia (agradeça ao governo Lulla) e pode demorar até 10 dias.

Continuar lendo Desenvolvendo para IPhone sem Objective-C (Parte 3/3)

Desenvolvendo para IPhone sem Objective-C (Parte 2/3)

Ok, eu já percebi que você não comprou meu app na loja da Apple, mas tudo bem, você sabe que não escrevo isto por dinheiro e que “você não precisa me ajudar a lhe ajudar”. Feita esta lamentação, voltemos ao frango. Quer dizer ao software.

Espero que ontem durante a noite você tenha feito já sua web app para o IPhone e esteja craque no uso da biblioteca jQTouch. Como não houve perguntas nos comentários, ou ninguém leu, ou não há duvidas. Vamos em frente.

Hoje veremos como transformar uma web app num aplicativo que possa ser vendido na loja da Apple. Há algumas bibliotecas que prometem fazer isto, algumas delas não respeitam as condições da loja da Apple e fazem as aplicações serem rejeitadas e outras custam muito caro. A biblioteca Phonegap tem a vantagem de ser aceita pela Apple e de ser 0800, ou seja, não vamos perder tempo falando de outras. Phonegap na cabeça!

A Phonegap, além de permitir compilar web apps em aplicativos nativos, tem uma outra vantagem bacana: permite que você use o mesmo código para criar apps para Android, Blackberry, Symbian e Windows Mobile. Tudo bem que a parte do IPhone é a mais desenvolvida, mas é um trabalho de portabilidade muito promissor.

Também a phonegap dá acesso aos componentes do sistema operacional como a agenda de telefones, o gps, o acelerômetro, o magnetômetro, etc.

Agora a má notícia. Você precisará de um Mac, não porque a Phonegap exija, mas porque, para compilar apps para o IPhone, só usando Mac. Puxa vida, dirá você, macacos me mordam, um Mac custa muito caro e agora, quem poderá me defender? Eu não vou recomendar para você que monte um Hackintosh, viu? Não monte um Hackintosh, nem procure no Google sobre isto. Compre um Mac. Mais uma coisa: não procure no Google sobre Hackintosh nem OSX86, que pirataria é coisa feia.

Eu uso um Mac Mini com o Leopard 10.5.8 e dá conta do recado, o SDK do IPhone você pode baixar, juntamente com o compilador, em http://developer.apple.com O download é bem grandinho, coisa de 3.4GB, portanto, deixe baixando à noite…

Para criar seu ambiente de desenvolvimento IPhone você vai precisar apenas da ferramenta GIT que pode ser instalada do seguinte endereço: http://git-scm.com/

A seguir, execute a seguinte sequência de comandos no terminal do Mac OS, num diretório que você irá usar para desenvolvimento:

git clone git://github.com/phonegap/phonegap-iphone.git
cd phonegap-iphone
git submodule init
git submodule update
make

Pronto, agora você deve ter neste diretório um arquivo: PhoneGapLibInstaller.pkg

Com o XCode fechado, execute o PhoneGapLibInstaller.pkg e instale-o.

Abra o XCode e, ao criar um projeto novo, você verá na parte de User Templates a opção: Phonegap.
Selecione esta opção e voilà! Criado seu projeto.

Agora, basta mover a Web App que você criou para o diretório www do projeto que está aberto em sua tela. E compilar para o simulador de IPhone e começar a brincar.

Algumas funcionalidades interessantes do Phonegap (uso de câmera, acelerômetro, gps, etc) você encontra em: http://docs.phonegap.com/

Um guia introdutório do Phonegap para caso tenha alguma dúvida pode ser visto em: http://phonegap.pbworks.com/Getting-Started

Caso você tenha outras dúvidas deixe um comentário neste post. Aliás, você já passou do nível anta na App que você comprou?

Parte 1: http://www.zeletron.com.br/2010/04/desenvolvendo-para-iphone-sem-objective-c-parte-13.html

App de Demo : http://itunes.apple.com/app/zeroes/id368251065?mt=8

Desenvolvendo para IPhone sem Objective-C (Parte 1/3)

Aplicação usada como exemplo:
http://itunes.apple.com/app/zeroes/id368251065?mt=8

Havia prometido o tutorial e finalmente chegou o dia. Vamos ver se conseguimos fazer as 3 partes em 3 dias consecutivos. Talvez, você que esperou tanto tempo esteja se perguntando porque ele demorou tanto para fazer o tutorial? Demorei porque esperei o programa que vou usar como modelo ficar aprovado na loja da Apple, o tempo de revisão é de 5 a 7 dias e hoje pela manhã ele foi publicado. Este programa que vou usar como modelo chamado Zeroes é um jogo de raciocínio que custa US$ 0.99 (você gostará tanto do tutorial que vai comprar ele, não vai?)


O caminho convencional de desenvolvimento para o IPhone é usando o compilador XCode com a linguagem Objective-C (que de C aliás tem muito pouco), este caminho não é acessível a todos os desenvolvedores e tem uma curva de aprendizado bastante lenta. O outro caminho, aprovado pela Apple, é o do desenvolvimento Web com Javascript + HTML5 + CSS3. No entanto o desenvolvimento Web não permite que o aplicativo seja vendido na loja da Apple a menos que você compile ele em um executável e este é o objetivo do tutorial.

Continuar lendo Desenvolvendo para IPhone sem Objective-C (Parte 1/3)

Google compra Picnik

Não é o que você está pensando.

O Google adquiriu hoje a empresa de edição de fotos on-line chamada Picnik. Com uma aplicação de design caprichado e uma boa funcionalidade a Picnik oferece várias funcionalidades que você teria em programas comerciais ou Gimp’s da vida totalmente on-line. A Picnik oferece integração com praticamente todas as redes sociais de compartilhamentos de fotos, tanto para leitura como para escrita.

Autocorreção, cortar, redimensionar, consertar a exposição, filtros de nitidez e remoção de olhos vermelhos são algumas das funcionalidades que o Picnik oferece.

Além da versão gratuita, a Picnik oferece a versão premium que possui retoques muito mais sofisticados. Não saberia dizer se a versão premium continua após a venda para o Google.

No entanto a pergunta que fica é: porque o Google comprou a Picnik? Além de um belo código Javascript o que ela tem a oferecer?