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)



One response

5 01 2015

Hi, you post interesting posts on your site, you deserve much more visitors, just search in google
for – augo’s tube traffic

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: