PyPE solution to PE problem 44
PyPE solution to PE problem 44
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
===
Pentagonal numbers are generated by the formula, Pn=n(3n1)/2. The first ten
pentagonal numbers are:
1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference,
70 - 22 = 48, is not pentagonal.
Find the pair of pentagonal numbers, Pj and Pk, for which their sum and
difference is pentagonal and D = |Pk - Pj| is minimised; what is the value
of D?
Solution
--------
First, we assume that j != k, and since the order doesn't matter, we limit
our solution space to j > k. The start point is k=1, j=2, and we work our
way up from there. We note that at all times, the value for Pk will have
already been calculated once as a Pj, so we cache the values of Pj for re-
use.
Next, we check to see if both the sum and difference of Pj and Pk are
themselves pentagonal numbers. If so, we return the difference.
This assumes that there are very few sets that match these criteria, and
that as soon as we find an answer, it is the correct one. One slight point
to help in this assumption is that k is counted down from j-1 to 1, such
that for a given j, the first answer found will be a minimum difference.
Answer
------
5482660