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