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.

Haskell

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   0m27.894s
user   0m27.680s
sys    0m0.012s

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   0m6.438s
user   0m6.392s
sys    0m0.000s