I spent some time playing around with a way to reduce calculations by constructing something akin to a sieve, (2^16 is the same as 4^8 and 16^4), but it turns out that the brute force solutions runs in under a second on my machine so it seemed silly to spend any more time with it.

Ruby even minds the big numbers for me, so the solution is quite trivial:

Problem #29

How many distinct terms are in the sequence generated by a^(b) for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

MIN, MAX = 2,100
values = []

(MIN..MAX).each do |base|
  (MIN..MAX).each do |power|
    values << base**power
  end
end

puts values.uniq.length