src/sicp/ex1_27.clj

   1 (ns sicp.ex1_27
   2   (:use [sicp utils]
   3         [clojure.contrib trace test-is]))
   4
   5 ;; exercise 1.27
   6 (comment
   7   "Some notes on Carmichael numbers: Carmichael numbers are those that fail
   8    Fermat little test. That is, for any n in the Carmichael set,
   9    (prime? n)      => false
  10    (fermat-test n) => true."
  11   )
  12 (defn brute-force-fermat-test [n]
  13   (try-all 2 n))
  14
  15 (defn try-all [a n]
  16   (cond (= a n) true
  17         (try-it a n) (try-all (inc a) n)
  18         :else false))
  19 (comment
  20   "all the given numbers pass the above test, i.e. for every a < n,
  21    a^n mod n === a mod n"
  22   user> (brute-force-fermat-test 561)
  23   true
  24   user> (brute-force-fermat-test 1105)
  25   true
  26   user> (brute-force-fermat-test 1729)
  27   true
  28   user> (brute-force-fermat-test 2465)
  29   true
  30   user> (brute-force-fermat-test 2821)
  31   true
  32   user> (brute-force-fermat-test 6601)
  33   true
  34   )