Euler Solution 37

From ProgSoc Wiki

Jump to: navigation, search

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
Personal tools