# Yet another naive BigInteger solution

Published on 2011-07-31Problem 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:

2

^{2}=4, 2^{3}=8, 2^{4}=16, 2^{5}=32

3^{2}=9, 3^{3}=27, 3^{4}=81, 3^{5}=243

4^{2}=16, 4^{3}=64, 4^{4}=256, 4^{5}=1024

5^{2}=25, 5^{3}=125, 5^{4}=625, 5^{5}=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; } } }