euler

1.0.0


Clojure solutions to the first 33 Project Euler problems.

Unit tests are provided to compare the result of each problem's solution function to the official Project Euler answer for that problem. A simple way to run the tests is by using lein from the command line:

(/home/drc/code/euler)$ lein test

dependencies

org.clojure/math.numeric-tower
0.0.1
org.clojure/math.combinatorics
0.0.2
org.clojure/clojure
1.4.0-beta1

dev dependencies

swank-clojure
1.4.0
lein-marginalia
0.7.0



(this space intentionally left almost blank)
 

Before launching into the problems, let's take a quick tour of some useful syntax.

(ns org.drcabana.euler.prequel)

Defining a function is the natural unit of work in functional programming. Clojure offers multiple ways to define functions, so let's look at some examples. This treatment is not exhaustive, it just covers some common cases.

The classic function of one argument.

(defn square
  [x]
  (* x x))
=>(square 4)
   16

A two argument function.

(defn sum-of-cubes
  [x y]
  (+ (* x x x) (* y y y) ))
=>(sum-of-cubes 2 3)
   35

A single required argument, with a variable number of optional arguments. The more-args argument is treated as a sequence. The name does not matter; it is the & that signals that the next symbol will be the bound to the sequence of subsequent arguments.

(defn sum-of-squares
  [x & more-args]
  (+ (square x)
     (apply + (map square more-args))))
=>(sum-of-squares 2)
   4
   =>(sum-of-squares 2 3 4)
   29

There are a couple of ways two define anonymous functions. The first is to use fn. Here's an anonymous version of square, applied to the number 5. You can think of fn as Clojure's way of spelling lambda.

=>( (fn [x] (* x x)) 5)
   25

An even terser way to define square is to use the #() form. Here % denotes the single argument to the function .

=>( #(* % %) 5)
   25

The #() form allows for multiple arguments by numbering them. Here we define a function which divides its first arg by its second, and apply it.

=>( #(/ %1 %2) 20 5)
   4

You can create functions of multiple arity, defined on a case per case basis.

(defn foo
  ([] "one meeellion")
  ([x] (* 2 x))
  ([x y] (+ x y))
  ([x y z] (max x y z)))
=>(foo)
   "one meeellion"
   =>(foo 3)
   6
   =>(foo 2 3)
   5
   =>(foo 2 3 4)
   4

Various Clojure data structures can be used both as data structures and as functions. For instance, sets can be used as functions. Let's define a set.

(def digits #{0 1 2 3 4 5 6 7 8 9})

A slick way way to use a set is to test for membership in the set itself. The way it works is that (digits x) returns x when x is an element of digits, and returns nil otherwise.

=>(digits 3)
   3    ;; 3 is truthy.
   =>(digits 22)
   nil  ;; nil is falsey.

This becomes problematic if nil is an element of the set in question. When that is not an issue, this way of testing membership can be quite handy. See the solution to problem 24 for an example.

For more (somewhat densely packed) information, check out the official documentation for Clojure's special forms and for the Clojure reader.

Clojure is fortunate to have several very good books. To my taste, the best introductory book is Programming Clojure. The Joy of Clojure is a must read, but perhaps not the best place to start for readers who don't already have some lisp in their veins.

 

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.

(ns org.drcabana.euler.prob01)

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

(defn qualifies?
  [x]
  {:pre (integer? x)}
  (or (zero? (rem x 5))
      (zero? (rem x 3))))

The solution illustrates recurring patterns worth watching for in subsequent problems.

  • We begin by generating a sequence of data.
  • We then use filter and a predicate to extract a desired subsequence.
  • We wrap up by using reduce and a selected function to compute a value from the subsequence.
(defn solution []
  (reduce + (filter qualifies? (range 1000))))

Notes:

Predicates are functions that return true or false. By convention, the names of predicates end with a question mark.

Notice that Clojure has some design-by-contract fu. We used a precondition in the definition of the qualifies function. For the official docs on pre-conditions, grep for "pre-expr" here. Post-conditions are also available. If you would like a stronger dose of Clojure dbc goodness, check out Trammel.

Docs: filter integer? range reduce rem zero?

 

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

(ns org.drcabana.euler.prob02)

fibonacci is an arity-0 function which returns the sequence of Fibonacci numbers. The +' operator performs addition with bigints, avoiding overflows for large values of a and b.

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

The pattern is pretty much the same as in the previous problem. We generate a sequence, filter it with a predicate, and reduce the result to a single number.

(defn solution
  []
  (->> (fibonacci)                  ;; generate an infinite lazy sequence
       (take-while #(< % 4000001))  ;; realize the subseq of interest
       (filter even?)               ;; filter out evens, then reduce
       (reduce +)))

Notes:

The overall pattern of the solution is the same as in problem 1, but the code looks a bit different, due to the use of the ->> macro. I like ->> because it allows code to be read from top to bottom. By way of comparision, I could have written the code this way.

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

Docs: ->> first iterate letfn map take-while

 

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

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

Return the least divisor of n in the closed interval [k ... n].

(defn least-divisor
  [k n]
  {:pre [(integer? k) (integer? n) (<= 2 k n)]}
  (let [limit (inc (int (sqrt n)))
        candidates (drop-while #(pos? (rem n %)) (range k limit)) ]
    (if (seq candidates) (first candidates) n)))

Return the prime factorization of n, as a vector of primes. By construction the factors will be in non-decreasing order. For example,

;=> (prime-factors 72)
[2 2 2 3 3]
(defn prime-factors
  [n]
  {:pre [(integer? n) (< 0 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 solution []
  (reduce max (prime-factors 600851475143)))

Docs: conj drop-while loop max quot recur seq

 

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

(ns org.drcabana.euler.prob04)

Is word a palindrome?

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

There are only 900 3-digit numbers, so brute force suffices. It suffices to consider only the cases where a <= b because multiplication is commutative.

(defn solution []
  (let [products
       (for [a (range 100 1000)
             b (range 100 1000) :when (<= a b)]
         (* a b))]
   (reduce max (filter palindrome? products))))

Notice that once again we constructed a sequence, filtered it, then reduced it.

Docs: for let str

 

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

The LCM function is well known to be associative:

LCM(LCM(a,b),c) = LCM(a, LCM(b,c)).

That means the Clojure solution to our problem is immediate: (reduce LCM (range 1 21)). We just need to construct an LCM function. A simple way is 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. Naturally, we use Euclid's algorithm to implement GCD.

(ns org.drcabana.euler.prob05)

gcd computes the greatest common divisor of positive integers a and b. It would be faster to replace the repeated subtractions with division, but this code is prettier because it is more symmetric. In recreational programming one is free to prefer beauty over speed.

(defn gcd
  [a b]
  {:pre [(integer? a) (integer? b) (pos? a) (pos? b)]}
  (cond
   (= a b) a
   (> a b) (recur (- a b) b)
   :else   (recur (- b a) a)))

lcm computes the least common multiple of a and b.

(defn lcm
  [a b]
  (/ (* a b) (gcd a b)))
(defn solution []
  (reduce lcm (range 1 21)))

Each of the first five solutions in this problem set has used reduce. I did not set out to do that, and only noticed it after the fact. The reduce function will be used many times in the remaining problems.

Docs: cond

 

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.

(ns org.drcabana.euler.prob06)
(defn solution []
  (let [square #(* % %)
        values (range 1 101)
        square-of-sum  (square (reduce + values))
        sum-of-squares (reduce + (map square values))]
    (- square-of-sum sum-of-squares)))
 

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

(ns org.drcabana.euler.prob07
  (:use [org.drcabana.euler.prob03 :only (least-divisor)]))

We already have a useful bit of number theoretic code from problem 3. We reuse it via the :use statement in the namespace declaration.

Return the least positive integer greater than 1 which divides n.

(defn least-nontrivial-divisor
  [n]
  {:pre [(integer? n) (<= 2 n)]}
  (least-divisor 2 n))

Primes are easily defined in terms of the least-nontrivial-divisor function: an integer n>1 is prime if and only if its least non-trivial divisor is n.

(defn prime?
  [n]
  {:pre [integer? n]}
  (if (< n 2)
    false
    (== n (least-nontrivial-divisor n))))

Return the sequence of primes. We test only odd numbers for primality.

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

Clojure uses 0-based indexing, but the problem statement uses 1-based indexing, so we have to decrement the index.

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

Docs: cons iterate nth

 

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.

(ns org.drcabana.euler.prob08)

We will need a way to convert a numeric character into an integer. Notice the idiom used in the precondition: membership in a set is tested by using the set as a function.

(defn char-to-int [char]
  {:pre [(#{\0 \1 \2 \3 \4 \5 \6 \7 \8 \9} char)]}
  (Integer/parseInt (str char)))
(defn solution []
  (let [product (partial reduce *)
        digits "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"]
    (->> (map char-to-int digits)
         (partition 5 1)
         (map product)
         (reduce max))))

Picasso is alleged to have remarked that "good artists borrow, great artists steal". The extremely useful partition function was stolen from Mathematica. Well done.

I quietly used Java, in the call to Integer/parseInt. Java interop in Clojure can be so seamless you may not notice it.

Docs: partial partition

 

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

a + b + c = 1000

a2 + b2 = c2.

The original problem statement is available here.

(ns org.drcabana.euler.prob09)
(defn pythagorean?
  [a b c]
  (= (* c c) (+ (* a a)
                (* b b))))

We choose c = 1000 - a - b, thus meeting the sum constraint. The :when condition ensures that the Pythagorean constraint is met.

(defn solution []
  (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))))

Docs: for

 

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

(ns org.drcabana.euler.prob10
  (:use [org.drcabana.euler.prob07 :only (primes)]))

The machinery for generating primes is in place from problem 7. The only thing new here is the final reduction step.

(defn solution []
  (reduce + (take-while #(< % 2000000) (primes))))
 

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.

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

Here are the numbers, or rather a string we'll later convert to a sequence of numbers.

(def 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")

We want to work with a two-dimensional grid, so we define a constructor that turns a sequence (of suitable length) into square matrix. The matrix will be represented as an anonymous function of variable arity.

The matrix function returns a lookup function. Given two integer indices, the latter performs the expected lookup. Conveniently, the lookup function will return 1 if either index is out of bounds. Given no args, the lookup function will return the row length of the matrix.

(defn matrix
  [xs]
  (let [row-length (int (sqrt (count xs)))]
    (assert (= (count xs) (* row-length row-length)))
    (letfn [(valid? [j k] (and (integer? j)
                               (integer? k)
                               (< -1 j row-length)
                               (< -1 k row-length)))
            (idx [j k]    (+ j (* row-length k)))]
      (fn
        ([] row-length)
        ([[j k]] (if (valid? j k) (nth xs (idx j k)) 1))))))

Compute the sequence of the indices of elements contiguous to origin in the given direction. The origin and direction should each be pairs [j k] of integers.

(defn contiguous
  [origin direction]
  (iterate #(map + direction %) origin))

Determine the largest contiguous length-four product in matrix M.

(defn score
  ([M]
     (reduce max (for [j (range (M))
                       k (range (M))]
                   (score M [j k]))))
  ([M [j k]]
     (let [directions [ [0 1] [0 -1] [1 0] [-1 0] [1 1] [1 -1] [-1 1] [-1 -1] ]]
       (reduce max (map #(score M [j k] %) directions))))
  ([M [j k] dir]
     (let [segment (take 4 (contiguous [j k] dir))]
       (reduce * (map M segment)))))
(defn solution []
  (let [numbers (->> digits
                     (re-seq #"\d+")
                     (map #(Integer. %)))]
    (score (matrix numbers))))

This was largely an exercise in using closures. I have the nagging feeling I could have done something simpler. But closure-object duality is cool.

Docs: assert letfn re-seq

 

Problem 12 is to find the first triangle number to have 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.

(ns org.drcabana.euler.prob12
  (:use [org.drcabana.euler.prob03 :only (prime-factors)]))

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).

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

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 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].

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

The pieces are in place, the only thing left is to put them together.

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

We determined the number of divisors of n without actually computing the divisors. Another approach would have been to compute the divisors and count them. In problem 21 we will write a function to compute the divisors of n.

Docs: drop-while identity iterate partition-by

 

Problem 13 is to find the first ten digits of the sum of 100 50-digit numbers. Here are the 50-digit numbers, or rather, a string containing them, one per line. The original problem statement is available here

(ns org.drcabana.euler.prob13)
(def num-str
  "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 solution []
  (->> (re-seq  #"\d+" num-str) ;; split the string
       (map #(bigint %))        ;; convert substrings to integers
       (reduce +)               ;; sum the integers
       (str)                    ;; convert the sum to a string
       (take 10)                ;; take the first ten digits
       (apply str)              ;; concat the digits into a string
                                ;; turn final string back into integer
       (bigint)))

Docs: apply bigint re-seq

 

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

(ns org.drcabana.euler.prob14)

First let's define the Collatz function:

(defn collatz [n]
  {:pre [(pos? n) (integer? n)]}
  (if (even? n)
    (/ n 2)
    (+ (* 3 n) 1)))

For any positive integer n, we can form the corresponding Collatz sequence.

(defn C [n]
  (iterate collatz n))

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.

Define the Collatz-length of N to be the number of terms in C(N) before the first 1. The use of memoize speeds things up considerably, but this is the most time intensive of the problems in this set.

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

The question is what value of N less than one million has the largest collatz-length.

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

Docs: iterate memoize sort-by

 

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)!)

In particular C(40,20) = 40!/(20! * 20!). A bit of cancellation simplifies the expression. In Clojure versions 1.3 and above, multiplication can overflow, though not silently. We avoid the overflow by using the *' operator.

(ns org.drcabana.euler.prob15)
(defn solution []
  (/ (reduce *' (range 21 41))
     (reduce *' (range 1 21))))
 

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

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

Compute the sequence of digits in the base 10 representation of n.

(defn digits
  [n]
  {:pre [(integer? n)]}
  (letfn [(char-to-int [c] (Integer. (str c))) ]
    (map char-to-int (str n))))
(defn solution []
  (reduce + (digits (expt 2 1000))))

Docs: Integer

 

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.

(ns org.drcabana.euler.prob17)

Without much ado, here's a solution.

(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 mutually call one another, so 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 solution []
  (->> (range 1 1001)
       (map name-of)
       (map #(.length %))
       (reduce + )))

Docs: declare

 

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.

(ns org.drcabana.euler.prob18
  (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")

Our data is given to us as a string, so we'll transform the string into something we can work with. First we'll turn it into a sequence of integers, then we'll turn that sequence into a data structure suited to our algorithmic needs.

Construct a sequence of integers from a string of whitespace delimited blocks of digits.

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

The data structure we want looks like this: ((75) (95 64) (17 47 82) (18 35 87 10) (20 4 82 47 65) ... )

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

The idea here is simple. Imagine the triangle has only three elements, say (a (b c)). Then the maximal path sum is (+ a (max b c)). The trick is to start with the two bottom rows, and work up.

(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 solution []
  (first (reduce merge-rows (reverse triangle))))

Notice that computing the maximal sum across all paths did not require determining the path along which the sum is maximal.

We resisted the temptation to use naked recursion. We could have tried transforming the numbers into the obvious binary tree, and defined the sum at the root to be the number at the root plus the max of the sums of the root's two subtrees, with appropriate stopping conditions at the leaves. For a small problem (like this one) it would have worked, but that algorithm uses resources exponential wrt to the depth of the tree. The algorithm actually used is quadratic wrt to the the number of elements in the last line of the triangle.

Docs: split-lines

 

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.

(ns org.drcabana.euler.prob19)
(defn solution []
  (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
       calendar-dates   (cycle (concat year year year leap-year))    ;; 1904 was a leap year
       Sunday?          (fn [[day date]] (= :sun day))
       first-of-month?  (fn [[day date]] (= 1 date))]
    (->> (map vector days-of-week calendar-dates)
         (take days-per-century)
         (filter Sunday?)
         (filter first-of-month?)
         (count))))

The solution is quite mechanical. We construct two sequences: one of calendar dates, and one of weekdays. Both sequences cycle endlessly. We count off 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.

Docs: cycle mapcat vector

 

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

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

Problem 21: 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.

(ns org.drcabana.euler.prob21)

Compute the divisors of n. Each divisor is counted only once.

(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)))

Predicate: is n an amicable number?

(defn amicable?
  [n]
  (let [m  (- (sum-of-divisors n) n)
        k  (- (sum-of-divisors m) m)]
    (and (= n k)
         (not= n m))))
(defn solution []
  (reduce + (filter amicable? (range 1 10000))))

Docs: into mapcat not= quot when

 

Problem 22: 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.

(ns org.drcabana.euler.prob22)
(defn solution []
  (let [alpha  (seq "ABCDEFGHIJKLMNOPQRSTUVWXYZ")
        point-values (zipmap alpha (iterate inc 1))
        score  (fn [name]
                 (reduce + (map point-values name)))
        names (->> (slurp "data/names.txt")
                   (re-seq #"[A-Z]+" )
                   (sort))]
    (reduce + (map * (map score names) (iterate inc 1) ))))

Docs: slurp sort zipmap

 

Problem 23: A positive integer n is called 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.

(ns org.drcabana.euler.prob23
  (:use [org.drcabana.euler.prob21 :only (divisors)]))
(defn abundant?
  [n]
  (let [divs (divisors n)
        sum-proper-divisors (fn [k] (- (reduce + divs) k))]
    (> (sum-proper-divisors n) n)))

The magic constant 28123 is stipulated by the problem.

(def limit (inc 28123))

There are 6072 elements in abundants.

(def abundants (vec (filter abundant? (range 1 limit))))

Construct the set of numbers below limit which are the sum of two members of abundants.

(defn sums-of-abundants []
  (into #{}
        (for [a abundants b abundants :when (<= a b) :when (< (+ a b) limit)]
          (+ a b))))
(defn solution []
  (let [total-all (reduce + (range 1 limit))
        total-soa (reduce + (sums-of-abundants))]
    (- total-all total-soa)))

Docs: into vec

 

Problem 24: 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.

(ns org.drcabana.euler.prob24)

The simple approach is to use brute force. Notice that each :when condition uses a set as a function to test for membership in the set. We simply force a through j to be distinct.

(defn perms []
  (let [symbols (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])))

The Project Euler problem statement require the permutation to be represented as a 10 digit integer.

(defn perm-to-integer [perm]
  (bigint (apply str perm)))

We generate permutations in lex order, and just pick the one we want. Clojure uses 0-based indexing, but the problem implicitly uses 1-based indexing. We need to adjust the index to get our answer.

(defn solution []
  (perm-to-integer (nth (perms) 999999)))

The brute force approach generated a lot of permutations we did not need. A fancier algorithm can compute the desired permutation directly. The algorithm takes advantage of a relationship between permutations of the digits 0...9 and the representation of integers in a factorial base. The details are beyond the scope of these comments, but the interested reader might look at this Wikipedia article.

Compute the factorial of n.

(defn fac
  [n]
  (reduce * (range 2 (inc n))))

Compute the sequence of factorials of the positive integers.

(defn factorials
  []
  (map fac (iterate inc 1)))

Express the positive integer n as the coefficients of linear combination of factorials.

=> (fdase 134)
(1 0 2 1 0)
;; 134 = 1*5! + 0*4! + 2*3! + 1*2! + 0*1!
(defn fbase
  ([n]
     (let [basis (reverse (take-while #(<= % n) (factorials)))]
       (fbase n basis [] )))
  ([n basis accumulator]
     (if (empty? basis)
       accumulator
       (let [b (first basis)]
         (recur (rem n b)
                (rest basis)
                (conj accumulator (quot n b)))))))

The nth permutation of the symbols 0-9 in lex order, indexing is 1-based.

(defn nth-perm
  [n]
  (loop [symbols (range 10)
         indices (fbase (dec n))
         result  []]
    (if (empty? indices)
      (concat result symbols)
      (let [k           (first indices)
            sym         (nth symbols k)
            without-sym (concat (take k symbols)
                                (drop (inc k) symbols))]
        (recur without-sym
               (rest indices)
               (conj result sym))))))
(defn solution-alternative []
  (perm-to-integer (nth-perm 1000000)))

Docs: concat conj nth

 

Problem 25: What is the index of the first Fibonacci number at least 1000 digits long? The original problem statement is available here.

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

The problem implicitly uses 1-based indexing, Clojure uses 0-based indexing. So counting the 'too-small' cases gives the expected answer.

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

Problem 26 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.

(ns org.drcabana.euler.prob26)

This problem centers about the algorithm for long division. Suppose n and d are positive integers. We want to divide n by d. If n > d, as our first step we compute (quot n d) and (rem n d). If not, we multiply n by 10 and then proceed as before. Each step subsequent step in long division is much the same.

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

Lets see the division-step function in action. Consider 1/7, whose decimal expansion is 0.(142857) where the parens denote a recurring block of digits.

=> (take 7 (iterate div-step [1 7]))
([1 7] [10 7] [30 7] [20 7] [60 7] [40 7] [50 7])

Hmm, that may not seem entirely clear. It becomes clearer if we actually compute the quotients denoted by each pair.

(defn quotient [[n d]] (quot n d))
=> (take 7 (map quotient (iterate div-step [1 7])))
(0 1 4 2 8 5 7)

At this point we have the machinery needed to compute decimal expansions. Next we focus on finding the recurring block of digits. The following utility function will be useful.

Find the first repeated element in a sequence. If none is found, return nil.

(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))))))

The first-repeated-element function would not terminate if given an infinite sequence with no repeated elements, but that is not a problem here. We are ready to go.

Compute the recurring digits in the decimal expansion of 1/k for integer k.

(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
         (map quotient))))
=> (recurring-digits 7)
(1 4 2 8 5 7)

Let's wrap this up.

(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)))
 

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.

(ns org.drcabana.euler.prob27
  (:use [org.drcabana.euler.prob07 :only (prime? primes)]))

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

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

We score the quadratic function q 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.

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

A quick glance at the problem statement might suggest that we need to vary both a and b over (range -999 1000), 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. Instead of testing 1999 values of b, we can restrict b to the 168 primes less than 1000.

(defn solution []
  (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)))

Notice the similarity of the solution function for this problem to that of problem 26.

 

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  7  8  9 10
19  6  1  2 11
18  5  4  3 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.

(ns org.drcabana.euler.prob28)

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. A bit of thought shows that the sides of the concentric squares are the odd numbers, starting from 3.

Why do we care about 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 n2, n2 - n + 1, n2 - 2n + 2, and n2 - 3n + 3.

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

The solution is immediate, and uses the standard idioms.

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

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.

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

This one is immediate.

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

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.

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

We'll need a function to compute the sequence of digits of n. Fortunately, we already have one of those, digits, left over from problem 16.

=>(digits 12345)
(1 2 3 4 5)

It's hard to come up with a good short name for a function that computes the sum of the fifth powers of the digits of n. I'll just call it phi, which is Greek for foo.

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

We need a name for integers that satisfy (== n (phi n)). Let's call them guilty numbers, and write a predicate to recognize them.

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

The question is what to do now. We could use guilty? to filter the integers. Let's do that, and take a peek at the first element of the sequence.

=>(take 1 (filter guilty? (iterate inc 2)))
(4150)

The trouble with this approach is that we don't know how many guilty numbers there are. The problem statement implies that there are only finitely many, but we don't know exactly how many. So using take as above is out. If we try to take too many, the search for more will not terminate.

We need an upper bound B on the size of the largest guilty number. Given such a bound, our solution would be (reduce + (filter guilty? (range 2 B))).

As it turns out, guilty numbers can't get very large. Why? Given any k-digit n, (phi n) is bounded above by (* k (expt 9 5)). Let's look at some concrete numbers.

=>(for [k '(9999 99999 999999)] [k (phi k)])
([9999 236196] [99999 295245] [999999 354294])

Notice that 999999 is much larger than (phi 999999), so there can not be any guilty numbers larger than 999999. This upper bound is not very tight, but it's good enough for the purpose at hand.

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

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.

(ns org.drcabana.euler.prob31)

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 obvious. 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:

A : the number of ways to make change using c

B : the number of ways to make change without using c

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.

(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 solution []
  (ways-to-make-change 200 [1 2 5 10 20 50 100 200]))

This is one of those problems where recursion leads to a very natural solution. Just for grins, try writing a non-recursive solution.

Docs: apply

 

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.

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

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. Way back in problem 24 we generated permutations of the digits 0-9, by brute force.

(defn perms []
  (let [symbols (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])))

That was fine for a one time thing, and it allowed me to illustrate both the :when notation, and the use of sets as their own characteristic functions. But one time was enough. It is rarely a good idea to roll your own mathematical functions when those functions are available as library functions. This time we'll use the permutations function provided by the clojure.math.combinatorics library.

Given a permutation, for example [ 3 9 1 8 6 7 2 5 4], we will split it into three parts, say [[3 9] [1 8 6] [7 2 5 4]], and then turn each of the 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.

Let's write some code. First we'll handle turning sequences of digits into numbers. Horner's algorithm is simple, efficient, and easily expressed using the reduce function. Notice that reduce can take an initial scalar argument in addition to the usual sequence argument. That initial arg shines here.

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

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.

(defn phi [[a b c d e f g h i]]
  (let [x (horner a b)
        y (horner c d e)
        y1 (horner b c d e)
        z (horner f g h i)]
    (cond
        (== z (* x y)) z
        (== z (* a y1)) z
        :else 0)))

I did not even try to give that last function a meaningful name. Mathematicians have very few qualms about meaningless function names, but some programmers find it difficult to let go. To them I say relax, take a walk on the wild side.

The problem requires that any given product be counted only once. The distinct function is tailor made for that job.

(defn solution []
  (->> (range 1 10)
       (permutations)
       (map phi)
       (distinct)
       (reduce +)))

Docs: cond distinct reduce

 

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 1, with two digit numerator and denominator. 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.

(ns org.drcabana.euler.prob33)

Here's a better way to think about 'curious' fractions. The fraction 4/8 is curious because there exists a single digit integer n (n=9 as it happens) such that 4/8 = 4n/n8. Here juxtaposition does not denote mulitplication. Instead 4n denotes 4*10+n, and n8 denotes n*10 +8.

We need a way to turn two digits into a number in the obvious way.

(defn number [a b]
  (+ (* 10 a) b))

When the fraction j/k is curious return j/k, otherwise return nil. The numerator and denominator of Clojure ratios are relatively prime, i.e., have no common factors.

(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)}
             [(/ jn kn) (/ jn nk) (/ nj kn) (/ nj nk)] ))))
(defn solution []
  (->> (for [a (range 1 10)
             b (range 1 10)]
         [a b])
       (keep curious)
       (filter #(< % 1))
       (reduce *)
       (denominator)))

Something I have neglected to mention so far is that in the ->> macro, one is not required to put parens around a function of a single argument. For instance, I could have written the solution this way.

(defn solution-alternate []
  (->> (for [a (range 1 10)
             b (range 1 10)]
         [a b])
       (keep curious)
       (filter #(< % 1))
       (reduce *)
       denominator))

Notice that denominator is not enclosed in parens. As a matter of taste I prefer the parens. It looks more uniform to me. I'm going to guess that anyone reading this is not likely to be parenphobic.

Docs: denominator keep partial some