Loading...
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.
Use this link to get the Project Euler 87 Solution Python 2.7 source.
Afterthoughts
- Runs for 1,409,343 iterations.
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 PMhttps://blog.dreamshire.com/common-functions-routines-project-euler/#prime_sieve
You can find all the useful functions we use on this page.
Posted by Mike Molony | October 9, 2016, 12:34 AM