PyPE solution to PE problem 87

Registered by Scott Armitage

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

Sprints

Whiteboard

    ProjectEuler.net problem 87
    ===========================

    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

(?)

Work Items

This blueprint contains Public information 
Everyone can see this information.

Subscribers

No subscribers.