Problem 9: Pythagorean Triplet

19 10 2009

Find the only Pythagorean triplet which sums to get 1000

A Pythagorean triplet consists of 3 numbers say x, y and z such that x < y < z and x^2 + y^2 = z^2.

The task is to find a triplet which satisfies the equation x + y + z = 1000

(defn sqr [x]
    (* x x))

(defn triplets [n]
    (loop [x 1 y 2 z (- n 3) acc '()]
  	    (>= x z) acc
	    (>= y z) (recur (inc x) (+ 2 x) (- n (+ 3 x x)) acc)
	    :else (recur x (inc y) (dec z) (cons (list x y z) acc)))))

triplets generates all possible triplets (x, y, z) where x + y + z = 1000 and x < y < z

After this all that needs to be done is

(apply * (first (filter #(let [[a b c] %]
				(= (+ (sqr a) (sqr b)) (sqr c)))
			    (triplets 1000)))

The let construct in this case has new syntax

(let [[a b c] '(1 2 3)]

This is known as destructuring, this syntax binds a, b and c to 1, 2 and 3 respectively.


Problem 8: 1000 digit number

18 10 2009

Find the largest product of 5 consecutive digits of a 1000 digit number

This can be solved very elegantly in Clojure, the 1000 digit number can be found here.

(def number-string "73167...")

(def digits (map #(- (int %) 48) number-string))

(apply max (map * digits (drop 1 digits) (drop 2 digits) (drop 3 digits) (drop 4 digits)))

number-string stores the 1000 digit number as a string

digits creates a list of digits from number-string, 48 is the ASCII value for the character ‘0’, 49 for ‘1’ and so on. Subtracting 48 from the character gives the digit value.

map runs only till one of the list arguments terminates so the last line is valid

Problem 7: Primes

17 10 2009

Find the 10001’st prime number

The prime numbers are intriguing, there is no pattern and no direct formula for the nth term in the series of primes. While an nth term formula would be enough for this problem, it would be far more useful to have an infinite, lazy list of primes like the fibonacci list in my earlier post.

The sieve of Eratosthenes is the one of the fastest way to find primes up to a given number. Implementing the essence of the sieve to get an infinite list was the goal.

Start of with an initial list of primes: ( 2 ) and a counter: n = 3
If none of the primes in the list divides n, add n to the list
increment n

Using this algorithm, we can implement an infinite list of primes easily but this turned out to be slow, far slower than I expected.

While searching for inspiration I came across this paper and one basic conclusion, my original implementation was not the sieve.

I tried implementing a large number of different algorithms including the sieve of Sundaram but none of them was fast enough. The sieve of Sundaram has an interesting method of finding primes. Instead of finding the primes themselves, it searches for the next odd composite.

This was the Eureka moment, I combined the concept of next odd composite with the Sieve of Eratosthenes and came up with this algorithm

Start with lc: last composite = 3, and a map of key value pairs {(9, 6)}
Remove the element from the list with the smallest key [(9, 6)]
store the key as nc: next composite and value as increment [nc = 9, increment = 6]
All odd numbers between lc and nc are prime
For each odd number, n, between lc and the  nc, insert (sqr(n), 2*n) into the map [(25, 10) (49, 14)]
lc = nc [lc = 9]
nc = nc + increment [nc = 15]
while nc exists as key in the map
    nc = nc + increment
insert (nc, increment) into the map [(15, 6)]
repeat from step 1 for next set of primes

Repeating the algorithm for 3 iterations

lc = 3                              map: {(9, 6)}
lc = 9          primes: 5, 7        map: {(15, 6), (25, 10), (49, 14)}
lc = 15         primes: 11, 13      map: {(21, 6), (25, 10), (49, 14), (121, 22), (169, 26)}

One thing which differentiates Clojure from other Lisps is the addition of powerful data structures as primitives. Clojure includes implementations for Vectors, Maps and Sets besides the usual List. [Clojure Data Structures]

Clojure also provides sorted versions of its Map and Set data type which make implementing a priority queue a breeze.

List           ()
Vector         []
Hash-Map       {}
Set           #{}

So here’s the implementation

(defn make-composite-cell [composite increment]
    [composite increment])

(defn get-composite [composite-cell]
    (first composite-cell))

(defn get-increment [composite-cell]
    (last composite-cell))

What I’ve done here is use a vector to abstract/hide away the implementation details for a new data type, composite-cell. Composite-cell is made up of 2 parts, a composite and an increment.

(defn insert-composite-cell [composite-cell composite-cell-queue]
    (let [composite (get-composite cell)
	  increment (get-increment cell)]
        (loop [new-composite composite]
		(contains? composite-cell-queue new-composite) (recur (+ new-composite increment))
		:else (assoc composite-cell-queue new-composite increment)))))

insert-composite-cell inserts a composite-cell into the priority queue, contains? checks to see if the key/priority already exists in the queue and assoc is used to add a new key-value pair to the queue.

(defn make-prime-system [last-composite composite-cell-queue]
    {:last-composite last-composite
      :composite-cell-queue composite-cell-queue})

(defn get-last-composite [prime-system]
    (:last-composite prime-system))

(defn get-composite-cell-queue [prime-system]
    (:composite-cell-queue prime-system))

Just like composite-cell, this uses the hash-table to implement a new data-type, prime-system. Prime system consists of the last-composite used and a list of composite-cells.

(def initial-prime-system 3 (sorted-map 9 6))

The initial prime system is the starting position for the algorithm

(defn get-primes [prime-system]
    (let [last-composite (get-last-composite prime-system)]
  	   next-composite (get-composite (first (get-composite-cell-queue prime-system)))]
        (range (+ last-composite 2) next-composite 2)))

get-primes returns a list of primes given by the given prime-system

(get-primes initial-prime-system)
=> (5 7)

And finally next-prime-system

(defn next-prime-system [prime-system]
    (let [primes (get-primes prime-system)
           queue (get-composite-cell-queue prime-system)
	   composite-cell (first queue)
	   composite (get-composite composite-cell)
	    increment (get-increment composite-cell)
	    queue (if (empty? primes)
			 (apply assoc (cons queue (concat (map #(list (* 2 %) (* % %)) primes)))))]
	(make-prime-system composite
		           (insert-composite-cell (make-composite-cell (+ composite increment)
		                                  (dissoc queue composite)))))

Most of the let bindings in this function are to reduce calculations or improve readability. The last binding on queue performs an additional operation. If no primes are generated for the prime-system, the same queue is returned, otherwise the primes are added to the queue.

assoc appends key value pairs to a hash-map

(assoc {:one 1} :two 2 :three 3)
=> {:one 1 :two 2 :three 3}

apply applies a function on a list just like reduce, except the list is taken at once.

(apply + '(1 2 3))
=> 6

Just like before, for the fibonacci numbers, we’ll create an infinite list of primes

(defn create-prime-list
	(lazy-cat '(2 3) (create-prime-list initial-prime-system)))
	(lazy-cat (get-primes prime-system) (create-prime-list (next-prime-system prime-system)))))

(def primes (create-prime-list))

The solution to the problem, the 10001’st prime number

(nth 10001 primes)

Problem 6: Sums of Squares of Sums

14 10 2009

Difference between sum of squares and square of sums

Find the difference between the sum of squares and the square of the sum of the integers 1 to 100

Using the functions map and reduce, this becomes trivial to implement

(defn sqr [x]
    (* x x))

(let [terms (range 1 101)]
    (- (reduce + (map sqr terms)) (sqr (reduce + terms))))

map takes a function and 1 or more lists and generates a new list of terms which are a result of the application of the function on each of the terms in the list/lists

(map + '(1 2 3) '(1 2 3))
=> (2 4 6)

Problem 5: Lowest Common Multiple

14 10 2009

Find the smallest number divisible by each of the numbers 1 to 20

The requirement is to find the Lowest Common Multiple (LCM)of the numbers 1 to 20

We can very easily find the LCM using the  Greatest Common Divisor (GCD) using the formula

lcm(x, y) = (x * y) / gcd(x, y)

A very fast method to calculate GCD is using Euclid’s algorithm

gcd(x, y) = gcd(y, x mod y)

Implementing this in Clojure

(defn gcd [x y]
	(zero? x) y
	(zero? y) x
	:else (recur y (mod x y))))

(defn lcm [x y]
    (/ (* x y) (gcd x y)))

(reduce lcm (range 1 21))

gcd calculates the greatest common divisor of 2 integers

(gcd 6 8 )
=> 2

lcm calculates the lowest common multiple of 2 integers

(lcm 6 8 )
=> 24

Problem 4: Numeric Palindromes

14 10 2009

Find the largest palindrome which is the product of 2, 3 digit numbers

The challenge is to find a numeric palindrome which is the product of 2 numbers, both from 100 to 999.

(defn reverse-int [n]
    (loop [m n acc 0]
       	    (zero? ) acc
	    :else (recur (quot m 10) (+ (* acc 10) (mod m 1))))))

(defn palindrome? [n]
    (= n (reverse-int n)))

(defn euler-4 [lower-limit upper-limit]
    (loop [p upper-limit q upper-limit largest 0]
	(let [candidate (* p q)]
		(< p lower-limit) largest
		(< candidate largest) largest
		(< lower-limit q) (recur (dec p) (dec p) largest)
                (palindrome? candidate)
  	  	    (if (> candidate largest)
			(recur p (dec q) candidate))
		:else (recur p (dec q) largest)))))

(euler-4 100 999)

let like loop, forms a dynamic binding between the odd and even terms in the argument list for the expression in the body of the let.

(let [a 3 b 4]
    (+ a b))
=> 4

if takes 2 – 3 expressions as arguments, if the first one evaluates to be True, then the second (then) is evaluated, else the third (else) is evaluated. In this case there is no else clause, the control breaks out of the if statement

(if (< 2 3)
=> 4

reverse-int takes an integer as argument and reverses it

(reverse-int 234)

palindrome? is a predicate which checks if an integer is a palindrome

(palindrome? 121)
=> True

There are 2 optimizations in this solution

1> Any 2 numbers are multiplied only once
2> If the largest palindrome found so far is larger than the current (* p q), return it

Problem 3: Prime Factor

13 10 2009

Find the largest prime factor of a composite number

The brute force method would be to find all the prime factors and choose the largest, a better algorithm is this one.

(defn divides? [n x]
    (zero? (mod n x)))

(defn largest-prime-divisor [n]
    (loop [x 2 m n]
	    (= x m) x
	    (divides? m x) (recur x (/ m x))
	    :else (recur (inc x) m))))

Clojure’s syntax takes a while getting used to but now I find it quite easy to express an algorithm in it. Lets trace what happens with a small value

(largest-prime-divisor 100)
(loop 2 100)
(loop 2 50)
(loop 2 25)
(loop 3 25)
(loop 4 25)
(loop 5 25)
(loop 5 5)
=> 5