# Euler Solution 37

### From ProgSoc Wiki

# Solutions for Problem 37

Define f(n) to be True if n is prime and if you truncate n from left to right or right to left, every number produced is also prime. For example: 3797, 379, 37, 3, 797, 97 and 7 are all prime.

There are exactly 11 such numbers that have more than 1 digit, find their sum.

## Haskell by SanguineV

Runtime: 2.918 seconds (on aglaope)

{- Generate primes lazily -} primes :: [Integer] primes = 2:3:primes' where 1:p:candidates = [6*k+r | k <- [0..], r <- [1,5]] primes' = p : filter isPrime candidates isPrime n = all (not . divides n) $ takeWhile (\p -> p*p <= n) primes' divides n p = n `mod` p == 0 {- Note that prime truncatable numbers may begin with 2, but every other digit must - be odd. Write a test for this to save checking needlessly. -} okDigs :: Integer -> Bool okDigs n | n < 10 = n == 2 || mod n 2 == 1 okDigs n = mod (mod n 10) 2 == 1 && okDigs (div n 10) {- Find an element in a sorted list. -} elem' :: Integer -> [Integer] -> Bool elem' n [] = False elem' n (x:xs) | x == n = True elem' n (x:xs) | x > n = False elem' n (x:xs) = elem' n xs {- Return the number of digits of an integer. -} digs :: Integer -> Integer digs n | n < 10 = 1 digs n = 1 + (digs (div n 10)) {- Return a list of truncated numbers based on a number. -} truncs :: Integer -> [Integer] truncs n | n < 10 = [] truncs n = foldl (\x y -> x ++ [mod n y] ++ [div n y]) [] (map (\z -> pow 10 z) [1..((digs n) - 1)]) {- Calculate the power of n to the p. -} pow :: Integer -> Integer -> Integer pow n 0 = 1 pow n 1 = n pow n p = n * (pow n (p - 1)) {- Define a list of primes that are potentially prime truncatable. -} prims = filter okDigs primes {- Find all the primes that are prime truncatable, starting with the - pre-filtered primes. Drop the first 4 as they are single digit, take - the next 11 as we know there are only 11. Sum them and print the result. -} main = print (sum (take 11 (drop 4 (filter (\x -> foldl (\a b -> a && (elem' b prims)) True (truncs x)) prims))))

I solved the first 10 by hand, but wrote the code to efficiently check my solutions and so expanded it to find the last one.

## Python by Althalus

Runtime: 2.29 seconds

import time import math start_time=time.time() #Read in from a long list of Primes I generated for an earlier problem (Why re-generate primes every second problem?) #Limit the primes list to those with no even digits in them. #(Sooner or later during the truncating, one of those digits will be on the end, creating something divisible by 2: IE #NO prime with an even digit can truncate.) Similarly, nothing with a 5 can be truncated either. file = open(r'primes.txt','r') primes = [int(i) for i in file.readlines() if len(set(i).intersection(set('245680'))) == 0 \ #2 and 5 are both primes however, and if we left it here, they would not be in our list of primes. #Numbers beginning with 2 and 5, also can not be excluded from our list (though a 2 or 5 elsewhere in a number can be safely excluded). or ((i[0] == '2' or i[0] == '5') and len(set(i[1:]).intersection(set('245680'))) == 0)] file.close() def isTruncatable(n): n = str(n) if len(n) == 1: return False for i in range(1,len(n)): if int(n[i:]) not in primes or n[i:] == 1: return False for i in range(1,len(n)): if int(n[:-i]) not in primes or n[:-i] == 1: return False return True list = [] count = 0 for p in primes: if isTruncatable(p): count+=1 print p list.append(p) print list print count print sum(list) run_time = time.time() - start_time print run_time