# Project Euler Problem 37 Solution

## Question

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.

isPrime :: Int -> Bool
isPrime n | n <= 1 = False
| otherwise = not $or [n rem x == 0 | x <- [2..floor$ sqrt $fromIntegral n]] expand :: [Int] -> [Int] expand ns = [p | n <- ns, k <- [1, 3, 7, 9], let p = 10*n + k, isPrime p] candidates :: [Int] candidates = dropWhile (< 10)$ concat $takeWhile (not . null) (iterate expand [2, 3, 5, 7]) leftTruncatable :: Int -> Bool leftTruncatable n = all isPrime$ takeWhile (< n) [n rem 10^x | x <- [1..]]

main :: IO ()
main = print $sum$ filter leftTruncatable candidates
$ghc -O2 -o truncatable-primes truncatable-primes.hs$ time ./truncatable-primes
real   0m0.003s
user   0m0.000s
sys    0m0.000s

## Python

#!/usr/bin/env python
from collections import defaultdict
import math
from functools import reduce

def factorize(n):
if n < 1:
raise ValueError('fact() argument should be >= 1')
if n == 1:
return []  # special case
res = []
# iterate over all even numbers first.
while n % 2 == 0:
res.append(2)
n //= 2
# try odd numbers up to sqrt(n)
limit = math.sqrt(n+1)
i = 3
while i <= limit:
if n % i == 0:
res.append(i)
n //= i
limit = math.sqrt(n+i)
else:
i += 2
if n != 1:
res.append(n)
return res

def num_divisors(n):
factors = sorted(factorize(n))
histogram = defaultdict(int)
for factor in factors:
histogram[factor] += 1
# number of divisors is equal to product of
# incremented exponents of prime factors
from operator import mul
try:
return reduce(mul, [exponent + 1 for exponent in list(histogram.values())])
except:
return 1

def is_prime(num):
if num_divisors(num) == 2 and num > 1:
return True
else:
return False

def is_truncatable(prime):
if not is_prime(prime):
return False

digits = [int(digit) for digit in str(prime)]
if len(digits) == 1:
return False

for i in range(1, len(digits)):
left = int(''.join(str(digit) for digit in digits[:i]))
right = int(''.join(str(digit) for digit in digits[i:]))
if not is_prime(left) or not is_prime(right):
return False
return True

def main():
print(sum(n for n in range(1, 1000000) if is_truncatable(n)))

if __name__ == "__main__":
main()
$time python3 truncatable-primes.py real 0m23.440s user 0m23.436s sys 0m0.000s ## Ruby #!/usr/bin/env ruby require 'mathn' puts (10..1000000).select { |i| (0..i.to_s.length-1).all? { |j| i.to_s[0..j].to_i.prime? && i.to_s[j..-1].to_i.prime? } }.reduce(:+) $ time ruby truncatable-primes.rb
real   0m2.292s
user   0m2.288s
sys    0m0.000s