Problema 18 - Caminho com soma máxima I

Eis aí um problema interessantíssimo. Leia a descrição. É melhor. :o)

Meu método não foi usar força-bruta. Utilizei, ao contrário, uma abordagem de ir gerando a solução para o menor triângulo (começando da extremidade superior) e, então, ir aumentando até atingir o triângulo completo. Primeiro, salvar o triângulo num arquivo de texto. Depois, agi da seguinte maneira a cada linha do triângulo (tente visualizar olhando para o mesmo):

• Os elementos extremos da esquerda e da direita recebem, respectivamente, o seu próprio valor somado ao extremo correspondente da linha anterior.
• Os outros elementos, os que não são extremos, recebem o seu próprio valor somado ao maior elemento da linha anterior imetidamente à sua esquerda ou direita.
• No final, na última linha, o maior elemento desta será a resposta pedida na descrição do problema.

Engenhoso e eficiente. Tanto que também resolvi o Problema 67 com exatamente o mesmo método, sem tirar nem pôr, em pouco mais que um piscar de olhos. Se fosse usar força bruta, o Problema 67 levaria mais que uma eternidade.

Problema 17 - Contagem do número de letras

Este problema pede para contar quantas letras usamos se formos escrever todos os números inteiros de 1 a 1000 por extenso, em inglês (britânico). Pede para ignorarmos espaços e hífens (42 é "forty-two") mas para considerarmos "and" (142 é "one hundred and forty-two").

Achei este problema, pessoalmente, um tanto sem graça, embora haja necessidade de certo raciocínio lógico. Gerei manualmente, em vetores, os nomes dos números de 1 a 19 e as dezenas de 20 a 90, daí fui gerando os nomes dos números de 1 a 1000 por concatenação adequada de strings. Ao final, apaguei todos os espaços (os hífens eu nem me preocupei em gerar...) e contei caracteres.

Cabe a observação de que R é uma linguagem um tanto chata para se manipular strings, embora isso possa ser feito de maneira bem precisa (até demais para o meu gosto).

Problema 16 - Soma dos dígitos de uma potência

Este problema quer saber: qual é a soma dos dígitos de 2^1000? "Ora, calcule 2^1000, converta para string e some os dígitos". Em tese, isso resolve. E foi bem o que tentei fazer... até ver que o número está muito acima do limite de tamanho confiável do R para armazenar inteiros. Também poderia ir dividindo (divisão inteira) por 10 e somando os restos da divisão, mas aí eu recebia avisos de possíveis erros durante a operação e, no fim, o resultado estava errado.

Assim, resolvi aprender com as crianças e calcular 2^1000 "manualmente", como expliquei aqui:

Agora, sim! Somemos os dígitos do vetor e problema resolvido.

Aprendendo a somar e a multiplicar

Você certamente se lembra dos clássicos métodos aprendido no antigo Primário (atual Ensino Fundamental I) para se somar ou multiplicar dois números inteiros, certo? Pois eu resolvi implementá-los em R. Transformar o número em um vetor de dígitos, realizar a soma ou a multiplicação "manualmente", e retornar um vetor de dígitos.

"Ora, mas por quê?" Porque aparecerão problemas envolvendo números muito grandes, e o R possui limitação de tamanho para números inteiros. Um número inteiro pode ser armazenado de maneira exata até 2147483647, que é 2^31 - 1. Acima disso, ainda podemos trabalhar com os números, porém podem haver erros nos cálculos (o próprio R lança warnings quando for o caso - é comum, por exemplo, com divisões inteiras). Existem bibliotecas que lidam bem com números de tamanho arbitrário (o clássico GMP de décadas, Rmpfr, Brobdingnag, talvez existam outras), mas resolvi encarar o desafio à minha maneira. A seguir, respectivamente, soma e multiplicação:



No caso da soma, a idéia básica é completar o menor número (em número de dígitos) com zeros à esquerda e, então, somar termo-a-termo, não esquecendo de levar para o termo seguinte eventuais somas com resultado maior ou igual a 10. Considero o vetor reverso (ou seja, de trás pra frente) nos cálculos apenas para não ter que ficar "passeando" do último ao primeiro elemento, mas sim do primeiro ao último. Questão de gosto pessoal.

No caso da multiplicação, também faço como aprendemos quando éramos crianças primárias: multiplico o número de cima por cada algarismo do número de baixo, depois vou colocando zeros nos resultados, por fim somo tudo.

O próximo problema lançará mão dessas artimanhas...

Problema 15 - Caminhos num reticulado

Leia a descrição do problema.

É fácil perceber que, no caso de um reticulado n x n, qualquer caminho terá comprimento igual a 2n, com n movimentos para a direita e n movimentos para baixo. Como representar um caminho? Eu escolhi fazê-lo por meio de um vetor de comprimento 2n, com n elementos "D" e n elementos "B". Assim, no caso exemplificado na descrição (n = 2), os caminhos possíveis seriam:

• DDBB
• DBDB
• DBBD
• BDDB
• BDBD
• BBDD

Este é um problema combinatório de se contar anagramas. Para n arbitrário, a resposta é (2n)! / (n! * n!) - prove isso -, que é equivalente a produto(n+1, n+2, ..., 2n) / n!,  e eu resolvi em uma linha, em R, da seguinte maneira:

Note que é fácil a conta dar overflow para n grande, ou pelo menos perda de precisão, no caso do R. Existem meios de contornar isso, mas prefiro utilizá-los apenas quando necessário. Por ora, fiquemos com um pouco de simplicidade.

Problema 14 - Maior seqüência de Collatz

Dado n inteiro positivo, uma seqüência de Collatz para n é uma seqüência gerada da seguinte maneira:

• n <- n / 2, se n for par;
• n <- 3*n + 1, se n for ímpar.

Existe uma conjectura que supõe que todas as seqüências de Collatz terminam em 1.

O que o Problema 14 quer saber é: qual n abaixo de 1 milhão produz a seqüência de Collatz mais longa? Eu resolvi isso de duas maneiras.

Método 1

Este é o método mais direto. Para cada número entre 2 e 1.000.000, ir gerando o próximo elemento da seqüência de Collatz e ativar um contador. Vence quem tiver o maior contador ao final.

Usei o pacote "parallel" pela primeira vez aqui, para poder aplicar aqui a função de contagem em mais de um elemento/seqüência ao mesmo tempo através de computação paralela. Interessante notar, também, que basta testar n para n ímpar (por quê?), deixando o cálculo aproximadamente duas vezes mais rápido.

Método 2

Não usei computação paralela. Mas eu tomei vantagem de um corolário da conjectura citada na (minha) descrição do problema: se m pertence à seqüência gerada por n, então ambas seqüências serão iguais a partir de m. Em outras palavras, se estou gerando a seqüência de n, cheguei em m e já conheço o tamanho da seqüência de m, posso parar aí e verificar o próximo n.

O Método 1 levou, no meu caso, 5,85 minutos para ser executado, enquanto o Método 2 levou 35,19 segundinhos.

Problema 13 - Grande soma

Pede-se para calcular os 10 primeiros dígitos da soma de uma lista de 100 números com 50 algarismos cada.

Meu método: primeiro transformar num vetor de strings, depois extrair apenas os 11 primeiros dígitos de cada número (os dígitos além do 12º não farão diferença no resultado), então somar tudo e extrair os 10 primeiros dígitos do resultado convertido para string.

Quick and dirty.

PS: hoje é meu aniversário. Parabéns pra mim! :o)

Problema 12 - Número triangular altamente divisível

Este é um problema muito interessante, tanto pelo entendimento do problema quanto pela implementação de uma solução. Pede-se para calcular o primeiro número triangular a possuir mais de 500 divisores. "Ah, mas é só ir gerando os números triangulares, passar o script que calcula o número de divisores, testar para ver se este número passa de 500, e pronto!". Bem, em teoria está correto. Porém, dá para melhorar - e muito.

Se você pegar um papel e um lápis, verá rapidamente que os números triangulares são somas de uma PA de razão 1 começando em 1. E mais: verá também que são (a partir do segundo número) a metade da multiplicação de um número par por um número impar. Agora, se a e b são números primos entre si, então n_divisores(a*b) = n_divisores(a) * n_divisores(b). A prova é um exercício para o leitor. Pode-se ver, também, que os dois fatores que compõem um número triangular > 1 são primos entre si. Portanto, com isso em mente, podemos construir um algoritmo que calcula a quantidade de divisores de números bem menores que cada número triangular, e usar o resultado para o mesmo efeito.


Este problema do PE é um caso em que usar a força bruta é uma péssima idéia. :o) No meu computador, esta solução foi encontrada em 44,88 segundos, enquanto uma versão em força bruta do mesmo algoritmo (calculando diretamente o número de divisores de cada número triangular) levou 7,31 minutos...

Calculando a quantidade de divisores de um número

Do Teorema Fundamental da Aritmética, segue que, para calcularmos a quantidade de divisores (positivos) de um dado n, devemos somar 1 a cada expoente da representação por produto de números primos e, então, multiplicar essas quantidades.

Como suporte à solução de problemas futuros, fiz um script que pega esta idéia e calcula a quantidade de divisores de um número natural.

Problema 11 - Maior produto numa grade

É dada uma matriz 20 x 20. Deseja-se saber o maior produto envolvendo 4 elementos da matriz que sejam adjacentes em qualquer direção (vertical, horizontal, diagonal).

Eu salvei a matriz num arquivo de texto com os números separados por espaços. Com o comando read.csv pude ler facilmente e transformar o arquivo em uma matriz por linhas (um "data frame" do R, na verdade). Então, é só "passear" nas quatro direções, tomando cuidado com os índices e as dimensões da matriz.

Problema 10 - Soma de primos

Vamos encontrar a soma de todos os números primos abaixo de 2 milhões?

Bastou-me gerar o Crivo de Eratóstenes para n = 2 * 10^6 e somar tudo.

Problema 9 - Tripla pitagórica especial

Este PE pede, no fundo, para encontrar uma tripla pitagórica que, pela descrição do problema, já sabemos que é única. Seria, no caso, a única tripla de números naturais (a,b,c) tal que a < b < c, a^2 + b^2 = c^2 e a + b + c = 1000.

Vamos, então, iterar por a e b, calcular c em função da última condição pedida e ver se bate... É o jeito.

Problema 8 - Maior produto numa série

É-nos dado um número com 1000 dígitos. Pede-se para calcular o maior produto de 5 dígitos consecutivos deste número.

Bem, eu transformei em string e fui "passeando" por ela... Easy.

O Crivo de Eratóstenes revisitado

Um dos primeiros posts tratava da minha implementação do Crivo de Eratóstenes. Pois bem, eu melhorei minha implementação, porém resolvi deixar a anterior como registro.

Essencialmente, o que fiz de diferente? Calculei os primos até a raíz quadrada de n e os seus múltiplos. Isso, por si só, já exclui do corte os primos maiores que a raíz de n, e somente eles.

Para terem uma idéia do ganho: com o método anterior, levei 3,43 para gerar a lista dos números primos até 1 milhão, enquanto com o método novo (que estarei usando de agora em diante) levei meros 5,85 segundinhos...

That's all, folks!

Problema 7 - 10.001º primo

Qual é o 10.001º número primo? É o que este problema quer saber.

Eu pensei no seguinte... É fácil, usando o Crivo de Eratóstenes, calcular todos os primos até n. Portanto, se eu conhecer um limite superior (um N grande) para o n-ésimo primo, basca aplicar o Crivo. Isso, porém, é impraticável num caso geral. Assim sendo, eu fiz uma função que calcula o n-ésimo primo começando por gerar um crivo até 2*n e, então, testando os ímpares a partir do último primo para ver se são primos, até achar.

Não conheço um método melhor, mas pelo menos este meu método funciona. Claro, tampouco quero apelar para algorítmos probabilísticos...

Problema 6 - Diferença da soma de quadrados

Este problema é tão simples de ser resolvido e de ser entendido que não irei nem discutí-lo. Fiquei com preguiça e resolvi, quick and dirty, em uma só linha vetorizando as operações.

Dica: é possível resolver o problema geral para n utilizando a diferença entre duas relações de recorrência. :) Mas, desta vez, vamos deixar o computador trabalhar por mim.

Problema 5 - O menor múltiplo

Objetivo: calcular o menor número natural que seja divisível por cada um dos números de 1 até 20.

Seja 20 o nosso "alvo". Queremos calcular o mínimo múltiplo comum (MMC) de todos os números de 1 até 20. Eu não fiz, ainda, um programa para calcular o MMC, mas raciocinei que o número que quero calcular é o produto de todos as potências dos primos até 20 que também não ultrapassem 20. Prova? Exercício para o leitor (dica: Teorema Fundamental da Aritmética). Mas fiquem com meu código.

Interessante é que, conforme cresce o "alvo", o resultado cresce assustadoramente.

Problema 4 - Maior produto palíndromo

Objetivo: tomar todos os números que são produtos de dois números de 3 digitos e calcular o maior destes produtos que é um número palíndromo.

Método: fazer exatamente isso.

Quick and dirty.

Números palíndromos

Um palíndromo é uma palavra, frase ou número que pode ser igualmente lido de frente pra trás ou de trás pra frente. Por exemplo, "arara", "Socorram-me! Subi no ônibus em Marrocos", 2645462.

Existem problemas do PE que lidam com números palíndromos. O script abaixo verifica se um dado número é palíndromo ou não.

A idéia é ir fazendo a divisão inteira por 10 para obter o "reverso" do número e, por fim, testar se o reverso é igual ao número original. Pode dar problemas para números grandes por causa das limitações do R, sei como contornar isso, mas só vou mexer nisso se eu precisar.

Problema 3 - Maior fator primo

Objetivo: calcular o maior divisor primo de 600851475143.

Método: calcular os fatores primos deste numerozão.

Tendo em mãos a minha função que já calcula os fatores primos de um dado número, fica fácil.

Decomposição em fatores primos

Este script calcula a decomposição de um número natural n em seus fatores primos. Ele retorna uma lista contendo dois elementos: um vetor com os números primos que dividem n, ordenados de modo crescente, e um vetor com os expoentes correspondentes aos fatores primos. Se n for primo, obviamente n será o único fator, com expoente igual a 1.

Dado n, no máximo um divisor (e com expoente igual a 1) será maior que a raíz quadrada de n. Isso segue do Teorema Fundamental da Aritmética. Deste modo, meu método consiste em utilizar o Crivo de Eratóstenes para gerar os números primos até raíz(n). Opcionalmente, posso passar ao script um crivo já calculado, desde que, é claro, o maior primo constante nesta lista seja maior ou igual a raíz(n). Isso torna o script bem mais rápido.

O Crivo de Eratóstenes

Sabemos que n é primo se, e somente se, ele tiver dois divisores naturais distintos: 1 e n. Logo, 1 não pode ser primo.

Um método bastante conhecido - e eficaz - de se gerar uma seqüência de números primos é o crivo de Eratóstenes, um dos algorítmos mais antigos conhecidos. Ele consiste em pegar uma tabela com os números de 2 até n, manter 2 e ir marcando (jogando fora) os múltiplos de 2, manter o próximo número (3, no caso) e ir marcando seus múltiplos, e assim repetir o processo até não haver mais número com múltiplo menor ou igual a n sobrando.

Segue minha implementação em R, que será extremamente útil em muitos problemas do PE. Creio que ela possa ser melhorada.

Algo que gosto muito no R é a elegância como posso extrair subconjuntos de um vetor. Por exemplo, na linha

nums <- nums[nums %% j != 0]

eu quero que o vetor nums receba os elementos dele próprio que sejam divisíveis por j. Bem melhor que programar a iteração por seus elementos, não? E o R faz isso de maneira bem eficiente.

ATUALIZAÇÃO: consegui melhorar minha implementação. Só ver aqui. :o)

Calculando Fibonacci

Inspirado no Problema 2, fiz um programinha para calcular o n-ésimo termo da seqüência de Fibonacci. Ele pode ser facilmente modificado para, por exemplo, gerar toda a seqüência até n. Poderá ser útil mais tarde. Enjoy it:

Problema 2 - Números de Fibonacci pares

Veja a descrição do problema 2.

Resumindo: encontrar a soma dos elementos pares da seqüência de Fibonacci que não excedam 4.000.000.

Novamente, quick and dirty. Apenas fui gerando os termos e testando se eram pares, até passar de 4.000.000.

Problema 1 - Múltiplos de 3 e 5

Veja a descrição do Problema 1.

Resumindo: calcular a soma dos múltiplos de 3 ou 5 abaixo de 1000. Mole. Pode ser feito rapidamente com lápis e papel usando progressões aritméticas. Mas eu decidi resolver de outra maneira. Primeiro, gerei seqüências com todos os múltiplos de 3 e de 5 e somei tudo, depois subtraí a soma dos múltiplos de 15 (que é 3 * 5), para corrigir dupla contagem.

Quick and dirty. Sem firulas.

Introdução

Olá, seja bem vindo. Pretendo, com este blog, divulgar as minhas resoluções de problemas do Project Euler (PE) feitas com o auxílio da linguagem de programação R.

Project Euler?

Ele é uma coleção de problemas matemáticos, com praticamente um problema novo aparecendo a cada semana. São, em geral, problemas de aritmética e combinatória, mas não se restringindo a essas áreas. Os problemas têm dificuldade aproximadamente crescente. A idéia é resolver os problemas usando alguma implementação computacional eficiente (rápida) o que, em muitos casos, desencoraja o uso de força bruta.

R?

Esta é uma linguagem de programação bastante usada em trabalhos de estatística e mineração de dados, embora seja bastante usada por profissionais e pesquisadores de outras áreas. É uma linguagem interpretada (portanto bastante lenta para instruções envolvendo loops), de aprendizado relativamente rápido, e possui um excelente ferramental gráfico. Há evidentes semelhanças com MATLAB/Octave, por ser bem eficiente (em facilidade e em desempenho) para manipular funções e objetos vetoriais. Possui orientação a objetos e um vastíssimo repositório de bibliotecas. Entretanto, pretendo dar preferências as minhas próprias soluções.

Mais um blog sobre isso?

Sim. Há muitos blogs por aí discutindo problemas do PE e suas soluções, mas eu gostaria de também deixar o meu ponto de vista. Afinal, costuma-se haver diversas maneiras diferentes de se atacar problemas do PE. Também há muitos blogs por aí tratando da linguagem R. Comecei a usar R profissionalmente, admito que não sou um bom programador, e pretendo usar o PE e este blog como desculpa para:

1. Estudar implementação eficiente de algoritmos;
2. Estudar a própria linguagem R, significando que, às vezes, não vou dar uma solução eficiente de propósito por querer explorar algum outro aspecto da linguagem que seja de interesse;
3. Exercitar o cérebro lembrando-me de coisas que estudei na faculdade (sou bacharel em Matemática);
4. Motivar discussões, compartilhar conhecimento e aprender com comentários;
5. Exercitar um pouco de didática;  :o)
6. (Tentar) esclarecer minhas dúvidas;  :-D
7. E tudo isso em língua portuguesa! However, variable names and comments inside my code may be in English, so don't be surprised.

Todos os códigos que eu utilizar estarão disponívels em meu GitHub, o qual ainda não sei usar direito. Minhas velocidades de escrita, resolução dos problemas e atualização do GitHub não serão necessariamente as mesmas, advirto. ;-)

Estão preparados? Se bem que a pergunta correta é: estou preparado?