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