1
\$\begingroup\$

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.

Here's my implementation in Python, it's very slow(takes like 10 secs to show results. How to make it faster, more efficient?

def is_prime(number):
    """returns True for a prime number, False otherwise."""
    if number == 1:
        return False
    factor = 2
    while factor * factor <= number:
        if number % factor == 0:
            return False
        factor += 1
    return True


def get_truncatable(n):
    """returns truncatable numbers within range n."""
    for number in range(9, n, 2):
        if is_prime(number):
            check = 0
            for index in range(-1, -len(str(number)), -1):
                less_right = str(number)[:index]
                if not is_prime(int(less_right)):
                    check += 1
            if check == 0:
                for index in range(1, len(str(number))):
                    less_left = str(number)[index:]
                    if not is_prime(int(less_left)):
                        check += 1
                if check == 0:
                    yield number


if __name__ == '__main__':
    print(sum(list(get_truncatable(1000000))))
\$\endgroup\$
1
\$\begingroup\$

You know that a prime other than 2 and 5 ends in 1, 3, 7 or 9. What does that tell you about the digits of x if it is right truncatable? It tells you that all the digits after the first must be 1, 3, 7 or 9.

On the other hand, if you have a four digit left-truncatable number, then the last three digits are also left truncatable. So the find the n+1 digit both left and right truncatable numbers, you take an n digit one which starts with 1, 3, 7 or 9, and prepend any of the digits 1 to 9, and check that the result is both a prime and right-truncatable.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy