// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (6 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 87 Solution

Project Euler 87 Solution

Project Euler 87: Investigating numbers that can be expressed as the sum of a prime square, cube, and fourth power


Project Euler 87 Problem Description

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 = 22 + 23 + 24
33 = 32 + 23 + 24
49 = 52 + 23 + 24
47 = 22 + 33 + 24

How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?

Analysis

This is a problem that brute force solves so quickly and easily that much more investigation is hardly warranted. It’s not obvious that any other approach would produce a much faster solution.

Basically, this routine generates a list of prime numbers and considers candidates for the square root, cube root and fourth root of the limit. Then we iterate over the lists and calculate unique numbers below 50,000,000 as p22 + p33 + p44, where p2, p3,and p4 are prime numbers. The length of the set is the how many discrete sets fit the criteria.

Project Euler 87 Solution

Runs < 0.360 seconds in Python 2.7.
from Euler import prime_sieve as sieve
from itertools import product
P = set()
for a,b,c in product(sieve(7072), sieve(369), sieve(85)):
	q = a*a + b**3 + c**4
	if q >= 50000000: break
	P.add(q)
print len(P)
download arrowUse this link to get the Project Euler 87 Solution Python 2.7 source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|1097343|

Afterthoughts

  • Runs for 1,409,343 iterations.
Project Euler 87 Solution last updated

Discussion

2 Responses to “Project Euler 87 Solution”

  1. from Euler import prime_sieve as sieve

    How to get above line work. No module found for me.

    Posted by Zakir Hossain | October 7, 2016, 11:28 PM

Post a comment