Passed
Push — master ( 6c9680...9c2115 )
by Bill
02:28
created

solutions.problem37   A

Complexity

Total Complexity 8

Size/Duplication

Total Lines 80
Duplicated Lines 0 %

Importance

Changes 0
Metric Value
eloc 23
dl 0
loc 80
rs 10
c 0
b 0
f 0
wmc 8

2 Functions

Rating   Name   Duplication   Size   Complexity  
A solve() 0 8 3
A is_truncatable_prime() 0 22 5
1
"""
2
Project Euler Problem 37: Truncatable Primes
3
============================================
4
5
.. module:: solutions.problem37
6
   :synopsis: My solution to problem #37.
7
8
The source code for this problem can be
9
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem37.py>`_.
10
11
Problem Statement
12
#################
13
14
The number :math:`3797` has an interesting property. Being prime itself, it is possible to continuously remove digits
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (117/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
15
from left to right, and remain prime at each stage: :math:`3797, 797, 97`, and :math:`7`. Similarly we can work from
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (116/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
16
right to left: :math:`3797, 379, 37`, and :math:`3`.
17
18
Find the sum of the only eleven primes that are both truncatable from left to right and right to left.
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (102/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
19
20
.. note:: :math:`2, 3, 5`, and :math:`7` are not considered to be truncatable primes.
21
22
Solution Discussion
23
###################
24
25
Enumerate the prime numbers in ascending order, testing each in term for the truncatable property. For each truncatable
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (119/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
26
prime, accumulate their sum until eleven have been accounted for.
27
28
.. note:: due to the implementation of :func:`lib.sequence.Primes`, an upper-bound must be provided. This meant trial
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (117/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
29
          and error was required to identify an appropriate bound before the code below was correct.
30
31
Solution Implementation
32
#######################
33
34
.. literalinclude:: ../../solutions/problem37.py
35
   :language: python
36
   :lines: 39-
37
"""
38
39
from typing import Set
40
41
from lib.digital import num_digits
42
from lib.sequence import Primes
43
44
45
def is_truncatable_prime(value: int, primes: Set[int]) -> bool:
46
    """ Test whether `value` is both left to right and right to left truncatable or not
47
48
    :param value: the integer to test
49
    :param primes: a set of primes containing at least those in the range :math:`[2, value]`
50
    :return: whether `value` is truncatable or not
51
    """
52
53
    # Check for right to left truncatable
54
    temp = value
55
    while temp >= 10:
56
        temp //= 10
57
        if temp not in primes:
58
            return False
59
60
    # Check for left to right truncatable
61
    while num_digits(value) > 1:
62
        value %= 10 ** (num_digits(value) - 1)
63
        if value not in primes:
64
            return False
65
66
    return True
67
68
69
def solve():
70
    """ Compute the answer to Project Euler's problem #37 """
71
    upper_bound = 740000  # found by trial and error
72
    primes = set(Primes(upper_bound=upper_bound))
73
    multidigit_primes = filter(lambda p: p >= 10, primes)
74
    truncatable_primes = filter(lambda p: is_truncatable_prime(p, primes), multidigit_primes)
75
    answer = sum(truncatable_primes)
76
    return answer
77
78
79
expected_answer = 748317
0 ignored issues
show
Coding Style Naming introduced by
The name expected_answer does not conform to the constant naming conventions ((([A-Z_][A-Z0-9_]*)|(__.*__))$).

This check looks for invalid names for a range of different identifiers.

You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements.

If your project includes a Pylint configuration file, the settings contained in that file take precedence.

To find out more about Pylint, please refer to their site.

Loading history...
80