PyPE solution to PE problem 44

Registered by Scott Armitage

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

Sprints

Whiteboard

    ProjectEuler.net problem 44
    ===========================

    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

(?)

Work Items

This blueprint contains Public information 
Everyone can see this information.

Subscribers

No subscribers.