[archives] [homepage]

## SICP Exercise 1.27

The `fermat-test` procedure has been modified to test using every single number from 1 to (n-1), rather than using random numbers. The procedure `prime?` stays to check whether the number actually is prime using the `smallest-divisor` method.

``````(define (carmichael n)
(and (fermat-test-all n) (not (prime? n))))

(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 (fermat-test-all n)
(define (try-it a)
(cond ((= a n) #t)
((= (expmod a n n) a) (try-it (+ a 1)))
(else #f)))
(try-it 1))

(define (square x)
(* x x))

(define (smallest-divisor n)
(find-divisor n 2))

(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))

(define (prime? n)
(= n (smallest-divisor n)))

(define (divides? a b)
(= (remainder b a) 0))
``````

Running the test on a few Carmichael numbers:

``````> (charmichael? 561)
#t
> (charmichael? 1105)
#t
> (charmichael? 1729)
#t
> (charmichael? 2465)
#t
> (charmichael? 2821)
#t
> (charmichael? 6601)
#t
``````