Problema 21 - Números amigáveis

Um probleminha muito interessante! Seja d(n) a soma dos divisores próprios de um natural n. Se existirem dois números a e b tais que d(a) = b e d(b) = a, então a e b são chamados de números amigáveis. Pede-se, então, para calcular a soma de todos os números amigáveis abaixo de 10000.

O xis da quetão é, apenas, calcular a soma dos divisores de um dado número.

• O primeiro método a ser naturalmente pensado é: dado n, ir testando de 2 até raíz(n) se o candidato é divisor e, caso positivo, somar divisor e (por simetria) o resultado da divisão. Para acelerar, caso o número seja ímpar, testo a partir de 3 indo de 2 em 2. Lembrando, aí, que 1 é sempre divisor próprio e que n obviamente não o é.
• O segundo método foi usar a função divisor (ou função sigma), que como corolário provê a soma dos divisores através da decomposição de n em fatores primos. Aparentemente, um método mais inteligente... Mas, agora, vamos à realidade.

Ao invés de apenas rodar para n = 10.000 (e ter a resposta para o problema proposto), também rodei para n = 100.000 e para n = 1.000.000, a fim de comparar os dois métodos.

Código 1:

Código 2:

Desempenhos (respectivamente, método 1 e método 2), para comparação:

• n = 10.000: 1,28seg contra 9,40seg - tempo 7,3x maior
• n = 100.000: 24,30seg contra 1,77min - tempo 4,4x maior
• n = 1.000.000: 10,93min contra 18,83min - tempo 1,7x maior

Conclusão: o método mais simples, neste caso, ao contrário da (minha humilde) expectativa, é mais rápido que o método mais "elegante", embora essa diferença caia conforme aumentemos o tamanho do problema. Possivelmente, em algum momento o segundo método passe a levar vantagem. Até o momento, não resolvi pagar pra ver...

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