PyPE solution to PE problem 37
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
Related bugs
Sprints
Whiteboard
ProjectEule
===
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.
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