Yet another naive BigInteger solution
Published on Sunday, July 31, 2011Problem 29 looks like it should take forever to solve by brute force. It reads:
Consider all integer combinations of _a_ _b_ for 2 ≤ a ≤ 5 and 2 ≤ 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
If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
How many distinct terms are in the sequence generated by _a_ _b_ for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?
Nevertheless, I wanted to see the answer in order to determine the gap between the number of terms in the desired sequence and the number of distinct terms. But when I compiled my totally naïve, BigInteger-powered program, in ran in a couple seconds. Hence the seasoned programmer's caution against premature optimization: if your naïve solution is already fast enough for your purposes, just forget about squeezing more speed out of it.
using System;
using System.Numerics;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Problem029
{
class Program
{
static void Main(string[] args)
{
List<BigInteger> asToTheBs = new List<BigInteger>();
for (int i = 2; i <= 100; i++)
{
for (int j = 2; j <= 100; j++)
{
BigInteger aToTheB = BigIntegerPow(i, j);
if (!asToTheBs.Contains(aToTheB))
asToTheBs.Add(aToTheB);
}
}
Console.WriteLine(asToTheBs.Count());
}
private static BigInteger BigIntegerPow(int i, int j)
{
BigInteger exponentBase = new BigInteger(i);
for (int k = 1; k < j; k++)
exponentBase *= i;
return exponentBase;
}
}
}