Problem #87 concerns numbers which can be written as the sum of a perfect square, a perfect cube, and a perfect fourth power of prime numbers. The question reads:
Project Euler Problem 87: Prime power triples
The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is 28. In fact, there are exactly four numbers below fifty that can be expressed in such a way:
28 = 2^2 + 2^3 + 2^4
33 = 3^2 + 2^3 + 2^4
49 = 5^2 + 2^3 + 2^4
47 = 2^2 + 3^3 + 2^5
How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?
My solution to this is probably vastly inefficient. Here is my solution:
Solution #1: Brute Force Sieve Approach
First we use the Sieve of Eratosthenes to list all primes up to the square root of 50,000,000. Then we make lists of all the perfect squares, perfect cubes, and perfect fourth powers of those primes which are less than 50,000,000. Finally, we make a list with boolean values representing whether each number from 0 to 50,000,000 can be represented and update the list for every triple of a prime square, a prime cube, and a prime fourth power. Finally, we iterate through the list to count the numbers which can be represented. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Sieve Approach to Project Euler Problem #87
'''
import time
from math import sqrt
def sieveEratosthenes(n):
myPrimes = []
primePossible = [True]*(n+1)
primePossible[0] = False
primePossible[1] = False
for (i,possible) in enumerate(primePossible):
if possible:
for x in range(i*i, (n+1), i):
primePossible[x] = False
myPrimes.append(i)
return myPrimes
def projectEulerProblemEightySeven(n):
primes = sieveEratosthenes(int(sqrt(n)))
squares = []
cubes = []
fourths = []
cubeDone = False
fourthDone = False
for p in primes:
squares.append(p*p)
if not cubeDone:
c = p*p*p
if(c>n):
cubeDone = True
else:
cubes.append(c)
if not fourthDone:
f = p*p*p*p
if(f>n):
fourthDone = True
else:
fourths.append(f)
found = [False]*(n+1)
for a in squares:
for b in cubes:
if (b+a)>n:
break
for c in fourths:
s = a+b+c
if s>n:
break
else:
found[s] = True
total = 0
for x in found:
if x:
total+=1
return total
start = time.time()
print projectEulerProblemEightySeven(50000000)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
1097343
--- 0.985231161118 seconds ---
for input of n = 50000000.
'''
And with that, we’re done. That took nearly a second to run. I believe there is probably a faster way to do this, but this was the most efficient method that I could think of. I may return to this problem eventually.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 