1.27|

$ cd ~

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