Home › Blogs › garrett's blog ›

Project Euler Problem 29

garrett // Sep 10, 2009
//

Tonight's fun is Project Euler Problem 29. This turned out to be a lot easier than I thought. I wrote a quick scratch solution to test for correctness, and it turns out that the throw-away solution runs in < 1sec. What was this one?

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?

  1. #!/usr/bin/perl -w
  2. my $b      = 100;
  3. my $hash   = {};
  4. my $answer = 0;
  5.  
  6. for ( my $i = 2; $i <= $b; $i++ ) {
  7.   for ( my $j = 2; $j <= $b; $j++ ) {
  8.     my $prod = $i ** $j;
  9.     $hash->{"$prod"} = 1;
  10.   }
  11. }
  12.  
  13. printf("%d\n", scalar(keys(%$hash)));