SICP in Clojure: Chapter 1, Exercise 28

This is my Clojure solution to Chapter 1, Exercise 28:

(ns sicp.ch1.ex28)

(defn square-check
  [n m]
  (let [r (rem (* n n) m)]
    (if (and (not (or (= 1 n) (= (- m 1) n)))
             (= 1 r))
      0 r)))

(defn expmod
  [base exp m]
  (cond (zero? exp) 1
        (even? exp) (square-check (expmod base (/ exp 2) m) m)
        :else       (rem (* base (expmod base (dec exp) m))
                         m)))

(defn miller-rabin-test
  [n]
  (letfn [(try-it [a]
            (= (expmod a n n) a))]
    (try-it (inc (rand-int (dec n))))))

(def primes [1009 1013 1019 10007 10009 10037 100003 100019 100043
             1000003 1000033 1000037])

(every? miller-rabin-test primes) ; => true

(def carmichael-numbers [561 1105 1729 2465 2821 6601])

(map miller-rabin-test carmichael-numbers) ; => sometimes false

SICP in Clojure: Chapter 1, Exercise 27

This is my Clojure solution to Chapter 1, Exercise 27:

(ns sicp.ch1.ex27
  (:require [sicp.ch1.ex25 :as sicp-ch1-ex25]))

(defn fermat-test
  [n a]
  (= (sicp-ch1-ex25/expmod a n n) a))

(defn fermat-full-test
  [n]
  (every? (partial fermat-test n) (range n)))

(def carmichael-numbers [561 1105 1729 2465 2821 6601])

(every? fermat-full-test carmichael-numbers) ; => true -- but not
                                        ; prime numbers!

SICP in Clojure: Chapter 1, Exercise 26

This is my Clojure solution to Chapter 1, Exercise 26:

(ns sicp.ch1.ex26)

;; By replacing the call to square with an explicit multiplication,
;; we've changed the resultant process from a linear recursive
;; process to a tree recursion which changes the running-time from
;; O(log n) to O(log 2^n) = O(n).