Problem #63 concerns perfect powers and the number of digits in the perfect power. The question reads:
Project Euler Problem 63: Powerful digit counts
The 5-digit number, 16807=75, is also a fifth power. Similarly, the 9-digit number, 134217728=89, is a ninth power.
How many n-digit positive integers exist which are also an nth power?
My solution is heavily reliant on mathematics. Here is my solution:
Solution #1: Brute Force Approach
We know that any n-digit number must lie between 10^(n-1) and 10^n. Thus, if 9^n is not in this range, there will not be any nth powers with n digits. We can observe that because 10^(n-1) grows faster than 9^n, if 9^c < 10^(c-1) for some value of c, then 9^x < 10^(x-1) for x>c. Thus, it suffices to count the number of nth powers with this property for all powers of 10 less than 10^c. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #63
'''
import time
from math import ceil, floor
def projectEulerProblemSixtyThree(n):
total = 0
for c in range(1,n+1):
first = ceil(((10.)**(float(c)-1.))**(1./float(c)))
second = floor(((10.)**(float(c))-1.)**(1./float(c)))
first = int(first)
second = int(second)
for x in range(first,second+1):
if(len(str(x**c))==c):
total+=1
if(9**c < 10**(c-1)):
return total
return total
start = time.time()
print projectEulerProblemSixtyThree(1000)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
49
--- 9.89437103271e-05 seconds ---
for input of n = 1000.
'''
And with that, we’re done. The problems on Project Euler that involve pure mathematics such as inequalities and geometry tend to have very quick solutions, so it is no surprise that this one runs in under a millisecond.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 