Resolvendo o prolema 29 do Project Euler

Continuando a série de resoluções dos problemas do Project Euler, e considerando aqueles que foram resolvidos por poucas pessoas, escolhi o problema 29 para apresentar a sua solução.

Mas vamos ao enunciado do problema:

Considere todas as combinações de inteiros de ab para 2 <= a <= 5 and <= b <= 5:

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125

Se os números fossem dispostos em ordem numérica, removendo todas as repetições, temos a seguinte sequência de 15 elementos distintos:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

Quantos termos distintos existem na sequência gerada por <= a <= 100 e <= b <= 100?

A solução para este problema pode ser facilmente encontrada se usarmos uma linguagem que nos fornceça uma abstração para trabalharmos números grandes (com ~ 200 dígitos) e conjuntos sem repetição (em muitas linguagens chamados de set). Com essas premissas, decidi resolver o problema utilizando Scala.

O código que resolve o problema, apresentado abaixo, é bem simples,  principalmente pelas abstrações oferecidas pelas classes BigInt e Set.

Bom, é isso, simples e rápido. O tempo total de execução é algo em torno de 8 segundos e a resposta final é 9183.

Em breve mais soluções! 🙂