weima learns to program

my attempt to do the exercises in sicp.

Sunday, June 29, 2008

sicp exercise 1.27

;  Exercise 1.27. Demonstrate that the Carmichael numbers listed in footnote 47 really do fool the Fermat
;  test. That is, write a procedure that takes an integer n and tests whether a^n is congruent to
;  a modulo n for every a<n, and try your procedure on the given Carmichael numbers.

(define (carmichael index)
(cond ((= index 1)  561)
((= index 2) 1105)
((= index 3) 1729)
((= index 4) 2465)
((= index 5) 2821)
((= index 6) 6601)
(else 0)))

(define (square num) (* num num))

(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m)) m))
(else
(remainder (* base (expmod base (- exp 1) m)) m))))

(define (prime-test n base )
(if (= (expmod base n n) base)(display "prime\n")))

(define (prime-carmichael-test num)
(define (prime-carmichael-test-impl base)
(cond ((= base num) 0)
(else (prime-test num base) (prime-carmichael-test-impl (+ base 1)))))
(prime-carmichael-test-impl 2))

(prime-carmichael-test (carmichael 1))(newline)
(prime-carmichael-test (carmichael 2))(newline)
(prime-carmichael-test (carmichael 3))(newline)
(prime-carmichael-test (carmichael 4))(newline)
(prime-carmichael-test (carmichael 5))(newline)
(prime-carmichael-test (carmichael 6))(newline)

; The Carmichael numbers are not prime numbers, but the Fermat test gives a very high probability of
; them being a prime.