Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
tree: 061e659cfb
Fetching contributors…

Cannot retrieve contributors at this time

file 52 lines (43 sloc) 1.296 kb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
import math

def is_prime(n):
    if n < 2:
        return False
    for j in range(2, math.sqrt(n)+1):
        if n%j == 0:
            return False
    return True

def is_truncatable_prime(n):
    if not is_prime(n):
        return False
    orig = n = str(n)
    while len(n) > 1:
        n = n[:-1]
        if not is_prime(int(n)):
            return False
    n = orig
    while len(n) > 1:
        n = n[1:]
        if not is_prime(int(n)):
            return False
    return True

# primes or odd numbers will be considered valid digits
valid_digits = [1, 2, 3, 5, 7, 9]

# seed it with the valid ones
possibles = list(valid_digits)

# generate numbers and check for their 'truncatable-ness'
found = []

while len(found) < 11:
    new_possibles = []
    for i in xrange(len(possibles)):
        last_digit = possibles[i] % 10
        first_digit = int(str(possibles[i])[0])
        for digit in valid_digits:
            new_possibles.append(int(str(possibles[i]) + str(digit)))
            new_possibles.append(int(str(digit) + str(possibles[i])))
                
    possibles = []
    
    for num in new_possibles:
        if num not in found and is_truncatable_prime(num):
            found.append(num)
        if is_prime(num):
            possibles.append(num)

print sum(found)
Something went wrong with that request. Please try again.