Problem #29 concerns counting perfect powers. The question reads:
Project Euler Problem 29: Distinct powers
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?
My solution for this question falls into the category of “Brute Force”. However, it is still able to find the answer in the range from 2 to 10000 in under 10 seconds, so I believe it sufficiently efficient. I may decide to come back to this question eventually to search for a more efficient solution. Here is my solution:
Solution #1: Brute Force Approach
We simply iterate through the possible values of a. For each value of a that is not a perfect power, we automatically count all powers of that base a including its perfect powers within the range. For example, for a = 3, we count the powers with base 3, 9, 27, and 81 in one go. Then we use a sieve to store the fact that we’ve already checked 9, 27, and 81, and keep iterating through the values of a. Here is an implementation of this method in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #29
'''
import time
def projectEulerProblemTwentyNine(n):
checked = [False]*(n+1)
checked[0] = True
checked[1] = True
total = 0
for i in range(2,n+1):
if(not checked[i]):
p = 0
power = i
while(power<=n):
checked[power] = True
power*=i
p+=1
possible = [False]*(p*n+1)
for a in range(1,p+1):
for b in range(2,n+1):
possible[a*b] = True
for x in possible:
if x:
total+=1
return total
start = time.time()
print projectEulerProblemTwentyNine(100)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
9183
--- 0.000976085662842 seconds ---
for input of n=100
'''
As shown above, there are times where the brute force solution is plenty efficient for your purposes.
Thanks for reading!
The Inner Machinations of Walker 