Introduction

When first learning a programming language, I like to work Project Euler problems. Over the years I have accumulated solutions in several languages. I want to share those solutions in a way that may of interest. I try to do several things.

Why functional programming?

I believe that the function is the most important symbolic technology yet devised, speech excepted. I came to programming from mathematics rather than computer science. To a mathematician the function is a perfectly natural abstraction, and a wildly successful one. Mathematics has made possible the science and technology that shapes our world and how we think about it. Modern mathematics is essentially an extended meditation on functions. Functions just work.

I have waited a long time to see functional programming gain some semblance of commercial acceptance. We’re not there yet, but the prospects seem better than ever.

Occasionally I hear a developer complain of being unable to understand the functional approach. If that describes you, allow me to make a suggestion. The Project Euler problems lend themselves very nicely to functional programming methods.

Let’s say you want to learn Haskell; try this. Work some of the problems shown here. Read the solutions I present until you understand the approach. Then reconstruct the Haskell solutions, without looking at tem. If you get stuck, read the non-Haskell solutions and consult the Oracle at Google as required. This is what I call active reading.

I hope that by seeing the same solution from multiple perspectives, the active reader may come to see the underlying functional approach as something independent of its particular expression in a given language. I also hope that if you see (and use!) a few workhorse patterns again and again, the unfamiliar may come to be familiar, and simple FP will start to become easy.

Give function programming a shot; you may find you like it.

Caveats

I expect that my solutions may not be entirely idiomatic in any of the four languages I have chosen. I claim no real expertise in any of these languages, not having put in my 10,000 hours in any of them. Pull requests intended to make a solution more idiomatic are welcome, as are questions.

Problem 1

(ns org.drcabana.euler.p01)

(defn qualifies [x]
  (or (zero? (mod x 5))
      (zero? (mod x 3))))

(defn solve []
  (reduce + (filter qualifies (range 1 1000))))

(defn -main []
  (println (solve)))

module p01

let solution = 
    [1..999] 
    |> List.filter (fun x -> x % 3 = 0 || x % 5 = 0)
    |> List.sum 

printfn "%d" solution
qualifies x = (x `mod` 3 == 0) || (x `mod` 5 == 0)
solution = sum $ filter qualifies [1..999]

main = do print solution
def qualifies(x):
   return (x % 3 == 0) or (x % 5 == 0)

def solution():
    return sum(x for x in range(1, 1000) if qualifies(x))

if __name__ == "__main__":
    print(solution())

Problem 1 is to sum the positive integers less than 1000 which are divisible by either 3 or 5. The original problem statement is available here.

The qualifies function returns true if and only if x is divisible by 3 or by 5.

The solution illustrates a recurring pattern:

Notice that the python and clojure range functions do not include the upper bound, while the haskell and f# [1..n] notation does.

Problem 2

(ns org.drcabana.euler.p02)

(defn fibonacci []
  (letfn [(fib [[a b]] [b (+' a b)])]
    (->> [0 1]
         (iterate fib)
         (map first))))

(defn solve []
  (->> (fibonacci)              
       (take-while #(< % 4000001)) 
       (filter even?)              
       (reduce +)))

(defn -main []
  (println (solve)))
module p02

let fibonacci =
    let f (a:bigint, b:bigint) = Some (a, (b, a + b))
    Seq.unfold f (0I, 1I)       

let solution limit =
    fibonacci
    |> Seq.takeWhile (fun n -> n < limit)
    |> Seq.filter (fun n -> n % 2I = 0I)
    |> Seq.sum    

printfn "%A" <| solution 4000001I
module P02 where

fibonacci = map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)
solve = sum $ filter even $ takeWhile (< 4000001) fibonacci

main = do print solve 
from itertools import takewhile

def fibonacci():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

def solution():
    n = 4000001
    fibs = takewhile(lambda x: x<n, fibonacci())
    return sum(x for x in fibs if x % 2 == 0)

if __name__ == "__main__":
    print(solution())

Problem 2 is to sum the even Fibonacci numbers not exceeding four million. The original problem statement is available here.

The pattern is pretty much the same as in the previous problem:

I do not use the widely seen definition that fib(n+1) = fib(n) + fib(n-1) because it is tragically inefficient, with time complexity of O(exp n).

Problem 3

(ns org.drcabana.euler.p03)

(defn least-divisor [k n]
  (let [candidates (drop-while #(pos? (rem n %)) (range k n))]
    (if (seq candidates) (first candidates) n)))

(defn prime-factors [n]
  (loop [n n factors [] k 2]
    (if (= 1 n)
      factors
      (let [d (least-divisor k n)]
        (recur (quot n d) (conj factors d) d)))))

(defn solve []
  (reduce max (prime-factors 600851475143)))

(defn -main []
  (println (solve)))

module p03

open System.Numerics

let rec leastDivisor (k : BigInteger) (n : BigInteger) =
    if n % k = 0I then k 
    else leastDivisor (k + 1I) n 

let rec pfactors (k : BigInteger) (n : BigInteger) =
    let d = leastDivisor k n
    if d = n then [n] 
    else d :: pfactors d (n / d)

let primeFactors (n : BigInteger) = pfactors 2I n
let solution = primeFactors 600851475143I |> List.max
printfn "%A" solution
module P03 where

least_divisor :: Integer -> Integer -> Integer
least_divisor k n =
  let factors = dropWhile (\x -> n `mod` x > 0) [k .. n] 
  in case factors of
      [] -> n
      f:fs -> f

pfactors k n =
  if d == n
    then [n]
    else d : pfactors d (n `div` d)
  where d = least_divisor k n

solution = maximum $ pfactors 2 600851475143

main = do print solution
from itertools import dropwhile

def least_divisor(k,n):
    while k < n:
        if n%k == 0: return k
        else: k +=1
    return n

def prime_factors(n):
    k = 2
    N = n
    factors = []
    while N > 1:
        k = least_divisor(k,N)
        factors.append(k)
        N = N/k
    return factors

def solution():
    n = 600851475143
    return max(prime_factors(n))

if __name__ == "__main__":
    print(solution())

Problem 3 is to find the largest prime divisor of 600851475143. The original problem statement is available here.

The least_divisor(k, n) function computes the least divisor of n in the (inclusive) range k..n. Since n divides n, and the range is finite, there must exist a least divisor of n in the range.

Problem 4

(ns org.drcabana.euler.p04)

(defn palindrome? [word]
  (let [chars (seq (str word))]
    (= chars (reverse chars))))

(defn solve []
  (let [products
       (for [a (range 100 1000)
             b (range 100 (inc a))]
         (* a b))]
    (reduce max (filter palindrome? products))))

(defn -main[]
  (println (solve)))
module p04

let palindrome n =
   let word = string n |> Seq.toArray
   word = Array.rev word

let solution =
   [for a in 100..999 do 
    for b in 100..a -> a*b] 
   |> List.filter palindrome
   |> List.max

printfn "%A" solution
palindrome n = 
    word == reverse word
    where word = show n

solution = 
    maximum $ filter palindrome products
    where products = [a*b | a <- [100..999], b <- [100..a]]

main = do print solution
def palindrome(word):
   w = str(word)
   return w == w[::-1]

def solution():
   products = [a*b for a in range(100,1000) for b in range(100, a)]
   return max([p for p in products if palindrome(p)])

if __name__ == "__main__": 
    print(solution())

Problem 4 is to find the largest palindrome made from the product of two 3-digit numbers. The original problem statement is available here.

There are only 900 positive 3-digit integers, so brute force is the way to go. Notice that we again construct a sequence, filter it, then reduce it.

Problem 5

(ns org.drcabana.euler.p05)

(defn gcd [a b]
  (if (zero? b)
    a
    (gcd b (mod a b))))

(defn lcm [a b]
  (/ (* a b) (gcd a b)))

(defn solve []
  (reduce lcm (range 1 21) ))

(defn -main[] 
  (println (solve)))
module p05

let rec gcd a b  =
  if b = 0 then a
  else gcd b (a % b)

let lcm a b = (a * b) / (gcd a b)

let solution = List.reduce lcm [1..20]
printfn "%A" solution
import Prelude hiding (gcd,lcm)
import Data.List (foldl')

gcd a b  =
  if b == 0
     then a
     else gcd b (a `mod` b)

lcm a b = (a * b) `div` (gcd a b)

solution = foldl' lcm 1 [1..20]

main = do print solution
def gcd(a, b):
  if b == 0:
     return a
  else:
     return gcd(b, a%b)

def lcm(a, b): 
  return int((a * b) / gcd(a, b))

def solution(): 
  return reduce(lcm, range(1, 21))

if __name__ == "__main__":
    print(solution())

Problem 5 is to find the least common multiple of the integers {1,2,…,20}. The original problem statement is available here.

A simple way implement the LCM function to use the greatest common divisor function, GCD. It can be proven that

LCM(a b) * GCD(a b) = a * b

so we can use GCD to implement LCM. We use Euclid’s algorithm to implement GCD.

Problem 6

(ns org.drcabana.euler.p06)

(defn solve []
  (let [values (range 1 101)
        total (reduce + values)]
    (- (* total total)
       (reduce + (map #(* % %) values)))))

(defn -main []
  (println (solve)))
module p06

let squares = 
  [for x in [1..100] -> x*x]

let squareOfSum = 
  let total = Seq.sum [1..100]
  total * total

let solution = squareOfSum - (Seq.sum squares)

printfn "%d" solution
solution = total*total - sum [n*n | n <- values]
    where values = [1..100]
          total = sum values

main = do print solution
def solution():
    values = range(1,101)
    total = sum(values)
    return total*total - sum([n*n for n in values])

if __name__ == "__main__":  
    print(solution())

Problem 6 is to find the difference between the square of the sum of 1 … 100 and the sum of the squares of 1 … 100. The original problem statement is available here.

Problem 7

(ns org.drcabana.euler.p07
  (:use [clojure.math.numeric-tower :only (sqrt ceil)]))

(defn contains-divisor [[a b] n]
  (cond 
    (> a b) false
    (zero? (mod n a)) true
    true (recur [(inc a) b] n)))

(defn prime? [n]
  (if (< n 2) false
    (let [limit (ceil (sqrt n))]
      (not (contains-divisor [2 limit] n)))))

(defn primes []
  (let [odd-numbers (iterate #(+ 2 %) 3)]
    (cons 2 (filter prime? odd-numbers))))

(defn solve[]
    (nth (primes) 10000))

(defn -main []
  (println (solve)))
module p07

let rec containsDivisor (a : int64 , b : int64) n =
    if a > b then false
    elif n % a = 0L then true
    else containsDivisor (a+1L, b) n

let isPrime n =
    match n with
    | 2L | 3L -> true
    | _ -> let limit = double n |> sqrt |> ceil |> int64
           not <| containsDivisor (2L, limit) n 

let primes = 
    let oddNumbers = Seq.unfold (fun a -> Some(a,a+2L)) 3L
    oddNumbers 
    |> Seq.filter isPrime
    |> Seq.append [2L]

let solution = Seq.nth 10000 primes
printfn "%A" solution
module P07 where

containsDivisor a b n =
  if a > b then False
  else if n `mod` a == 0 then True
  else containsDivisor (a+1) b n

isPrime n
  | n < 2 = False
  | n == 2 = True 
  | n == 3 = True
  | otherwise = not $ containsDivisor 2 limit n
      where limit = ceiling $ sqrt $ fromIntegral n

primes = filter isPrime (2 : [3,5..])
solution = primes !! 10000
main = do print solution

import math

def contains_divisor(a,b,n):
    while a <= b:
        if n % a == 0: return True
        a += 1
    return False

def is_prime(n):
    if n < 2: return False
    if n == 2: return True
    if n == 3: return True
    limit = int(math.ceil(math.sqrt(n)))
    return not(contains_divisor(2,limit,n))

def primes():
    yield 2
    p = 3
    while True:
        if is_prime(p): yield p
        p += 2

def solution():
    p = primes()
    for k in range(1,10001):
        p.next()
    return p.next()

if __name__ == "__main__":
    print(solution())

Problem 7 is to find the 10001-th prime number. The orginal problem statement is available here.

The method used to generate primes, trial division, is easy to understand, but it is slow. To determine whether n is prime, we simply try dividing n by every k in 2..n-1. If we find a divisor, then n is not prime.

In practice we can stop the trial divisions once k exceeds ceiling(sqrt(n)). This improves the performance of the algorithm from O(wretched) to O(slow).

We’ll see something faster in problem 10.

Problem 8

(ns org.drcabana.euler.p08)

(defn digit-to-int [char]
  {:pre [(#{\0 \1 \2 \3 \4 \5 \6 \7 \8 \9} char)]}
  (Integer/parseInt (str char)))

(defn solve []
  (let [product (partial reduce *)
        digits "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"]
    (->> (map digit-to-int digits)
         (partition 5 1)
         (map product)
         (reduce max))))

(defn -main [] 
    (println (solve)))
module p08

let digits = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"

let rec partition xs =
   match xs with
   | a::b::c::d::e :: ys -> [a; b; c; d; e] :: partition (b::c::d::e :: ys)
   | _ -> []

let product xs = List.reduce (*) xs

let solution = 
  digits 
  |> List.ofSeq
  |> List.map (string >> int)
  |> partition
  |> List.map product
  |> List.max

printfn "%A" solution
import Data.Char (digitToInt)

digits = 
   "73167176531330624919225119674426574742355349194934\
   \96983520312774506326239578318016984801869478851843\
   \85861560789112949495459501737958331952853208805511\
   \12540698747158523863050715693290963295227443043557\ 
   \66896648950445244523161731856403098711121722383113\
   \62229893423380308135336276614282806444486645238749\
   \30358907296290491560440772390713810515859307960866\
   \70172427121883998797908792274921901699720888093776\
   \65727333001053367881220235421809751254540594752243\
   \52584907711670556013604839586446706324415722155397\
   \53697817977846174064955149290862569321978468622482\
   \83972241375657056057490261407972968652414535100474\
   \82166370484403199890008895243450658541227588666881\
   \16427171479924442928230863465674813919123162824586\
   \17866458359124566529476545682848912883142607690042\
   \24219022671055626321111109370544217506941658960408\
   \07198403850962455444362981230987879927244284909188\
   \84580156166097919133875499200524063689912560717606\
   \05886116467109405077541002256983155200055935729725\
   \71636269561882670428252483600823257530420752963450"

partition xs n  = 
    if n > length xs
       then []
       else (take n xs) : partition (tail xs) n

solution = maximum $ map product (partition nums 5)
    where nums = map digitToInt digits

main = print solution

from operator import mul

digits = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"

def partition(xs, n, offset=1):
    limit = len(xs)+1-n
    return [ xs[i:i+n] for i in range(0, limit, offset)]

def product(lst):
    return reduce(mul, lst)

def solution():
    nums = map(int, digits)
    seqs = partition(nums, 5)
    return max(map(product, seqs))

if __name__ == "__main__":
    print(solution())

In problem 8 we are given a string of numeric digits, and asked to find the maximal product of five consecutive digits. The original problem statement is available here.

Clojure’s partition function is extremely useful. I suspect Clojure borrowed it from Mathematica. I could not find a similar function in Python, Haskell, or F#, so I had to roll my own (relatively limited) versions.

I took a different approach to the implementation of partition in each language, but the approach to the overall problem is the same across the implementations:

Problem 9

(ns org.drcabana.euler.p09)

(defn pythagorean?
  [a b c]
  (= (* c c) (+ (* a a)
                (* b b))))

(defn solve []
  (let [triples
        (for [a (range 1 1000)
              b (range a 1000)
              c [(- 1000 a b)]
              :when (pythagorean? a b c)]
          [a b c])]
    (reduce * (first triples))))

(defn -main []
  (println (solve)))
module p09

let pythagorean (a, b, c) = 
  c*c = a*a + b*b

let triples = 
  [for a in [1..999] do 
   for b in [a..999] -> (a,b, 1000-a-b)]

let solution = 
  triples
  |> List.filter pythagorean
  |> List.head
  |> (fun (a,b,c) -> a*b*c)

printfn "%A" solution

pythagorean [a, b, c] = c*c == a*a + b*b
triples = [[a,b,1000-(a+b)] | a <- [1..999], b <-[a..999]]  
solution = (map product $ filter pythagorean triples) !! 0

main = print solution

def pythagorean(a,b,c): 
    return c*c == a*a + b*b

triples = [[a,b,1000-(a+b)] for a in range(1,999) for b in range(a,999)]

def solution():
    return [a*b*c for [a,b,c] in triples if pythagorean(a,b,c)][0]

if __name__ == "__main__":
    print(solution())

Problem 9 is to find the Pythagorean triple that sums to 1000, and form the product of its elements. That is, return the product of postive integers a,b,c such that

The original problem statement is available here.

Problem 10

(ns org.drcabana.euler.p10
  (:use [clojure.set :only (union)]))

(defn sieve [m k]
  (if (m k)
      (let [maps (for [v (m k)] {(+ k v) #{v}})]
        (merge-with union m (reduce conj maps)))
      (assoc m (* k k) #{k})))

(defn primes-up-to [k]
  (let [domain (range 2 k)
        composites (reduce sieve {} domain)]
    (remove composites domain)))

(defn solve []
  (reduce + (primes-up-to 2000000)))

(defn -main []
  (println (solve)))

module p10

open System.Numerics

let rec sieve n composites =
    let rec nextKey j k =
        let x = j+k
        if x % 2 = 0 || (Map.containsKey x composites) 
            then nextKey x k
            else x

    match Map.tryFind n composites with
    | None -> 
        seq {yield n
             yield! sieve (n+2) (composites.Add (n*n, n))}
    | Some d ->
        sieve (n+2) (composites.Add (nextKey n d, d))

let primes = 
    seq {yield 2
         yield! sieve 3 Map.empty}

let rec sum (total:bigint) (xs:int seq) =
    match List.ofSeq xs with
    | x :: rest -> sum (total + bigint x) rest
    | [] -> total

let solution k =
    primes 
    |> Seq.takeWhile (fun x -> x < k)
    |> sum 0I

printfn "%A" <| solution 2000000
import P07 (isPrime)

primes = 2 : filter isPrime [3,5..]
solution = sum $ takeWhile (< 2000000) primes

main = print solution
def sieve( ):
    yield 2
    Composites = { }
    n = 3
    while True:
        d = Composites.pop(n, None)
        if d == None:
            Composites[n*n] = n
            yield n
        else:          # d divides n
            x = n + d
            while x in Composites or x % 2 == 0:
                x += d
            Composites[x] = d
        n += 2

def solution():
    ps = sieve()
    n = 0
    total = 0
    while n < 2000000:
        total += n
        n = ps.next()
    return total

if __name__ == "__main__":
    print(solution())

Problem 10 is to find the sum of all the primes less than two million. The original problem statement is available here.

The trial division method of prime generation used in problem 7 is not fast enough for the problem at hand. We need a new approach, a sieve method. Sieve methods are nicely described in The Genuine Sieve of Eratosthenes by Melissa O'Neill, and in any number of other online resources.

A warning is in order. In this problem my Clojure solution is not the “same” as in the other three languages, although it is conceptually similar. I describe the Clojure solution in a separate appendix. I think it is exceedingly cool, and it puts Clojure’s handling of maps to fine use, so I indulged myself.

Problem 11

(ns org.drcabana.euler.p11)

(def digits [
    8, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91,  8,
   49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 04, 56, 62, 00,
   81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 03, 49, 13, 36, 65,
   52, 70, 95, 23, 04, 60, 11, 42, 69, 24, 68, 56, 01, 32, 56, 71, 37, 02, 36, 91,
   22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80,
   24, 47, 32, 60, 99, 03, 45, 02, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50,
   32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70,
   67, 26, 20, 68, 02, 62, 12, 20, 95, 63, 94, 39, 63,  8, 40, 91, 66, 49, 94, 21,
   24, 55, 58, 05, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72,
   21, 36, 23,  9, 75, 00, 76, 44, 20, 45, 35, 14, 00, 61, 33, 97, 34, 31, 33, 95,
   78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 03, 80, 04, 62, 16, 14,  9, 53, 56, 92,
   16, 39, 05, 42, 96, 35, 31, 47, 55, 58, 88, 24, 00, 17, 54, 24, 36, 29, 85, 57,
   86, 56, 00, 48, 35, 71, 89, 07, 05, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58,
   19, 80, 81, 68, 05, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 04, 89, 55, 40,
   04, 52,  8, 83, 97, 35, 99, 16, 07, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66,
   88, 36, 68, 87, 57, 62, 20, 72, 03, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69,
   04, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18,  8, 46, 29, 32, 40, 62, 76, 36,
   20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 04, 36, 16,
   20, 73, 35, 29, 78, 31, 90, 01, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 05, 54,
   01, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 01, 89, 19, 67, 48
])

(defn mat [[j,k]] 
  (let [valid #(<= 0 % 19)
        offset (+ k (* 20 j))]
    (if (and (valid j) (valid k))
      (digits offset)
      0)))

(defn product [xs]
  (reduce * xs))

(defn east [j k]
  (for [d (range 4)]
    [(+ j d) k]))

(defn south [j k]
  (for [d (range 4)]
    [j (+ k d)]))

(defn southeast [j k]
  (for [d (range 4)]
    [(+ j d) (+ k d)]))

(defn southwest [j k]
  (for [d (range 4)]
    [(- j d) (+ k d)]))

(defn score [j k]
  (reduce max [(product (map mat (east j k)))
               (product (map mat (south j k)))
               (product (map mat (southeast j k)))
               (product (map mat (southwest j k)))]))

(defn solve []
  (reduce max
    (for [j (range 19) k (range 19)]
       (score j k))))

(defn -main[]
  (println (solve)))
module p11

let digits = 
  [ 8; 02; 22; 97; 38; 15; 00; 40; 00; 75; 04; 05; 07; 78; 52; 12; 50; 77; 91;  8;
   49; 49; 99; 40; 17; 81; 18; 57; 60; 87; 17; 40; 98; 43; 69; 48; 04; 56; 62; 00;
   81; 49; 31; 73; 55; 79; 14; 29; 93; 71; 40; 67; 53; 88; 30; 03; 49; 13; 36; 65;
   52; 70; 95; 23; 04; 60; 11; 42; 69; 24; 68; 56; 01; 32; 56; 71; 37; 02; 36; 91;
   22; 31; 16; 71; 51; 67; 63; 89; 41; 92; 36; 54; 22; 40; 40; 28; 66; 33; 13; 80;
   24; 47; 32; 60; 99; 03; 45; 02; 44; 75; 33; 53; 78; 36; 84; 20; 35; 17; 12; 50;
   32; 98; 81; 28; 64; 23; 67; 10; 26; 38; 40; 67; 59; 54; 70; 66; 18; 38; 64; 70;
   67; 26; 20; 68; 02; 62; 12; 20; 95; 63; 94; 39; 63;  8; 40; 91; 66; 49; 94; 21;
   24; 55; 58; 05; 66; 73; 99; 26; 97; 17; 78; 78; 96; 83; 14; 88; 34; 89; 63; 72;
   21; 36; 23;  9; 75; 00; 76; 44; 20; 45; 35; 14; 00; 61; 33; 97; 34; 31; 33; 95;
   78; 17; 53; 28; 22; 75; 31; 67; 15; 94; 03; 80; 04; 62; 16; 14;  9; 53; 56; 92;
   16; 39; 05; 42; 96; 35; 31; 47; 55; 58; 88; 24; 00; 17; 54; 24; 36; 29; 85; 57;
   86; 56; 00; 48; 35; 71; 89; 07; 05; 44; 44; 37; 44; 60; 21; 58; 51; 54; 17; 58;
   19; 80; 81; 68; 05; 94; 47; 69; 28; 73; 92; 13; 86; 52; 17; 77; 04; 89; 55; 40;
   04; 52;  8; 83; 97; 35; 99; 16; 07; 97; 57; 32; 16; 26; 26; 79; 33; 27; 98; 66;
   88; 36; 68; 87; 57; 62; 20; 72; 03; 46; 33; 67; 46; 55; 12; 32; 63; 93; 53; 69;
   04; 42; 16; 73; 38; 25; 39; 11; 24; 94; 72; 18;  8; 46; 29; 32; 40; 62; 76; 36;
   20; 69; 36; 41; 72; 30; 23; 88; 34; 62; 99; 69; 82; 67; 59; 85; 74; 04; 36; 16;
   20; 73; 35; 29; 78; 31; 90; 01; 74; 31; 49; 71; 48; 86; 81; 16; 23; 57; 05; 54;
   01; 70; 54; 71; 83; 51; 54; 69; 16; 92; 33; 48; 61; 43; 52; 01; 89; 19; 67; 48 ]

let mat (j,k) = 
    let valid n = 
        0 <= n  &&  n < 20
    if valid j && valid k then digits.[20*j + k]
    else 0

let nbhds (j,k) =
    [[for d in 0..3 -> (j+d, k)];
     [for d in 0..3 -> (j+d, k+d)];
     [for d in 0..3 -> (j,   k+d)];
     [for d in 0..3 -> (j-d, k+d)]] 

let tally nbhd = 
    List.map mat nbhd
    |> List.reduce (*)

let score (j,k) = 
    nbhds (j,k)
    |> List.map tally
    |> List.reduce max

let solution =
    [for j in 0..19 do
     for k in 0..19 -> score (j,k)]
    |> List.reduce max

printfn "%A" solution
digits =
  [08, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91, 08,
   49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 04, 56, 62, 00,
   81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 03, 49, 13, 36, 65,
   52, 70, 95, 23, 04, 60, 11, 42, 69, 24, 68, 56, 01, 32, 56, 71, 37, 02, 36, 91,
   22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80,
   24, 47, 32, 60, 99, 03, 45, 02, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50,
   32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70,
   67, 26, 20, 68, 02, 62, 12, 20, 95, 63, 94, 39, 63, 08, 40, 91, 66, 49, 94, 21,
   24, 55, 58, 05, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72,
   21, 36, 23, 09, 75, 00, 76, 44, 20, 45, 35, 14, 00, 61, 33, 97, 34, 31, 33, 95,
   78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 03, 80, 04, 62, 16, 14, 09, 53, 56, 92,
   16, 39, 05, 42, 96, 35, 31, 47, 55, 58, 88, 24, 00, 17, 54, 24, 36, 29, 85, 57,
   86, 56, 00, 48, 35, 71, 89, 07, 05, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58,
   19, 80, 81, 68, 05, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 04, 89, 55, 40,
   04, 52, 08, 83, 97, 35, 99, 16, 07, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66,
   88, 36, 68, 87, 57, 62, 20, 72, 03, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69,
   04, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 08, 46, 29, 32, 40, 62, 76, 36,
   20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 04, 36, 16,
   20, 73, 35, 29, 78, 31, 90, 01, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 05, 54,
   01, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 01, 89, 19, 67, 48]

mat (j, k) = if valid j && valid k                                                             
                then digits !! offset                                                          
                else 0                                                                         
             where offset = 20 * j + k                                                         
                   valid idx =  0 <= idx && idx < 20                                           

score j k = maximum [points [(j+del, k)     | del <- [0..3]],
                     points [(j, k+del)     | del <- [0..3]],
                     points [(j+del, k+del) | del <- [0..3]],
                     points [(j-del, k+del) | del <- [0..3]]]
            where points = product . map mat

solution = maximum [score j k | j <- [0..19], k <- [0..19]]

main = print solution
from operator import mul

digits = [
    8, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91,  8,
   49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 04, 56, 62, 00,
   81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 03, 49, 13, 36, 65,
   52, 70, 95, 23, 04, 60, 11, 42, 69, 24, 68, 56, 01, 32, 56, 71, 37, 02, 36, 91,
   22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80,
   24, 47, 32, 60, 99, 03, 45, 02, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50,
   32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70,
   67, 26, 20, 68, 02, 62, 12, 20, 95, 63, 94, 39, 63,  8, 40, 91, 66, 49, 94, 21,
   24, 55, 58, 05, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72,
   21, 36, 23,  9, 75, 00, 76, 44, 20, 45, 35, 14, 00, 61, 33, 97, 34, 31, 33, 95,
   78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 03, 80, 04, 62, 16, 14,  9, 53, 56, 92,
   16, 39, 05, 42, 96, 35, 31, 47, 55, 58, 88, 24, 00, 17, 54, 24, 36, 29, 85, 57,
   86, 56, 00, 48, 35, 71, 89, 07, 05, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58,
   19, 80, 81, 68, 05, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 04, 89, 55, 40,
   04, 52,  8, 83, 97, 35, 99, 16, 07, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66,
   88, 36, 68, 87, 57, 62, 20, 72, 03, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69,
   04, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18,  8, 46, 29, 32, 40, 62, 76, 36,
   20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 04, 36, 16,
   20, 73, 35, 29, 78, 31, 90, 01, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 05, 54,
   01, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 01, 89, 19, 67, 48
]

def valid(idx): 
  return 0 <= idx and idx < 20

def mat(coord): 
    j,k = coord
    if valid(j) and valid(k):
       return digits[20*j + k]
    else:
       return 0

def south(j, k):
    return [[j+d, k] for d in [0,1,2,3]]
def east(j, k):
    return [[j, k+d] for d in [0,1,2,3]]
def southeast(j, k):
    return [[j+d, k+d] for d in [0,1,2,3]]
def southwest(j, k):
    return [[j-d, k+d] for d in [0,1,2,3]]

def product(lst):
    return reduce(mul,lst)

def score(j,k):
    e =  product(map(mat, east(j,k)))
    se = product(map(mat, southeast(j,k)))
    s =  product(map(mat, south(j,k)))
    sw = product(map(mat, southwest(j,k)))
    return max(e, se, s, sw)

def solution():
    return max([score(j,k) for j in range(20) for k in range(20)])

if __name__ == "__main__":
    print(solution())

Problem 11 is to find the maximal product of four consecutive numbers in a 20x20 square grid of numbers. Consecutive here means contiguous in a row, column, or diagonal. The original description is available here.

The numbers are given to us as a one-dimensional list. The mat function provides the two dimensional indexing we need to simulate the 20x20 grid.

We traverse the grid, and at each cell [j k] compute the product of the four contiguous blocks:

Coordinates [j k] are oriented as follows:
[0 0] [0 1] —-> East
[1 0] [1 1]
|
|
v
South

In the original Project Euler version of the data, several of the numbers were written as 08 or 09. Python and Clojure treat leading zeros as indicating octal numbers, in which case neither 08 nor 09 is a valid number. I simply dropped the leading zero by hand editing the data; this does not change the spirit of the problem, nor the solution.

Problem 12

(ns org.drcabana.euler.p12
  (:use [org.drcabana.euler.p03 :only (prime-factors)]))

(defn tri [n]
  (/ (* n (inc n)) 2))

(defn count-divisors [n]
  (->> (prime-factors n)
       (partition-by identity)
       (map count)
       (map inc)
       (reduce *)))

(defn solve []
  (->> (iterate inc 1)
       (map tri)
       (drop-while #(< (count-divisors %) 500))
       first))

(defn -main []
  (println (solve)))
module p12
open System.Numerics

let tri (n : bigint ) = 
    n * (n+1I) / 2I

let partitionBy f xs =
    Seq.groupBy f xs |> Seq.map snd

let countDivisors n =
    p03.primeFactors(n)
    |> partitionBy (fun x -> x)
    |> Seq.map Seq.length
    |> Seq.map (fun x -> x + 1)
    |> Seq.reduce (*)

let solution =
    Seq.initInfinite (fun x -> 2I + (bigint x))
    |> Seq.map tri
    |> Seq.find (fun n -> countDivisors n > 500)

printfn "%A" solution

import P03 (pfactors)
import Data.List (group, find)

count_divisors n =
    product $ map (+ 1) multiplicities
    where factors = group $ pfactors 2 n
          multiplicities = map length factors

solve = find sufficient $ map tri [1..]
        where sufficient = \n -> count_divisors n > 500
              tri n = (n * (n+1)) `div` 2

main :: IO ()
main = print solve
from itertools import groupby
from operator import mul
from p03 import prime_factors

def tri():
  n = 2
  while True:
    yield (n * (n+1))/2
    n += 1

def count_divisors(n):
  pf = prime_factors(n)
  factors = [list(g) for k, g in groupby(pf)]
  multiplicities = map(len, factors)
  return reduce(mul, map(lambda x: x+1, multiplicities))

def solution():
  tn = tri()
  t = tn.next()
  while (count_divisors(t) < 501):
     t = tn.next()
  return t

if __name__ == "__main__":
    print(solution())

Problem 12 is to find the first triangle number with over five hundred divisors. Divisors are assumed to be positive. The original problem statement is available here.

We break this problem into two parts: how to compute triangle numbers, and how to count the divisors of integer.

The nth triangle number is the (inclusive) sum of the integers from 1 to n. The formula is well known, but worth explaining. Write the sum twice, but the second time write it in reverse order.

1 + 2 + … + n n + (n-1) + … + 1

Summing the n columns, each totals n+1. So twice the sum of 1…n is equal to n(n+1).

How many divisors does n have? Any divisor of n is the product of one or more prime factors of n. How many distinct such products are possible?

The simplest way to think about it is to from a product p1k1 p2k2 … pmkm where the p’s are the distinct prime factors of n, and the exponents vary from 0 to the multiplicity of the corresponding prime factor. For example, the prime factors of 12 are [2 2 3] so we can form products 2j * 3k where j varies from 0 to 2, and k varies from 0 to 1, hence 12 has 6=3*2 divisors, [1 2 3 4 6 12].

Problem 13

(ns org.drcabana.euler.p13)

(def numbers
  [37107287533902102798797998220837590246510135740250
   46376937677490009712648124896970078050417018260538
   74324986199524741059474233309513058123726617309629
   91942213363574161572522430563301811072406154908250
   23067588207539346171171980310421047513778063246676
   89261670696623633820136378418383684178734361726757
   28112879812849979408065481931592621691275889832738
   44274228917432520321923589422876796487670272189318
   47451445736001306439091167216856844588711603153276
   70386486105843025439939619828917593665686757934951
   62176457141856560629502157223196586755079324193331
   64906352462741904929101432445813822663347944758178
   92575867718337217661963751590579239728245598838407
   58203565325359399008402633568948830189458628227828
   80181199384826282014278194139940567587151170094390
   35398664372827112653829987240784473053190104293586
   86515506006295864861532075273371959191420517255829
   71693888707715466499115593487603532921714970056938
   54370070576826684624621495650076471787294438377604
   53282654108756828443191190634694037855217779295145
   36123272525000296071075082563815656710885258350721
   45876576172410976447339110607218265236877223636045
   17423706905851860660448207621209813287860733969412
   81142660418086830619328460811191061556940512689692
   51934325451728388641918047049293215058642563049483
   62467221648435076201727918039944693004732956340691
   15732444386908125794514089057706229429197107928209
   55037687525678773091862540744969844508330393682126
   18336384825330154686196124348767681297534375946515
   80386287592878490201521685554828717201219257766954
   78182833757993103614740356856449095527097864797581
   16726320100436897842553539920931837441497806860984
   48403098129077791799088218795327364475675590848030
   87086987551392711854517078544161852424320693150332
   59959406895756536782107074926966537676326235447210
   69793950679652694742597709739166693763042633987085
   41052684708299085211399427365734116182760315001271
   65378607361501080857009149939512557028198746004375
   35829035317434717326932123578154982629742552737307
   94953759765105305946966067683156574377167401875275
   88902802571733229619176668713819931811048770190271
   25267680276078003013678680992525463401061632866526
   36270218540497705585629946580636237993140746255962
   24074486908231174977792365466257246923322810917141
   91430288197103288597806669760892938638285025333403
   34413065578016127815921815005561868836468420090470
   23053081172816430487623791969842487255036638784583
   11487696932154902810424020138335124462181441773470
   63783299490636259666498587618221225225512486764533
   67720186971698544312419572409913959008952310058822
   95548255300263520781532296796249481641953868218774
   76085327132285723110424803456124867697064507995236
   37774242535411291684276865538926205024910326572967
   23701913275725675285653248258265463092207058596522
   29798860272258331913126375147341994889534765745501
   18495701454879288984856827726077713721403798879715
   38298203783031473527721580348144513491373226651381
   34829543829199918180278916522431027392251122869539
   40957953066405232632538044100059654939159879593635
   29746152185502371307642255121183693803580388584903
   41698116222072977186158236678424689157993532961922
   62467957194401269043877107275048102390895523597457
   23189706772547915061505504953922979530901129967519
   86188088225875314529584099251203829009407770775672
   11306739708304724483816533873502340845647058077308
   82959174767140363198008187129011875491310547126581
   97623331044818386269515456334926366572897563400500
   42846280183517070527831839425882145521227251250327
   55121603546981200581762165212827652751691296897789
   32238195734329339946437501907836945765883352399886
   75506164965184775180738168837861091527357929701337
   62177842752192623401942399639168044983993173312731
   32924185707147349566916674687634660915035914677504
   99518671430235219628894890102423325116913619626622
   73267460800591547471830798392868535206946944540724
   76841822524674417161514036427982273348055556214818
   97142617910342598647204516893989422179826088076852
   87783646182799346313767754307809363333018982642090
   10848802521674670883215120185883543223812876952786
   71329612474782464538636993009049310363619763878039
   62184073572399794223406235393808339651327408011116
   66627891981488087797941876876144230030984490851411
   60661826293682836764744779239180335110989069790714
   85786944089552990653640447425576083659976645795096
   66024396409905389607120198219976047599490197230297
   64913982680032973156037120041377903785566085089252
   16730939319872750275468906903707539413042652315011
   94809377245048795150954100921645863754710598436791
   78639167021187492431995700641917969777599028300699
   15368713711936614952811305876380278410754449733078
   40789923115535562561142322423255033685442488917353
   44889911501440648020369068063960672322193204149535
   41503128880339536053299340368006977710650566631954
   81234880673210146739058568557934581403627822703280
   82616570773948327592232845941706525094512325230608
   22918802058777319719839450180888072429661980811197
   77158542502016545090413245809786882778948721859617
   72107838435069186155435662884062257473692284509516
   20849603980134001723930671666823555245252804609722
   53503534226472524250874054075591789781264330331690])

(defn solve []
  (->> (reduce + numbers)       ;; sum the numbers 
       (str)                    ;; convert the sum to a string
       (take 10)                ;; take the first ten digits
       (apply str)))            ;; concat into a string

(defn -main []
  (println (solve)))
module p13

let numbers =
  [37107287533902102798797998220837590246510135740250I ;
   46376937677490009712648124896970078050417018260538I ;
   74324986199524741059474233309513058123726617309629I ;
   91942213363574161572522430563301811072406154908250I ;
   23067588207539346171171980310421047513778063246676I ;
   89261670696623633820136378418383684178734361726757I ;
   28112879812849979408065481931592621691275889832738I ;
   44274228917432520321923589422876796487670272189318I ;
   47451445736001306439091167216856844588711603153276I ;
   70386486105843025439939619828917593665686757934951I ;
   62176457141856560629502157223196586755079324193331I ;
   64906352462741904929101432445813822663347944758178I ;
   92575867718337217661963751590579239728245598838407I ;
   58203565325359399008402633568948830189458628227828I ;
   80181199384826282014278194139940567587151170094390I ;
   35398664372827112653829987240784473053190104293586I ;
   86515506006295864861532075273371959191420517255829I ;
   71693888707715466499115593487603532921714970056938I ;
   54370070576826684624621495650076471787294438377604I ;
   53282654108756828443191190634694037855217779295145I ;
   36123272525000296071075082563815656710885258350721I ;
   45876576172410976447339110607218265236877223636045I ;
   17423706905851860660448207621209813287860733969412I ;
   81142660418086830619328460811191061556940512689692I ;
   51934325451728388641918047049293215058642563049483I ;
   62467221648435076201727918039944693004732956340691I ;
   15732444386908125794514089057706229429197107928209I ;
   55037687525678773091862540744969844508330393682126I ;
   18336384825330154686196124348767681297534375946515I ;
   80386287592878490201521685554828717201219257766954I ;
   78182833757993103614740356856449095527097864797581I ;
   16726320100436897842553539920931837441497806860984I ;
   48403098129077791799088218795327364475675590848030I ;
   87086987551392711854517078544161852424320693150332I ;
   59959406895756536782107074926966537676326235447210I ;
   69793950679652694742597709739166693763042633987085I ;
   41052684708299085211399427365734116182760315001271I ;
   65378607361501080857009149939512557028198746004375I ;
   35829035317434717326932123578154982629742552737307I ;
   94953759765105305946966067683156574377167401875275I ;
   88902802571733229619176668713819931811048770190271I ;
   25267680276078003013678680992525463401061632866526I ;
   36270218540497705585629946580636237993140746255962I ;
   24074486908231174977792365466257246923322810917141I ;
   91430288197103288597806669760892938638285025333403I ;
   34413065578016127815921815005561868836468420090470I ;
   23053081172816430487623791969842487255036638784583I ;
   11487696932154902810424020138335124462181441773470I ;
   63783299490636259666498587618221225225512486764533I ;
   67720186971698544312419572409913959008952310058822I ;
   95548255300263520781532296796249481641953868218774I ;
   76085327132285723110424803456124867697064507995236I ;
   37774242535411291684276865538926205024910326572967I ;
   23701913275725675285653248258265463092207058596522I ;
   29798860272258331913126375147341994889534765745501I ;
   18495701454879288984856827726077713721403798879715I ;
   38298203783031473527721580348144513491373226651381I ;
   34829543829199918180278916522431027392251122869539I ;
   40957953066405232632538044100059654939159879593635I ;
   29746152185502371307642255121183693803580388584903I ;
   41698116222072977186158236678424689157993532961922I ;
   62467957194401269043877107275048102390895523597457I ;
   23189706772547915061505504953922979530901129967519I ;
   86188088225875314529584099251203829009407770775672I ;
   11306739708304724483816533873502340845647058077308I ;
   82959174767140363198008187129011875491310547126581I ;
   97623331044818386269515456334926366572897563400500I ;
   42846280183517070527831839425882145521227251250327I ;
   55121603546981200581762165212827652751691296897789I ;
   32238195734329339946437501907836945765883352399886I ;
   75506164965184775180738168837861091527357929701337I ;
   62177842752192623401942399639168044983993173312731I ;
   32924185707147349566916674687634660915035914677504I ;
   99518671430235219628894890102423325116913619626622I ;
   73267460800591547471830798392868535206946944540724I ;
   76841822524674417161514036427982273348055556214818I ;
   97142617910342598647204516893989422179826088076852I ;
   87783646182799346313767754307809363333018982642090I ;
   10848802521674670883215120185883543223812876952786I ;
   71329612474782464538636993009049310363619763878039I ;
   62184073572399794223406235393808339651327408011116I ;
   66627891981488087797941876876144230030984490851411I ;
   60661826293682836764744779239180335110989069790714I ;
   85786944089552990653640447425576083659976645795096I ;
   66024396409905389607120198219976047599490197230297I ;
   64913982680032973156037120041377903785566085089252I ;
   16730939319872750275468906903707539413042652315011I ;
   94809377245048795150954100921645863754710598436791I ;
   78639167021187492431995700641917969777599028300699I ;
   15368713711936614952811305876380278410754449733078I ;
   40789923115535562561142322423255033685442488917353I ;
   44889911501440648020369068063960672322193204149535I ;
   41503128880339536053299340368006977710650566631954I ;
   81234880673210146739058568557934581403627822703280I ;
   82616570773948327592232845941706525094512325230608I ;
   22918802058777319719839450180888072429661980811197I ;
   77158542502016545090413245809786882778948721859617I ;
   72107838435069186155435662884062257473692284509516I ;
   20849603980134001723930671666823555245252804609722I ;
   53503534226472524250874054075591789781264330331690I ]

let solution =
  let total = List.sum numbers |> string
  total.Substring(0,10)

printfn "%A" solution


numbers =
  [37107287533902102798797998220837590246510135740250,
   46376937677490009712648124896970078050417018260538,
   74324986199524741059474233309513058123726617309629,
   91942213363574161572522430563301811072406154908250,
   23067588207539346171171980310421047513778063246676,
   89261670696623633820136378418383684178734361726757,
   28112879812849979408065481931592621691275889832738,
   44274228917432520321923589422876796487670272189318,
   47451445736001306439091167216856844588711603153276,
   70386486105843025439939619828917593665686757934951,
   62176457141856560629502157223196586755079324193331,
   64906352462741904929101432445813822663347944758178,
   92575867718337217661963751590579239728245598838407,
   58203565325359399008402633568948830189458628227828,
   80181199384826282014278194139940567587151170094390,
   35398664372827112653829987240784473053190104293586,
   86515506006295864861532075273371959191420517255829,
   71693888707715466499115593487603532921714970056938,
   54370070576826684624621495650076471787294438377604,
   53282654108756828443191190634694037855217779295145,
   36123272525000296071075082563815656710885258350721,
   45876576172410976447339110607218265236877223636045,
   17423706905851860660448207621209813287860733969412,
   81142660418086830619328460811191061556940512689692,
   51934325451728388641918047049293215058642563049483,
   62467221648435076201727918039944693004732956340691,
   15732444386908125794514089057706229429197107928209,
   55037687525678773091862540744969844508330393682126,
   18336384825330154686196124348767681297534375946515,
   80386287592878490201521685554828717201219257766954,
   78182833757993103614740356856449095527097864797581,
   16726320100436897842553539920931837441497806860984,
   48403098129077791799088218795327364475675590848030,
   87086987551392711854517078544161852424320693150332,
   59959406895756536782107074926966537676326235447210,
   69793950679652694742597709739166693763042633987085,
   41052684708299085211399427365734116182760315001271,
   65378607361501080857009149939512557028198746004375,
   35829035317434717326932123578154982629742552737307,
   94953759765105305946966067683156574377167401875275,
   88902802571733229619176668713819931811048770190271,
   25267680276078003013678680992525463401061632866526,
   36270218540497705585629946580636237993140746255962,
   24074486908231174977792365466257246923322810917141,
   91430288197103288597806669760892938638285025333403,
   34413065578016127815921815005561868836468420090470,
   23053081172816430487623791969842487255036638784583,
   11487696932154902810424020138335124462181441773470,
   63783299490636259666498587618221225225512486764533,
   67720186971698544312419572409913959008952310058822,
   95548255300263520781532296796249481641953868218774,
   76085327132285723110424803456124867697064507995236,
   37774242535411291684276865538926205024910326572967,
   23701913275725675285653248258265463092207058596522,
   29798860272258331913126375147341994889534765745501,
   18495701454879288984856827726077713721403798879715,
   38298203783031473527721580348144513491373226651381,
   34829543829199918180278916522431027392251122869539,
   40957953066405232632538044100059654939159879593635,
   29746152185502371307642255121183693803580388584903,
   41698116222072977186158236678424689157993532961922,
   62467957194401269043877107275048102390895523597457,
   23189706772547915061505504953922979530901129967519,
   86188088225875314529584099251203829009407770775672,
   11306739708304724483816533873502340845647058077308,
   82959174767140363198008187129011875491310547126581,
   97623331044818386269515456334926366572897563400500,
   42846280183517070527831839425882145521227251250327,
   55121603546981200581762165212827652751691296897789,
   32238195734329339946437501907836945765883352399886,
   75506164965184775180738168837861091527357929701337,
   62177842752192623401942399639168044983993173312731,
   32924185707147349566916674687634660915035914677504,
   99518671430235219628894890102423325116913619626622,
   73267460800591547471830798392868535206946944540724,
   76841822524674417161514036427982273348055556214818,
   97142617910342598647204516893989422179826088076852,
   87783646182799346313767754307809363333018982642090,
   10848802521674670883215120185883543223812876952786,
   71329612474782464538636993009049310363619763878039,
   62184073572399794223406235393808339651327408011116,
   66627891981488087797941876876144230030984490851411,
   60661826293682836764744779239180335110989069790714,
   85786944089552990653640447425576083659976645795096,
   66024396409905389607120198219976047599490197230297,
   64913982680032973156037120041377903785566085089252,
   16730939319872750275468906903707539413042652315011,
   94809377245048795150954100921645863754710598436791,
   78639167021187492431995700641917969777599028300699,
   15368713711936614952811305876380278410754449733078,
   40789923115535562561142322423255033685442488917353,
   44889911501440648020369068063960672322193204149535,
   41503128880339536053299340368006977710650566631954,
   81234880673210146739058568557934581403627822703280,
   82616570773948327592232845941706525094512325230608,
   22918802058777319719839450180888072429661980811197,
   77158542502016545090413245809786882778948721859617,
   72107838435069186155435662884062257473692284509516,
   20849603980134001723930671666823555245252804609722,
   53503534226472524250874054075591789781264330331690]

solution = n    -- integers print nicely
           where num_str = take 10 $ show $ sum numbers
                 n = read num_str :: Integer

main = print solution

numbers = [
   37107287533902102798797998220837590246510135740250,
   46376937677490009712648124896970078050417018260538,
   74324986199524741059474233309513058123726617309629,
   91942213363574161572522430563301811072406154908250,
   23067588207539346171171980310421047513778063246676,
   89261670696623633820136378418383684178734361726757,
   28112879812849979408065481931592621691275889832738,
   44274228917432520321923589422876796487670272189318,
   47451445736001306439091167216856844588711603153276,
   70386486105843025439939619828917593665686757934951,
   62176457141856560629502157223196586755079324193331,
   64906352462741904929101432445813822663347944758178,
   92575867718337217661963751590579239728245598838407,
   58203565325359399008402633568948830189458628227828,
   80181199384826282014278194139940567587151170094390,
   35398664372827112653829987240784473053190104293586,
   86515506006295864861532075273371959191420517255829,
   71693888707715466499115593487603532921714970056938,
   54370070576826684624621495650076471787294438377604,
   53282654108756828443191190634694037855217779295145,
   36123272525000296071075082563815656710885258350721,
   45876576172410976447339110607218265236877223636045,
   17423706905851860660448207621209813287860733969412,
   81142660418086830619328460811191061556940512689692,
   51934325451728388641918047049293215058642563049483,
   62467221648435076201727918039944693004732956340691,
   15732444386908125794514089057706229429197107928209,
   55037687525678773091862540744969844508330393682126,
   18336384825330154686196124348767681297534375946515,
   80386287592878490201521685554828717201219257766954,
   78182833757993103614740356856449095527097864797581,
   16726320100436897842553539920931837441497806860984,
   48403098129077791799088218795327364475675590848030,
   87086987551392711854517078544161852424320693150332,
   59959406895756536782107074926966537676326235447210,
   69793950679652694742597709739166693763042633987085,
   41052684708299085211399427365734116182760315001271,
   65378607361501080857009149939512557028198746004375,
   35829035317434717326932123578154982629742552737307,
   94953759765105305946966067683156574377167401875275,
   88902802571733229619176668713819931811048770190271,
   25267680276078003013678680992525463401061632866526,
   36270218540497705585629946580636237993140746255962,
   24074486908231174977792365466257246923322810917141,
   91430288197103288597806669760892938638285025333403,
   34413065578016127815921815005561868836468420090470,
   23053081172816430487623791969842487255036638784583,
   11487696932154902810424020138335124462181441773470,
   63783299490636259666498587618221225225512486764533,
   67720186971698544312419572409913959008952310058822,
   95548255300263520781532296796249481641953868218774,
   76085327132285723110424803456124867697064507995236,
   37774242535411291684276865538926205024910326572967,
   23701913275725675285653248258265463092207058596522,
   29798860272258331913126375147341994889534765745501,
   18495701454879288984856827726077713721403798879715,
   38298203783031473527721580348144513491373226651381,
   34829543829199918180278916522431027392251122869539,
   40957953066405232632538044100059654939159879593635,
   29746152185502371307642255121183693803580388584903,
   41698116222072977186158236678424689157993532961922,
   62467957194401269043877107275048102390895523597457,
   23189706772547915061505504953922979530901129967519,
   86188088225875314529584099251203829009407770775672,
   11306739708304724483816533873502340845647058077308,
   82959174767140363198008187129011875491310547126581,
   97623331044818386269515456334926366572897563400500,
   42846280183517070527831839425882145521227251250327,
   55121603546981200581762165212827652751691296897789,
   32238195734329339946437501907836945765883352399886,
   75506164965184775180738168837861091527357929701337,
   62177842752192623401942399639168044983993173312731,
   32924185707147349566916674687634660915035914677504,
   99518671430235219628894890102423325116913619626622,
   73267460800591547471830798392868535206946944540724,
   76841822524674417161514036427982273348055556214818,
   97142617910342598647204516893989422179826088076852,
   87783646182799346313767754307809363333018982642090,
   10848802521674670883215120185883543223812876952786,
   71329612474782464538636993009049310363619763878039,
   62184073572399794223406235393808339651327408011116,
   66627891981488087797941876876144230030984490851411,
   60661826293682836764744779239180335110989069790714,
   85786944089552990653640447425576083659976645795096,
   66024396409905389607120198219976047599490197230297,
   64913982680032973156037120041377903785566085089252,
   16730939319872750275468906903707539413042652315011,
   94809377245048795150954100921645863754710598436791,
   78639167021187492431995700641917969777599028300699,
   15368713711936614952811305876380278410754449733078,
   40789923115535562561142322423255033685442488917353,
   44889911501440648020369068063960672322193204149535,
   41503128880339536053299340368006977710650566631954,
   81234880673210146739058568557934581403627822703280,
   82616570773948327592232845941706525094512325230608,
   22918802058777319719839450180888072429661980811197,
   77158542502016545090413245809786882778948721859617,
   72107838435069186155435662884062257473692284509516,
   20849603980134001723930671666823555245252804609722,
   53503534226472524250874054075591789781264330331690]

def solution():
    total = sum(numbers)
    return str(total)[0:10]

if __name__ == "__main__":
    print(solution())

Problem 13 is to find the first ten digits of the sum of 100 50-digit numbers. The original problem statement is available here

Problem 14

(ns org.drcabana.euler.p14)

(defn collatz [n]
  (if (even? n)
    (/ n 2)
    (+ (* 3 n) 1)))

(defn collatz-seq [n]
  (iterate collatz n))

(def collatz-length
  (memoize (fn [n] 
    (count (take-while #(< 1 %) 
                       (collatz-seq n))))))

(defn solve []
  (->> (range 1 1000000)
       (map #(vector % (collatz-length %)))
       (sort-by second)
       (last)    ;; grab last pair, then 1st element of that pair
       (first)))

(defn -main []
  (println (solve)))
module p14

let collatz n = 
    let rec collatz n total =
      let total = total + 1L
      match n with
          | 1L -> total
          | _ when n % 2L = 0L -> collatz (n/2L) total
          | _ -> collatz ((3L*n)+1L) total
    collatz n 0L

let solution k = 
    [for n in 1L..k -> (collatz n, n)]
    |> List.max
    |> snd

printfn "%A" <| solution 999999L
import Data.MemoTrie

-- Recursion and memoization play well together, it's crazy.
collatz :: Int -> Int
collatz = memo coll
  where coll n
          | n == 1         = 1
          | n `rem` 2 == 0 = 1 + collatz (n `quot` 2)
          | otherwise      = 1 + collatz (3*n + 1)

solve = snd $ maximum [(collatz n, n) | n <- [1..999999]]
main = print solve
import qualified Data.Map as M
import Data.List
import Data.Ord

colstep x = 
    if x `rem` 2 == 0
       then x `div` 2 
       else x*3 + 1

collatzMap :: M.Map Integer Integer

collatzMap = M.fromAscList [(i, collatz i) | i <- [1..limit]]
  where limit = 10000
        collatz 1 = 1
        collatz x = if y <= limit  
                       then 1 + collatzMap M.! y
                       else 1 + collatz y
          where y = colstep x

solve = fst $ maximumBy (comparing snd) $ M.toList collatzMap

main = print solve
def colstep(x): 
  if x % 2 == 0:
    return x//2 
  else:
    return x*3 + 1

def collatz(n):
  k = 1
  while (n != 1):
      k += 1
      n = colstep(n)
  return k

def solution(limit):
  return max([[collatz(n),n] for n in range(1,limit)])

if __name__ == "__main__":
    print(solution(1000000))

Problem 14 is to find the positive integer less than one million with the largest Collatz length. The original problem statement is available here.

It is conjectured that for any positive N, C(N) is eventually 1. According to the Wikipedia, the conjecture has been tested out to N = 20 * 2^58.

Problem 15

(ns org.drcabana.euler.p15)

(defn choose [n k]
  (let [u (range (inc k) (inc n))
        v (range 1 (inc (- n k)))]
   (/ (reduce *' u)
      (reduce *' v))))

(defn solve []
  (choose 40 20))

(defn -main []
  (println (solve)))
module p15

open System.Numerics

let prod (x:int, y:int) : BigInteger =
    Seq.reduce (*) [bigint x .. bigint y]

let choose n k = 
   prod (k+1, n) / prod (1, n-k)

let solution = choose 40 20
printfn "%A" solution
choose n k = product [k+1..n] `div` product [1..n-k]
solution = choose 40 20

main = print solution

from operator import mul

def choose(n,k):
    u = reduce(mul, range(1+k, 1+n))
    v = reduce(mul, range(1, 1+n-k))
    return u//v

def solution():
    return choose(40,20)

if __name__ == "__main__":
    print(solution())

In problem 15 we consider a 20 by 20 rectangular grid. Starting at the top left corner, on any move we can move down or right. The question is how many distinct paths to the bottom right there are. The original problem statement is available here.

There’s not much to this one. To get to the bottom right we must make 40 moves: 20 downwards, and 20 to the right. Imagine we have 40 slots numbered 1 to 40. Once you have assigned the 20 downward moves to their slots, there is no choice about where to put the rightward moves. So the question is how many ways can you choose 20 slots from 40.

The answer is well known: the number of ways to choose K elements from N is C(N, K) = N!/(K! * (N-K)!). Simple computing the factorials and dividing as written does more work than is necessary. The solutions factor out K! from both the numerator and denominator.

Problem 16


(ns org.drcabana.euler.p16
  (:use [clojure.math.numeric-tower :only (expt)]))

(defn digits [n]
  (letfn [(char-to-int [c] (Integer. (str c))) ]
    (map char-to-int (str n))))

(defn solve []
  (reduce + (digits (expt 2 1000))))

(defn -main []
  (println (solve)))
module p16

let solution =
  [for c in string (pown 2I 1000) -> string c]
  |> List.map System.Int32.Parse  
  |> List.sum 

printfn "%d" solution

module P16

import Data.Char (digitToInt)

solution = sum $ digits $ 2^1000
  where digits = map digitToInt . show

main = print solution

def solution():
    return sum([int(d) for d in str(2 ** 1000)])

if __name__ == "__main__":
    print(solution())

Problem 16 is to sum the decimal digits of 2**1000. The original problem statement is available here.

Problem 17

(ns org.drcabana.euler.p17)

(def word-for
  {1 "one",        2 "two",        3 "three",
   4 "four",       5 "five",       6 "six",
   7 "seven",      8 "eight",      9 "nine",
   10 "ten",      11 "eleven",    12 "twelve",
   13 "thirteen", 14 "fourteen",  15 "fifteen",
   16 "sixteen",  17 "seventeen", 18 "eighteen",
   19 "nineteen", 20 "twenty",    30 "thirty",
   40 "forty",    50 "fifty",     60 "sixty",
   70 "seventy",  80 "eighty",    90 "ninety" })

;; The functions 'name-of' and 'three-digit-name' call one another. 
;; We get around the forward reference by declaring one of them.
(declare name-of)

(defn two-digit-name [n]
  (let [low  (rem n 10)
        high (- n low) ]
    (str (word-for high) (word-for low))))

(defn three-digit-name [n]
  (let [high (quot n 100)
        low  (rem  n 100)]
    (if (zero? low)
      (str (word-for high) "hundred" )
      (str (word-for high) "hundredand" (name-of low)))))

(defn name-of [n]
  (cond
   (< n 20)   (word-for n)
   (< n 100)  (two-digit-name n)
   (< n 1000) (three-digit-name n)
   (= n 1000) "onethousand"))

(defn solve []
  (->> (range 1 1001)
       (map name-of)
       (map #(.length %))
       (reduce + )))

(defn -main []
  (println (solve)))
module p17

let numberNames =
  [ (0 , "");         
    (1 , "one");       (2 , "two");        (3 , "three");
    (4 , "four");      (5 , "five");       (6 , "six");
    (7 , "seven");     (8 , "eight");      (9 , "nine");
    (10 , "ten");      (11 , "eleven");    (12 , "twelve");
    (13 , "thirteen"); (14 , "fourteen");  (15 , "fifteen");
    (16 , "sixteen");  (17 , "seventeen"); (18 , "eighteen");
    (19 , "nineteen"); (20 , "twenty");    (30 , "thirty");
    (40 , "forty");    (50 , "fifty");     (60 , "sixty");
    (70 , "seventy");  (80 , "eighty");    (90 , "ninety") ]

let wordFor = Map.ofList numberNames

let grab n = 
  match Map.tryFind n wordFor with
    | None -> ""
    | Some x -> x

let twoDigitName n =
  let low = n % 10
  let high = n - low 
  grab high + grab low

let rec threeDigitName n = 
    let high = n / 100
    let low = n % 100
    if low = 0 
        then grab high + "hundred"
        else grab high + "hundredand" + nameOf low        
and nameOf n =
  if n < 20 then grab n
  elif n < 100 then twoDigitName n
  elif n < 1000 then threeDigitName n
  else "onethousand"

let solution = 
    [1 .. 1000]
    |> List.map nameOf
    |> List.map String.length
    |> List.sum

printfn "%A" solution
import Prelude hiding (lookup)
import qualified Data.Map as Map

numberNames =  
  [ (0 , ""),           
    (1 , "one"),       (2 , "two"),        (3 , "three"),
    (4 , "four"),      (5 , "five"),       (6 , "six"),
    (7 , "seven"),     (8 , "eight"),      (9 , "nine"),
    (10 , "ten"),      (11 , "eleven"),    (12 , "twelve"),
    (13 , "thirteen"), (14 , "fourteen"),  (15 , "fifteen"),
    (16 , "sixteen"),  (17 , "seventeen"),  (18 , "eighteen"),
    (19 , "nineteen"), (20 , "twenty"),    (30 , "thirty"),
    (40 , "forty"),    (50 , "fifty"),     (60 , "sixty"),
    (70 , "seventy"),  (80 , "eighty"),    (90 , "ninety") 
  ]

wordFor = Map.fromList numberNames

grab n = 
  case Map.lookup n wordFor of
    Nothing -> ""
    Just x -> x

twoDigitName n = do
  grab high ++ grab low
  where low = n `mod` 10
        high = n - low

threeDigitName n = do
    if low == 0 
        then grab high ++ "hundred"
        else grab high ++ "hundredand" ++ nameOf low
    where high = n `div` 100
          low =  n `mod` 100

nameOf n
  | n < 20 = grab n
  | n < 100 =  twoDigitName n
  | n < 1000 = threeDigitName n
  | otherwise = "onethousand"

solve = 
    sum $ map length names
    where  names = map nameOf [1..1000]


main :: IO ()
main = print solve

word_for =  {
    0 : "",           
    1 : "one",       2 : "two",        3 : "three",
    4 : "four",      5 : "five",       6 : "six",
    7 : "seven",     8 : "eight",      9 : "nine",
   10 : "ten",      11 : "eleven",    12 : "twelve",
   13 : "thirteen", 14 : "fourteen",  15 : "fifteen",
   16 : "sixteen",  17 : "seventeen", 18 : "eighteen",
   19 : "nineteen", 20 : "twenty",    30 : "thirty",
   40 : "forty",    50 : "fifty",     60 : "sixty",
   70 : "seventy",  80 : "eighty",    90 : "ninety" 
}

def two_digit_name(n):
    low = n % 10
    high = n - low
    return word_for[high] + word_for[low]

def three_digit_name(n):
    high = n // 100
    low =  n % 100
    if low == 0:
        return word_for[high] + "hundred"
    else:
        return word_for[high] + "hundredand" + name_of(low)

def name_of(n):
  if n < 20:
      return word_for[n]
  elif n < 100:
      return two_digit_name(n)
  elif n < 1000:
      return three_digit_name(n)
  elif n == 1000:
      return "onethousand"
  else:
      none

def solution():
    names = map(name_of, range(1,1001))
    return sum(map(len, names))

if __name__ == "__main__":
    print(solution())

Problem 17 is as follows. If the numbers 1 to 5 are written out in words (one, two, three, four, five) then there are 3 + 3 + 5 + 4 + 4 = 19 letters used. If all the numbers from 1 to 1000 were written out in words, how many letters would be used?

Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The original problem statement is available here.

Problem 18

(ns org.drcabana.euler.p18
  (use [clojure.string :only (split-lines)]))

(def data-string
  "75
   95  64
   17  47  82
   18  35  87  10
   20  04  82  47  65
   19  01  23  75  03  34
   88  02  77  73  07  63  67
   99  65  04  28  06  16  70  92
   41  41  26  56  83  40  80  70  33
   41  48  72  33  47  32  37  16  94  29
   53  71  44  65  25  43  91  52  97  51  14
   70  11  33  28  77  73  17  78  39  68  17  57
   91  71  52  38  17  14  91  43  58  50  27  29  48
   63  66  04  68  89  53  67  30  73  16  69  87  40  31
   04  62  98  27  23  09  70  98  73  93  38  53  60  04  23")

(defn split-into-nums
  [string]
  (->> string
       (re-seq #"\d+")
       (map #(Integer. %))))

(def triangle
  (map split-into-nums (split-lines data-string)))

(defn maximize [row]
  (letfn [(pair-max [[a b]] (max a b))]
    (map pair-max (partition 2 1 row))))

(defn merge-rows [row1 row2]
  (map + (maximize row1) row2))

(defn solve []
  (first (reduce merge-rows (reverse triangle))))

(defn -main []
  (println (solve)))
module p18

let dataString =   
  "75
   95  64
   17  47  82
   18  35  87  10
   20  04  82  47  65
   19  01  23  75  03  34
   88  02  77  73  07  63  67
   99  65  04  28  06  16  70  92
   41  41  26  56  83  40  80  70  33
   41  48  72  33  47  32  37  16  94  29
   53  71  44  65  25  43  91  52  97  51  14
   70  11  33  28  77  73  17  78  39  68  17  57
   91  71  52  38  17  14  91  43  58  50  27  29  48
   63  66  04  68  89  53  67  30  73  16  69  87  40  31
   04  62  98  27  23  09  70  98  73  93  38  53  60  04  23"

let lines (s : string) = s.Split([|'\n'|])

// Split string s on whitespace into an array of strings
let split (s : string)  =
    let whitespace = " \t\r".ToCharArray()
    s.Split(whitespace, System.StringSplitOptions.RemoveEmptyEntries)

// Convert array of strings to array of ints
let asInts (s : string[]) = Array.map int s

let triangle =
    dataString
    |> lines
    |> Array.map split
    |> Array.map asInts

let maximize row =
    row
    |> Seq.pairwise
    |> Seq.map (fun (a,b) -> max a b)
    |> Array.ofSeq

let merge row1 row2  =
    Array.map2 (+) (maximize row1) row2

let solution = 
   triangle
   |> Array.rev
   |> Array.reduce merge
   |> Array.get <| 0

printfn "%A" solution
import Data.List (lines, foldl')

dataString =   
  "75 \n\
  \95  64 \n\ 
  \17  47  82 \n\
  \18  35  87  10 \n\
  \20  04  82  47  65 \n\
  \19  01  23  75  03  34 \n\
  \88  02  77  73  07  63  67 \n\
  \99  65  04  28  06  16  70  92 \n\
  \41  41  26  56  83  40  80  70  33 \n\
  \41  48  72  33  47  32  37  16  94  29 \n\
  \53  71  44  65  25  43  91  52  97  51  14 \n\
  \70  11  33  28  77  73  17  78  39  68  17  57 \n\ 
  \91  71  52  38  17  14  91  43  58  50  27  29  48 \n\
  \63  66  04  68  89  53  67  30  73  16  69  87  40  31 \n\
  \04  62  98  27  23  09  70  98  73  93  38  53  60  04  23"

triangle = 
    [map toInt (words ln) | ln <- lines dataString]
    where toInt str = read str :: Integer

maximize row =
    map (\(a, b) -> max a b) $ pairwise row
    where pairwise xs = zip xs (tail xs)

merge [] row1 = row1
merge row1 row2 = 
    zipWith (+) (maximize row1) row2

solution = 
    head (foldl' merge [] $ reverse triangle)  

main = print $ solution

data = """75
          95  64
          17  47  82
          18  35  87  10
          20  04  82  47  65
          19  01  23  75  03  34
          88  02  77  73  07  63  67
          99  65  04  28  06  16  70  92
          41  41  26  56  83  40  80  70  33
          41  48  72  33  47  32  37  16  94  29
          53  71  44  65  25  43  91  52  97  51  14
          70  11  33  28  77  73  17  78  39  68  17  57
          91  71  52  38  17  14  91  43  58  50  27  29  48
          63  66  04  68  89  53  67  30  73  16  69  87  40  31
          04  62  98  27  23  09  70  98  73  93  38  53  60  04  23"""

lines = [line.strip().split() for line in data.split("\n")]
triangle = [map(int, line) for line in lines]

def pairwise(row):
    return zip(row, row[1:])

def maximize(row):
    return map(lambda (a,b): max(a,b), pairwise(row))

def merge(row1, row2):
    return [a+b for a,b in zip(maximize(row1), row2)] 

def solution():
    tri = list(reversed(triangle)) 
    return reduce(merge, tri)[0]

if __name__ == "__main__":
    print(solution())

Problem 18: Start at the top of the triangle, move to an adjacent number on the row below, continuing this way to construct a path to the bottom. Consider the sum of the integers along the path. What is the maximal sum that can be constructed? The original problem statement is available here.

Problem 19

(ns org.drcabana.euler.p19)

(defn solve []
  (let [year (mapcat #(range 1 (inc %))
                     [31 28 31 30 31 30 31 31 30 31 30 31])

        leap-year (mapcat #(range 1 (inc %))
                          [31 29 31 30 31 30 31 31 30 31 30 31])

        days-per-century (+ (* 25 366) (* 75 365)) ;; 25 leap years, 75 std years       
        days-of-week (cycle [:tue :wed :thu :fri :sat :sun :mon])     ;; 1/1/1901 was a Tuesday
        dates (cycle (concat year year year leap-year))]              ;; 1904 was a leap year]

    (->> (map vector dates days-of-week)
         (take days-per-century)
         (filter #(= %1 [1 :sun]))
         (count))))

(defn -main []
  (println (solve)))
module p19

let cycle xs =
    Seq.initInfinite (fun _ -> xs) |> Seq.concat

let year =
    List.concat [[1..31];[1..28];[1..31];[1..30];[1..31];[1..30];
                 [1..31];[1..31];[1..30];[1..31];[1..30];[1..31]]

let leapYear =
    List.concat [[1..31];[1..29];[1..31];[1..30];[1..31];[1..30];
                 [1..31];[1..31];[1..30];[1..31];[1..30];[1..31]]

let dates =
    [year; year; year; leapYear] |> List.concat |> cycle 

let daysOfWeek =
    cycle ["Tu" ; "W" ; "Th" ; "F" ; "Sa" ; "Su" ; "M"]

let solution =
    let daysInCentury = 25 * (366 + 365 + 365 + 365)
    Seq.zip dates daysOfWeek
    |> Seq.take daysInCentury
    |> Seq.filter (fun x -> x = (1, "Su"))
    |> Seq.length

printfn "%A" solution
year =
    concat [[1..31],[1..28],[1..31],[1..30],[1..31],[1..30],
            [1..31],[1..31],[1..30],[1..31],[1..30],[1..31]]

leapYear =
    concat [[1..31],[1..29],[1..31],[1..30],[1..31],[1..30],
            [1..31],[1..31],[1..30],[1..31],[1..30],[1..31]]

dates =
    cycle $ concat [year, year, year, leapYear]

daysOfWeek =
    cycle ["Tu", "W", "Th", "F", "Sa", "Su", "M"]

solution =
    length $ filter ((1, "Su") ==) $ take daysInCentury $ zip dates daysOfWeek
    where daysInCentury = 25 * (366 + 365 + 365 + 365)

main = print solution

from itertools import cycle, izip, islice

m28 = range(1,29)
m29 = range(1,30)
m30 = range(1,31)
m31 = range(1,32)

year = m31 + m28 + m31 + m30 + m31 + m30 + \
       m31 + m31 + m30 + m31 + m30 + m31

leapYear = m31 + m29 + m31 + m30 + m31 + m30 + \
           m31 + m31 + m30 + m31 + m30 + m31

dates = cycle(year + year + year + leapYear)

daysOfWeek = cycle(["Tu", "W", "Th", "F", "Sa", "Su", "M"])

def solution():
    daysInCentury = 25 * (366 + 365 + 365 + 365)
    sundayIsFirst = lambda (n,day): (1,"Su")==(n,day)
    epoch = islice(izip(dates,daysOfWeek), 0, daysInCentury)
    return len(filter(sundayIsFirst, epoch))

if __name__ == "__main__":
    print(solution())

Problem 19: how many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)? The original problem statement is available here.

The solution is beautifully mechanical. We construct two sequences: one of calendar dates, and one of weekdays. Both sequences cycle endlessly. We take a century’s worth of elements from each sequence, pair up corresponding elements, filter out the pairs which satisfy our criteria, and count how many did so.

Problem 20

(ns org.drcabana.euler.p20)

(defn solve []
  (->> (reduce *' (range 1 101)) ;; use of *' avoids overflow
       (str)                     ;; convert to string
       (map #(Integer. (str %))) ;; convert each digit to an integer
       (reduce +)))

(defn -main []
  (println (solve)))
module p20

open System.Numerics

let digitsOf (x : BigInteger) =
    string x |> Seq.map (string >> int)

let solution =
    List.reduce (*) [2I .. 100I]
    |> digitsOf
    |> Seq.sum

printfn "%A" solution
import Data.Char (digitToInt)

solution = sum $ digits $ product [2..100]
  where digits = map digitToInt . show

main = print solution


from operator import mul

def digitsOf(n):
    return map(int, map(str, str(n)))

def solution():
    prod = reduce(mul, (range(2,101)))
    return sum(digitsOf(prod))

if __name__ == "__main__":
    print(solution())

Problem 20 is to find the sum of the digits in the number 100!. The original problem statement is available here.

Problem 21

(ns org.drcabana.euler.p21)

(defn divisors
  ([n d] (when (zero? (rem n d)) [d (quot n d)] ))
  ([n] (let [upperlim (inc (int (Math/sqrt n)))]
    (into #{} (mapcat #(divisors n %) (range 1 upperlim))))) )

(defn sum-of-divisors
  [n]
  (reduce + (divisors n)))

(defn amicable?
  [n]
  (let [m  (- (sum-of-divisors n) n)
        k  (- (sum-of-divisors m) m)]
    (and (= n k)
         (not= n m))))

(defn solve []
  (reduce + (filter amicable? (range 1 10000))))

(defn -main []
  (println (solve)))
module p21

let divisorOf n d = 
    0 = n % d 

let divisors n =
    let limit = double n |> sqrt |> ceil |> int
    let lowdivs = List.filter (divisorOf n) [1..limit]
    let highdivs = [for d in lowdivs -> n / d ]
    let alldivs = set <| List.append lowdivs highdivs
    let properdivs = Set.difference alldivs <| set [n]
    [for d in properdivs -> d]

let amicable n =
    let m = List.sum <| divisors n
    let k = List.sum <| divisors m
    n = k && n <> m

let solution = 
    [1..9999]
    |> Seq.filter amicable
    |> Seq.sum

printfn "%A" solution
module P21 where

import Data.Set (fromList, toList, (\\))
set  = Data.Set.fromList
list = Data.Set.toList 

-- We exclude n but include 1
divisors n =
    list $ alldivs \\ set[n]
    where limit = ceiling $ sqrt $ fromIntegral n
          lowdivs = filter (divisorOf n) [1..limit]
          highdivs = [div n d | d <- lowdivs]
          alldivs = set $ lowdivs ++ highdivs
          divisorOf n d = 0 == n `mod` d 

amicable n = 
    n == k && n /= m
    where m = sum $ divisors n
          k = sum $ divisors m

solution = sum $ filter amicable [1..9999]
main = print $ solution

import math

def divisors(n):
    limit = int(math.ceil(math.sqrt(n)))
    lowdivs = filter(lambda x: n%x==0, range(1, limit+1))
    highdivs = [n/d for d in lowdivs]
    alldivs = set(lowdivs + highdivs)
    properdivs = alldivs.difference(set([n]))
    return list(properdivs)

def amicable(n):
    m = sum(divisors(n))
    k = sum(divisors(m))
    return n == k and n != m

def solution():
    return sum(filter(amicable, range(1,10000)))

if __name__ == "__main__":
    print(solution())

Define d(n) as the sum of the proper divisors of n. If d(a) = b and d(b) = a, where a != b, then a and b are called amicable numbers. Sum the amicable numbers less than 10000. The original problem statement is available here.

Problem 22

(ns org.drcabana.euler.p22)

(defn solve []
  (let [alpha  (seq "ABCDEFGHIJKLMNOPQRSTUVWXYZ")
        points (zipmap alpha (iterate inc 1))
        score  (fn [name]
                 (reduce + (map points name)))
        names  (->> (slurp "/home/drc/code/ec/data/names.txt")
                    (re-seq #"[A-Z]+" )
                    (sort))
        scores (map score names)]
    (reduce + (map * scores (iterate inc 1)))))

(defn -main []
  (println (solve)))
module p22

open System.IO

let split (s : string)  =
    let comma = ",".ToCharArray()
    s.Split(comma, System.StringSplitOptions.RemoveEmptyEntries)

let names = 
    @"C:\data\euler-fp\names.txt"
    |> File.ReadAllText
    |> split
    |> Array.sort

let points c = 
    let alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    let vals = Seq.zip alpha [1..26] |> Map.ofSeq
    match Map.tryFind c vals with
    | None -> 0
    | Some x -> x

let score word  =
    Seq.map points word
    |> Seq.reduce (+)

let solution =
    let scores = Array.map score names
    Seq.map2 (*) scores [1 .. Array.length scores]
    |> Seq.sum

printfn "%A" solution
import Prelude hiding (lookup)
import Data.Map (lookup, fromList)
import Data.List.Split (splitOn) 
import Data.List (sort)

points c = 
  case lookup c vals of
    Nothing -> 0
    Just x -> x
  where alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        vals = fromList $ zip alpha [1..]

score word  =
    sum $ map points word

main = do  
        text <- readFile "/home/drc/code/euler-fp/data/names.txt"
        let scores = map score $ sort $ splitOn "," text
        print $ sum [a*b | (a,b) <- zip scores [1..]]



pts = dict(zip("ABCDEFGHIJKLMNOPQRSTUVWXYZ", range(1,27)))

def points(c):
    return pts.get(c,0)

def score(word):
    return sum(map(points, word))

def solution():
    filename = "../../data/names.txt"
    text = open(filename, 'r').read()
    names = sorted(text.split(","))
    scores = map(score, names)
    return sum( (k+1) * scores[k] for k in range(0, len(scores)))

if __name__ == "__main__":
    print(solution())

Using names.txt, a 46K text file containing over five thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714. What is the total of all the name scores in the file? The original problem statement is available here.

Problem 23

(ns org.drcabana.euler.p23
  (:use [org.drcabana.euler.p21 :only (divisors)]))

(defn abundant? [n]
  (let [divs (divisors n)
        sum-divs (fn [k] (- (reduce + divs) k))]
    (> (sum-divs n) n)))

;;The constant 28123 is stipulated by the problem.  
(def limit (inc 28123))
(def abundants (vec (filter abundant? (range 1 limit))))

(def sums-of-abundants
  (into #{}
        (for [a abundants 
              b abundants 
              :when (<= a b) :when (< (+ a b) limit)]
          (+ a b))))

(defn solve []
  (let [s (reduce + (range 1 limit))
        t (reduce + sums-of-abundants)]
    (- s t)))

(defn -main []
  (println (solve)))
module p23
open p21

let abundant n =
   let divs = divisors n
   n < List.sum divs

let limit = 28123  
let abundants = List.filter abundant [1..limit]

let sumsOfAbundants =
    seq {for a in abundants do
         for b in abundants do 
         if (b >= a) && (b <= limit - a) then yield a+b}
    |> Seq.distinct

let solution =
   let s = List.sum [1..limit]
   let t = Seq.sum sumsOfAbundants
   s - t

printfn "%A" solution
import Data.Set (fromList, toList)
import P21 (divisors)

-- Find the distinct elts of a list by converting the
-- list to a set, then converting the set back to a list.
distinct = toList . fromList

abundant n =
   sum divs > n
   where divs = divisors n

limit = 28123  -- constant given in problem stmt
abundants = filter abundant [1..limit]

sumsOfAbundants =
    distinct [a+b | a <- abundants, 
                    b <- abundants,
                    b >= a,
                    b <= limit - a]

solution = s - t
  where s = sum [1..limit]
        t = sum sumsOfAbundants

main = print solution
from p21 import divisors

def abundant(n):
   return n < sum(divisors(n))

limit = 28123  
abundants = filter(abundant, range(1, limit+1))

def sumsOfAbundants():
    sums = [a+b for a in abundants
                for b in abundants
                if (b >= a) and (b <= limit - a)]
    return list(set(sums))

def solution():
   s = sum(range(1, limit+1))
   t = sum(sumsOfAbundants())
   return s - t

if __name__ == "__main__":
    print(solution())

A positive integer n is abundant if the sum of its proper divisors exceeds n. It can be proven that every integer greater than 28123 is the sum of two abundant numbers. Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers. The original problem statement is available here.

Problem 24

(ns org.drcabana.euler.p24)

(defn perms []
  (let [symbols (map str (range 10))]
    (for [a symbols
          b symbols :when (nil? (#{a} b ))
          c symbols :when (nil? (#{a b} c))
          d symbols :when (nil? (#{a b c} d))
          e symbols :when (nil? (#{a b c d} e))
          f symbols :when (nil? (#{a b c d e} f))
          g symbols :when (nil? (#{a b c d e f} g))
          h symbols :when (nil? (#{a b c d e f g} h))
          i symbols :when (nil? (#{a b c d e f g h} i))
          j symbols :when (nil? (#{a b c d e f g h i} j))]
      [a b c d e f g h i j])))

(defn solve []
  (apply str (nth (perms) 999999)))

(defn -main []
  (println (solve)))
module p24

let solution =
    let symbols = set [0..9]
    seq {for a in symbols do
         for b in Set.difference symbols (set [a]) do
         for c in Set.difference symbols (set [a;b]) do
         for d in Set.difference symbols (set [a;b;c]) do
         for e in Set.difference symbols (set [a;b;c;d]) do
         for f in Set.difference symbols (set [a;b;c;d;e]) do
         for g in Set.difference symbols (set [a;b;c;d;e;f]) do
         for h in Set.difference symbols (set [a;b;c;d;e;f;g]) do
         for i in Set.difference symbols (set [a;b;c;d;e;f;g;h]) do
         for j in Set.difference symbols (set [a;b;c;d;e;f;g;h;i]) ->
         [a;b;c;d;e;f;g;h;i;j] }
    |> Seq.nth 999999
    |> List.map string
    |> String.concat ""

printfn "%A" solution
import Data.Set (fromList, toList, (\\))

set  = Data.Set.fromList
list = Data.Set.toList 
symbols = set [0..9]

perms = [ [a,b,c,d,e,f,g,h,i,j] |
          a <- list symbols,
          b <- list $ symbols \\ set [a],
          c <- list $ symbols \\ set [a,b],
          d <- list $ symbols \\ set [a,b,c],
          e <- list $ symbols \\ set [a,b,c,d],
          f <- list $ symbols \\ set [a,b,c,d,e],
          g <- list $ symbols \\ set [a,b,c,d,e,f],
          h <- list $ symbols \\ set [a,b,c,d,e,f,g],
          i <- list $ symbols \\ set [a,b,c,d,e,f,g,h],
          j <- list $ symbols \\ set [a,b,c,d,e,f,g,h,i] ]  

solution =
    concat $ Prelude.map show p
    where p = perms !! 999999

main = print solution

def solution():
    symbols = set(range(10))
    perms = [ [a,b,c,d,e,f,g,h,i,j]
              for a in symbols
              for b in symbols.difference(set([a]))
              for c in symbols.difference(set([a,b]))
              for d in symbols.difference(set([a,b,c]))
              for e in symbols.difference(set([a,b,c,d]))
              for f in symbols.difference(set([a,b,c,d,e]))
              for g in symbols.difference(set([a,b,c,d,e,f]))
              for h in symbols.difference(set([a,b,c,d,e,f,g]))
              for i in symbols.difference(set([a,b,c,d,e,f,g,h]))
              for j in symbols.difference(set([a,b,c,d,e,f,g,h,i])) ]
    return ''.join(map(str,perms[999999]))

if __name__ == "__main__":
    print(solution())

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9? The original problem statement is available here.

We’ll use brute force and set differences. This approach is not particularly fast, but it gets the job done here and in a wide variety of problems.

The Haskell and F# solutions of problem 32 will include a faster and more refined way to generate permutations.

Problem 25

(ns org.drcabana.euler.p25
  (:use [clojure.math.numeric-tower :only (expt)]
        [org.drcabana.euler.p02  :only (fibonacci)]))

(defn solve []
  (let [limit (expt 10 999)
        too-small? #(< % limit)]
    (->> (fibonacci)
         (take-while too-small?)
         (count))))

(defn -main []
  (println (solve)))
module p25

open System.Numerics

let fibonacci (a:bigint, b:bigint) = 
    Some(a, (b, a + b))

let solution =
    let limit = BigInteger.Pow(10I, 999)
    Seq.unfold fibonacci (0I, 1I)
    |> Seq.takeWhile (fun n -> n < limit)
    |> Seq.length 

printfn "%A" solution

// Rewrote fibonacci rather than import it from p02 in order
// to use bigints. The p02 version used ints.
import P02 (fibonacci)

solution =
    length $ takeWhile (< limit) fibonacci
    where limit = 10^999

main = print solution

from itertools import takewhile
from p02 import fibonacci

def solution():
    limit = 10**999
    return len(list(takewhile(lambda x: x<limit, fibonacci())))

if __name__ == "__main__":
    print(solution())

What is the index of the first Fibonacci number at least 1000 digits long? Here indexing is 1-based, and the first two Fibonacci numbers are 1 and 1. Alternatively, indexing is 0-based, and the first two Fibonacci numbers are 0 and 1. The original problem statement is available here.

Problem 26

(ns org.drcabana.euler.p26)

;; This is just long division
(defn divide [n d]
  (iterate #(* 10 (rem % d)) n))

(defn first-repeated-element
  ([xs] (first-repeated-element xs #{}))
  ([xs seen]
     (when-let [f (first xs)]
       (if (seen f)
         f
         (recur (next xs) (conj seen f))))))

(defn repeated-block [xs]
  (let [fre (first-repeated-element xs)]
    (->> xs
         (drop-while #(not= fre %)) ;; lose any noise such as leading 0's
         (next)                     ;; drop the leading fre
         (take-while #(not= fre %)) ;; grab upto next instance of fre
         (cons fre))))              ;; put back the fre we dropped

(defn num-repeated-digits [[n,d]]
    (count (repeated-block (divide n d))))

(defn solve []
  (let [scores (for [k (range 1 1000)]
                 [k (num-repeated-digits [1,k])])]
    (->> scores
         (sort-by second) ;; 2nd element is the number of recurring digits
         last             ;; the last pair has the largest 2nd element
         first)))

(defn -main []
  (println (solve)))
(ns org.drcabana.euler.p26)

(defn div-step [[n d]]
  (if (>= n d)
    [(* 10 (rem n d)) d]
    [(* 10 n) d]))

(defn step [ [n d] ]
  [(* 10 (rem n d)), d])

(defn steps [ [n d] ]
  (iterate step [n,d]))


(defn quotient [[n d]] (quot n d))

(defn first-repeated-element
  ([xs] (first-repeated-element xs #{}))
  ([xs already-seen]
     (when-let [f (first xs)]
       (if (already-seen f)
         f
         (recur (next xs) (conj already-seen f))))))

(defn recurring-digits
  [k]
  (let [steps (iterate div-step [1 k])
        fre (first-repeated-element steps)]
    (->> steps
         (drop-while #(not= fre %)) ;; lose any noise such as leading 0's
         next                       ;; drop the leading fre
         (take-while #(not= fre %)) ;; grab upto next instance of fre
         (cons fre)                 ;; put back the fre we dropped
        )))

(defn solution []
  (let [scores (for [k (range 1 1001)]
                 [k (count (recurring-digits k))])]
    (->> scores
         (sort-by second) ;; 2nd element is the number of recurring digits
         last             ;; the last pair has the largest 2nd element
         first)))

(defn -main []
  (println (solution)))
module p26 
open FSharpx.Collections

let iterate f x =
    LazyList.unfold (fun y -> Some(y, f y)) x

// This is just long division
let divide n d =
    iterate (fun x -> 10 * (x % d)) n

let firstRepeatedElt sq =
    let seen = new System.Collections.Generic.HashSet<_>()
    let rec fre xs  = 
        let x = LazyList.head xs
        if seen.Contains x then x
        else
            seen.Add x |> ignore
            fre (LazyList.tail xs)
    fre sq

let repeatedBlock sq =
    let x =  firstRepeatedElt sq
    let xs = Seq.skipWhile (fun z -> z <> x) sq
    let ys = Seq.takeWhile (fun z -> z <> x) (Seq.skip 1 xs)
    seq {yield x ; yield! ys}

let numRepeatedDigits n d =
    Seq.length <| repeatedBlock (divide n d)

let solution ulimit =
    [for k in 1..ulimit -> 
      (numRepeatedDigits 1 k, k)]
    |> Seq.max

printfn "%A" <| snd (solution 999)
https://gist.github.com/drcabana/9380680
https://groups.google.com/forum/#!topic/fsharp-opensource/fhVgE82z2-8
Semyon Grigorev
import qualified Data.Map as Map
import Data.List (sort)

-- This is just long division, n/d
divide n d =
  iterate (\x -> 10 * x `mod` d) n

firstRepeatedElt xs =
  fre xs Map.empty
  where
    fre xs seen =
      let x = head xs
      in if (Map.member x seen) then x
         else fre (tail xs) (Map.insert x x seen)

repeatedBlock ls =
  let x = firstRepeatedElt ls
      ys = dropWhile (\z -> z /= x) ls
      zs = takeWhile (\z -> z /= x) (tail ys)
  in x : zs

numRepeatedDigits n d =
  length . repeatedBlock $ divide n d

solution n = 
    snd . last $ sort [(numRepeatedDigits 1 k, k) | k <- [1..n]]

main = print $ solution 999
from itertools import takewhile, dropwhile, islice

def divide(n, d):
    while True:
        yield n
        n = 10 * (n % d)

def firstRepeatedElt(sq):
    seen = dict()
    for s in sq:
        if seen.get(s,-1) > -1:
            return s
        else:
            seen[s] = s

def repeatedBlock(sq):
    x = firstRepeatedElt(sq)
    dropwhile(lambda z: z != x, sq)
    return [x] + list(takewhile(lambda z: z != x, sq))

def numRepeatedDigits(n, d):
    return len(repeatedBlock(divide(n, d)))

def solution(ulimit):
    [a,b] = max([numRepeatedDigits(1, k),k] for k in range(1, ulimit))
    return b

if __name__ == "__main__":
    print(solution(1000))

The goal is to find the positive integer k < 1000 for which 1/k contains the longest recurring cycle in its decimal expansion. The original problem statement is available here.

The computation produces two sequences. The obvious one, [1,4,2,8, …], is the “answer”, and is the one we are taught to focus on. The other sequence, [10, 30, 20, 60, …], is not emphasized by most teachers of long divison. Yet it is more fundamental, and holds the key to understanding how to solve the current problem.

The firstRepeatedElt and repeatedBlock functions would not terminate if there were no repeated elements. That is not a problem here, because any rational p/q will contain a repeated block of digits.

Problem 27

(ns org.drcabana.euler.p27
  (:use [org.drcabana.euler.p07 :only (prime? primes)]))

(defn quadratic [a b]
  (let [q (fn [n] (+ (* n n) (* a n) b))
        t (* a b)]
    [t q]))

(defn score
  [[t q]]
  (->> (map q (range))
       (take-while prime?)
       (count)
       (vector t)))

(defn solve []
  (let [quads (for [a (range -999 1000)
                    b (take-while #(< % 1000) (primes))]
                (quadratic a b))]
    (->> (for [q quads] (score q))
         (sort-by second)
         last ;; the last pair contains the high score
         (first))))

(defn -main []
  (println (solve)))
module p27

let quadratic (a:int64) (b:int64) = 
    fun n -> (n + a)*n + b   

let score (a, b) =
    Seq.initInfinite (fun x -> int64 x)
    |> Seq.map (quadratic a b)
    |> Seq.takeWhile p07.isPrime
    |> Seq.length
    |> fun x -> (x, a*b) 

let solution =
    let smallPrimes = Seq.takeWhile (fun x -> x < 1000L) p07.primes
    [for a in [-999L..999L] do
     for b in smallPrimes -> score (a,b) ]
    |> Seq.sort |> Seq.last |> snd

printfn "%A" solution
import P07 (primes, isPrime)
import Data.Ord (comparing)
import Data.List (maximumBy)

quadratic a b =
    \n -> (n + a)*n + b

score a b = (a*b, count) 
    where count = length $ takeWhile isPrime $ map (quadratic a b) [0..]

solution =
    fst $ maximumBy (comparing snd) $ scores
    where scores = [score a b | a <- [-999..999],
                                b <- takeWhile (\x-> x < 1000) primes]

main = print solution

from itertools import takewhile
from p07 import is_prime, primes

def quadratic(a, b): 
    return lambda n: (n + a)*n + b

def nonnegs():
    a = 0
    while True:
        yield a
        a = a+1

def score(a,b):
    q = quadratic(a,b)
    count = 0
    while is_prime(q(count)):
        count +=1
    return (count, a*b) 

def solution():
    small_primes = list(takewhile(lambda x: x<1000, primes()))
    scores = [score(a, b) for a in range(-999,1000)
                          for b in small_primes]
    _,y = sorted(scores)[-1]
    return y


if __name__ == "__main__":
    print(solution())

For quadratics of form n² + an + b, where |a| < 1000 and |b| < 1000, find the a and b that produce the longest run of primes for consecutive values of n, starting with n = 0. Return the product of a and b. The original problem statement is available here.

We’ll construct quadratic functions specified by parameters a and b. Each generated function will be tagged with the product a*b.

We score each quadratic function by counting the length of the run of primes it generates. The returned value is a pair [t n] where t is the tag a*b, and n is the length of the run.

A quick glance at the problem statement might suggest that we need to vary both a and b over [-999…999], giving nearly four million cases to consider. We can do better by an order of magnitude.

We are interested in quadratics that generate primes. In particular, for any quadratic q, we require q(0) to be prime. But q(0) is equal to b. Hence we require b to be prime. Instead of testing 1999 values of b, we can restrict b to the 168 primes less than 1000.

Problem 28

(ns org.drcabana.euler.p28)

(defn sum-of-corners [n]
  (+ (* 4 n n ) (* -6 n) 6))

(defn solve []
  (let [odds (range 3 1002 2)]
    (inc (reduce + (map sum-of-corners odds)))))

(defn -main []
  (println (solve)))
module p28

let sumOfCorners n =
    4*n*n - 6*n + 6

let solution = 
    [3 .. 5 .. 1001]
    |> List.map sumOfCorners
    |> List.reduce (+)
    |> (+) <| 1

printfn "%A" solution
sumOfCorners n =
    4*n*n - 6*n + 6

solution = 
    1 + (sum $ map sumOfCorners [3,5 .. 1001])

main = print solution

def sumOfCorners(n):
    return 4*n*n - 6*n + 6

solution = sum(map(sumOfCorners, range(3,1002,2))) + 1

if __name__ == "__main__":
    print(solution)

Starting at 1 and moving to the right in a clockwise direction, a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20 07 08 09 10
19 06 01 02 11
18 05 04 03 12
17 16 15 14 13

The sum of the diagonals is 101. What is the sum of the the diagonals in a 1001 by 1001 spiral formed in the same way? The original problem statement is available here.

Forget the diagonals. Consider the concentric squares centered at 1. Notice that the square with upper right corner 9 contains exactly 9 numbers, and so has a side of length 3. Similarly, the square with upper right corner 25 contains 25 numbers and has side 5. The rising diagonal starting at 1 is the sequence of squares of the odd numbers.

Why look at the concentric squares? Because it is easy to sum the corners of the squares, and that sum across all the squares differs from the sum of the diagonals by exactly 1.

Consider a particular square, say the square of side n=5, with corners 25, 21, 17, and 13. Expressed symbolically, the corners are n^2, n^2 - n + 1, n^2 - 2n + 2, and n^2 - 3n + 3.

The solution is immediate, and uses the standard idioms.

Problem 29

(ns org.drcabana.euler.p29
  (:use [clojure.math.numeric-tower :only (expt)]))

(defn solve []
  (count (distinct (for [a (range 2 101)
                         b (range 2 101)]
                     (expt a b)))))

(defn -main []
  (println (solve)))
module p29

open System.Numerics

let pow (a : int) (b : int) : BigInteger =
    System.Numerics.BigInteger.Pow(bigint a, b)

let solution =
    seq { for a in [2 .. 100] do
          for b in [2 .. 100] ->  pow a b }
    |> Seq.distinct
    |> Seq.length

printfn "%A" solution
import Data.List (nub)
-- The oddly named *nub* returns the distinct elements of a list

solution =
    length $ nub terms
    where terms =  [a ** b | a <- [2..100], 
                             b <- [2..100]]

main = print solution

def solution():
    terms =  [a ** b for a in range(2, 101)
                     for b in range(2, 101) ]
    return len(list(set(terms)))

if __name__ == "__main__":
    print(solution())

Problem 29 is to count the distinct terms are in the sequence generated by a*b, for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100. The original problem statement is available here.

This one is immediate.

Problem 30

(ns org.drcabana.euler.p30
  (:use [org.drcabana.euler.p16 :only (digits)]
        [clojure.math.numeric-tower :only (expt)] ))

(defn phi [n]
  (reduce + (map #(expt % 5) (digits n))))

(defn guilty? [n]
  (== n (phi n)))

(defn solve []
  (reduce + (filter guilty? (range 2 999999))))

(defn -main []
  (println (solve)))
module p30

let digits n = 
    [for c in string n -> int (string c)]

let phi n = 
    digits n
    |> List.map (fun x -> pown x 5) 
    |> List.sum 

let guilty n = 
    n = phi n

let solution =
    [2..999999]
    |> List.filter guilty 
    |> List.sum 

printfn "%A" solution
import Data.Char (digitToInt)

digits n = 
    map digitToInt $ show n

phi n = 
    sum $ map (\x->x^5) $ digits n

guilty n = 
    n == phi n

solution = 
    sum $ filter guilty [2..999999]

main = print solution

def digits(n):
    return [int(d) for d in str(n)]

def phi(n):
    return sum(map(lambda x: x**5, digits(n)))

def guilty(n):
    return n == phi(n)

def solution():
    return sum(filter(guilty, range(2, 1000000)))

if __name__ == "__main__":
    print(solution())

Problem 30 is to find the sum of the integers greater than 1 that can be written as the sum of fifth powers of their digits. The original problem statement is available here.

Programmers often have a thing about meaningful function names. That makes sense in production code which has to be maintained. Mathematicians write on paper or blackboards while doing calculations by hand, and so tend to prefer short function names. I could not bring myself to call a function sumOfFifthPowerOfDigits or any such nonsense. So I called it phi, which is Greek for foo.

Problem 31

(ns org.drcabana.euler.p31)

(defn ways-to-make-change [amount coins]
  {:pre [(apply < coins)]}  ;; we require the coins sorted
  (let [c (first coins)]
    (cond
     (nil? c) 0             ;; no coins, no change
     (< amount c) 0         ;; if c is too big, so are the remaining coins
     (== amount c) 1
     :else (+ (ways-to-make-change amount (rest coins))
              (ways-to-make-change (- amount c) coins)))))

(defn solve []
  (ways-to-make-change 200 [1 2 5 10 20 50 100 200]))

(defn -main []
  (println (solve)))
module p31

let rec waysToMakeChange amount coins =
    match coins with
    | [] -> 0
    | c :: rest -> if amount < c then 0
                   elif amount = c then 1
                   else  waysToMakeChange amount rest + 
                         waysToMakeChange (amount-c) coins

let solution =
    waysToMakeChange 200 [1; 2; 5; 10; 20; 50; 100; 200]

printfn "%A" solution
waysToMakeChange amount coins =
  case coins of
    []     -> 0
    c:rest -> if amount < c then 0
                 else if amount == c then 1
                 else waysToMakeChange amount rest + 
                      waysToMakeChange (amount-c) coins

solution =
    waysToMakeChange 200 [1, 2, 5, 10, 20, 50, 100, 200]

main = print solution

def waysToMakeChange(amount, coins): 
  if coins ==  []:
    return 0
  else:
    c = coins[0] 
    rest = coins[1:]
    if amount < c:
        return 0
    elif amount == c:
        return 1
    else:
        return waysToMakeChange(amount, rest) + \
               waysToMakeChange((amount-c), coins)

def solution():
    return waysToMakeChange(200, [1, 2, 5, 10, 20, 50, 100, 200])

if __name__ == "__main__":
    print(solution())

In British currency there are eight coins: 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p). How many different ways can one make change for £2? The original problem statement is available here.

Some variation of this problems appears in almost every introduction to combinatorics. Two simple ideas combine to give an elegant solution to the problem.

The first idea is that when making change for N, either we use coin c, or we don’t. So the number of ways to to make change is A+B, where A and B denote the following:

The second idea is that the number of ways to make change for N using c is exactly the same as the number of ways to make change for N-c. Why? Consider any way to make change for N using c. Simply remove one instance of the coin c and you have change for N-c.

These two insights combine to give a very pretty recursive solution to the problem. This is a problem where recursion really shines. Just for grins, try writing a non-recursive solution…

BTW, note that the solution depends on the list of coins being sorted in ascending order.

Problem 32

(ns org.drcabana.euler.p32
  (:use [clojure.math.combinatorics :only [permutations]]))

(defn number
  [& digits]
  (reduce #(+ (* 10 %1) %2) 0 digits))

(defn pandigital-prod [[a b c d e f g h i]]
  (let [z (number f g h i)]
    (cond
        (== z (* (number a b) 
                 (number c d e))) z
        (== z (* (number a)
                 (number b c d e))) z
        :else 0)))

(defn solve []
  (->> (range 1 10)
       (permutations)
       (map pandigital-prod)
       (distinct)
       (reduce +)))

(defn -main []
  (println (solve)))
module p32

let pandigitalProd [a;b;c;d;e;f;g;h;i] =
    let number = List.reduce (fun x y -> 10*x + y)
    let z = number [f;g;h;i]
    if z = number [a;b] * number [c;d;e] then z
    elif z = number [a]   * number [b;c;d;e] then z
    else 0

// inject 0 [1;2;3] evaluates to [[0;1;2;3]; [1;0;2;3]; [1;2;0;3]; [1;2;3;0]]
let rec inject x xs =
    match xs with 
    | []    -> [[x]]
    | y::ys -> (x::xs) :: List.map (fun z -> y::z) (inject x ys)

let rec permutations xs =
    match xs with
    | []    -> [[]]
    | y::ys -> List.collect (inject y) (permutations ys)

let solution = 
    permutations [1..9]
    |> Seq.map pandigitalProd
    |> Seq.distinct
    |> Seq.sum

printfn "%A" solution
import Data.List (nub)

pandigitalProd [a,b,c,d,e,f,g,h,i] =
    if z == number [a,b] * number [c,d,e] ||
       z == number [a] * number [b,c,d,e] 
    then z
    else 0
    where z = number [f,g,h,i]
          number = foldl (\x y -> 10*x + y) 0   

-- inject 0 [1,2,3] evaluates to [[0,1,2,3], [1,0,2,3], [1,2,0,3], [1,2,3,0]]
inject x xs =
  case xs of 
    []   -> [[x]]
    y:ys -> (x:xs) : map (\z -> y:z) (inject x ys)

permutations xs =
  case xs of
    []   -> [[]]
    y:ys -> concatMap (inject y) $ permutations ys

solution = 
    sum $ nub $ map pandigitalProd $ permutations [1..9]

main = print solution

from itertools import permutations

def number(lst):
    return reduce(lambda x,y: 10*x+y, lst)

def pandigitalProd(lst):
   [a,b,c,d,e,f,g,h,i] = lst
   z = number([f,g,h,i])
   if z == number([a,b]) * number([c,d,e]): 
        return z
   elif z == number([a]) * number([b,c,d,e]): 
        return z
   else: 
        return 0

def solution():
    prods = map(pandigitalProd, permutations(range(1,10)))
    return sum(list(set(prods)))

if __name__ == "__main__":
    print(solution())

An n-digit number is pandigital if it makes use of each of the digits 1 to n exactly once. For example, the 5-digit number 15234 is pandigital.

The product 7254 is unusual because the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital. Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital expresssion. Count each product only once. The original problem statement is available here.

The fact that we want to use each of the digits 1 through 9 exactly once immediately suggests that we will want to generate permutations of the digits 1 .. 9.

Given a permutation, say [3 9 1 8 6 7 2 5 4], we’ll split it into three parts, say [[3 9] [1 8 6] [7 2 5 4]], and then turn each parts into the number represented by the corresponding digits, here [39 186 7254]. We’ll then test to see whether the product of the first two numbers is equal to the third.

There are only two ways to split the permutations into three numbers such that the product of the first two is equal to the third. For instance, the product of two single digit numbers cannot equal a seven digit number. A bit of thought eliminates the other impossible cases. The feasible splits are either a two digit number and a three digit number producing a four digit number, or a one digit number and a four digit number producing a four digit number.

Clojure and Python provide some flavor of a built-in permutations function. Haskell and F# may do so, but I could not seem to find it, and so rolled my own. It is generally a questionable idea to implement a mathematical function that the language or standard libraries already provide.

Problem 33

(ns org.drcabana.euler.p33)

;; For example, (number 2 3) yields 23
(defn number [tens ones]
  (+ (* 10 tens) ones))

(defn curious?
  ([[j k]]
     (first (keep (partial curious? [j k])
                  (range 1 10))))
  ([[j k] n]
     (let [jn (number j n)
           kn (number k n)
           nj (number n j)
           nk (number n k)]
       (some #{(/ j k)} ;; Sets are functions!
             [(/ jn kn) (/ jn nk) (/ nj kn) (/ nj nk)] ))))

(defn solve []
  (->> (for [a (range 1 10)
             b (range 1 10)]
         [a b])
       (keep curious?) ;; Keep the non-nils
       (filter #(< % 1))
       (reduce *)
       (denominator)))

(defn -main []
  (println (solve)))
module p33

let number tens ones =
    10N * tens + ones

let curious (j, k) =          
  let candidate n = 
     let jn = number j n
     let kn = number k n
     let nj = number n j
     let nk = number n k 
     let ratios = [jn/kn; jn/nk; nj/kn; nj/nk]
     List.filter (fun x -> x = (j/k)) ratios
  let candidates = List.concat [for n in 1N..9N -> candidate n]
  not <| List.isEmpty candidates          

let solution = 
    let s = [for a in 1N..9N do for b in 1N..9N -> (a,b)]
            |> List.filter curious 
            |> List.filter (fun (a,b) -> a < b)
            |> List.map (fun (a,b) -> a/b)
            |> List.reduce (*)
    s.Denominator

printfn "%A" solution
import Data.Ratio

number tens ones =
    10*tens + ones

curious (j, k) =
     not $ null candidates
     where candidates = dropWhile null [candidate n | n <- [1..9]]
           candidate n = 
              filter (== (j % k))  ratios
              where
                jn = number j n
                kn = number k n
                nj = number n j
                nk = number n k 
                ratios = [jn % kn, jn % nk, nj % kn, nj % nk]
solution = 
    denominator $ product [a % b | (a,b) <- cur]
    where cur = filter curious [(a,b) | a <- [1..9], b <-[1..9], a < b]

main = print solution

from fractions import Fraction
from operator import mul

def number(tens, ones):
    return 10*tens + ones

def curious(j,k):
    jok = Fraction(j,k)
    for n in range(1,10):
        jn = number(j,n); kn = number(k,n)
        nj = number(n,j); nk = number(n,k)
        if jok in [Fraction(jn,kn),Fraction(jn,nk),
                   Fraction(nj,kn),Fraction(nj,nk)]:
            return True
    return False

def solution():
    pairs = [(a,b) for a in range(1,10) for b in range(1,10)]
    cur = [Fraction(a,b) for (a,b) in pairs if curious(a,b) and a < b]
    prod = reduce(mul, cur)
    return prod.denominator

if __name__ == "__main__":
    print(solution())

49/98 is a curious fraction, because it allows incorrect cancellation. One can cancel the 9, which is absurd, and still get the right result 49/98 = 4/8. We shall consider fractions like 30/50 = 3/5 as trivial.

There are four non-trivial curious fractions less then 1, with two digit numerators and denominators. If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

The original problem statement is available here.

Colophon

Languges:

Operating Systems:

Windows ran virtualized under VirtualBox version 4.2.8

The Leo text editor was extremely useful in handling the quirks of working with many files in multiple languages, across operating systems. Leo is much more than a text editor; it is a tree wrangler. It even lets you plug in Emacs or Vim to do the actual text editing, giving you the best of both worlds. Highly recommended.

The side-by-side presentation layer was courtesy of Slate. The Slate layout seemed so right for what I had in mind that I could not resist. I had fun with this, so thanks.

Version control by Git and Github.

Secure data movement courtesy of OpenSSH, my nominee for the title of THE indispensible software tool.

I am grateful to the many people who have made such amazing tools freely available.

Appendix

We will build a map of key, value pairs. The keys are integers, the values are collections of integers. The semantics of the map are that a key k should be in the map if and only if k is composite. The value v corresponding to k will be a collection of one or more prime divisors of v.

Initially the map is empty. We walk a prefix of the integers, say [2 .. Max] in order, testing each element N in turn against the map, and updating the map as follows:

The insertion rules guarantee that only composite keys enter the map. The question is whether the map eventually contain every composite number in [2 .. Max]? It will, as can be proven using mathematical induction. I’ll spare you the proof, and instead show you the idea behind it.

Consider any composite number, say 12. It has a least prime divisor, 2 in this case. Follow the chain of insertions. We hit 2, then insert 4,{2} We hit 4, then insert 6,{2} We hit 6, then insert 8,{2} You can see where this is going: every multiple of 2 larger than 2 is eventually a key. Similarly, for any prime p, every multiple of p larger than p is eventually a key. But every composite is a multiple of some prime, so every composite is eventually in the map.

We must be careful with collisions. Suppose our map contains (39, {3..}),(40, {2..}) due to insertions prior to handling 39. Now hit 39, and insert (42, {3}). Next we hit 40, and want to insert (42, {2}). We do not want the (42, {2}) to simply replace (42, {3}). Both 2 and 3 divide 42, so what we want is (42, {2,3}). Our updates should not lose divisors.