PyPE solution to PE problem 37

Registered by Scott Armitage

PyPE solution to PE problem 37

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 37
    ===========================

    The number 3797 has an interesting property. Being prime itself, it is
    possible to continuously remove digits from left to right, and remain
    prime at each stage: 3797, 797, 97, and 7. Similarly we can work from
    right to left: 3797, 379, 37, and 3.

    Find the sum of the only eleven primes that are both truncatable from
    left to right and right to left.

    NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

    Solution
    --------

    We use a basic recursive algorithm for checking truncatability of a number.
    First, we determine if the number has multiple digits; if not, it is by
    default truncatable (according to our function's definition, not according
    to the problem statement; we have to account for this outside the function
    for testing truncatability). Otherwise, we remove one digit from the
    specified edge of the number and test the subnumber for both primality and
    truncatability. If the subnumber has both attributes, then the original
    number is truncatable.

    An earlier version of this program using the dynamic PyPE.pemath.isprime(...)
    function was used to originally solve the problem, yielding the following 11
    truncatable primes:

        23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, and 739397.

    With this foreknowledge, we create an array of booleans storing the primality
    of all numbers up to and including 739397 (since that is the highest number
    we will have to check). This drastically increases the speed of the solution,
    however it is less versatile -- if the same code is to be used for slightly
    different problems, care must be taken to avoid indexing errors.

    Answer
    ------

    748317

(?)

Work Items

This blueprint contains Public information 
Everyone can see this information.

Subscribers

No subscribers.