Problem 37

In the 37th Euler problem, I used the Hackage package containing the NumberTheory.Sieve.ONeill library in order to have access to an efficient infinite list of primes. Then it was a matter of manipulating lists to achieve the result.

    import NumberTheory.Sieve.ONeill
    import List
    import Char

    myElem (x:xs) n
      | n == x = True
      | n > x  = myElem xs n
      | n < x  = False

The myElem function searches a specific number in a sorted list (i.e. in the infinite prime list). Furthermore, it was a matter of defining the following functions:

    g :: Int -> Bool
    g n = foldr (&&) True (truncatable (show n))

    truncatable :: [Char] -> [Bool]
    truncatable n = map (myElem primes) (map h (delete "" (nub (inits n ++ tails n))))
      where h n = read n :: Int

    main = print $ sum (take 11 $ filter g (drop 4 primes))

The truncatable function produces a list of boolean values indicating if all the numbers of a list are prime, while g performs the logical and over the list. Finally, the main function produces the result with the following execution time:

real 0m0.670s user 0m0.662s sys 0m0.006s