PyPE solution to PE problem 87
PyPE solution to PE problem 87
Blueprint information
- Status:
- Complete
- Approver:
- None
- Priority:
- Undefined
- Drafter:
- None
- Direction:
- Needs approval
- Assignee:
- None
- Definition:
- Approved
- Series goal:
- None
- Implementation:
-
Implemented
- Milestone target:
- None
- Started by
- Scott Armitage
- Completed by
- Scott Armitage
Related branches
Related bugs
Sprints
Whiteboard
ProjectEule
===
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?
Solution
--------
This is more or less a brute-force attack, with some slight optimizations.
We note that the largest prime we will have to consider is less than the
sqrt(limit), so this drastically reduces the number of primes we need to
generate. Since we know we will be comparing squares, cubes, and tetrons
of these prime numbers, we also pre-compute arrays with these values, such
that we only have to do each computation once.
We then iterate over these values, starting with the tetrons since these
will break the limit first. At any time that our running total of x + y + z,
where x = _**2, y = _**3, and z = _**4, breaks the limit, we move on to the
next z or y.
At the bottom level of these iterations, if we haven't broken out, then we
have reached a number that can be formed as the sum requested, so we yield
the value.
The calling program collects these values into a set to eliminate any
duplicate entries and then returns the length of that set.
Answer
------
1097343