SICP exercise 1.27

From Drewiki

Jump to: navigation, search

Problem

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

Solution

Here is a procedure to perform the Fermat test on all numbers a<n. It returns #t if n passes the test, #f otherwise. 

(define (complete-fermat-test n)
  (complete-fermat-test-helper n (- n 1)))
 
(define (complete-fermat-test-helper n a)
  (cond ((= a 0) #t)
        ((fermat-test n a) (complete-fermat-test-helper n (- a 1)))
        (else #f)))
 
(define (fermat-test n a)
  (= (expmod a n n) a))
 
(define (square x) (* x x))
 
(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))))

Tests: 

(complete-fermat-test 1)

Output: 

#t

(complete-fermat-test 2)

Output: 

#t

(complete-fermat-test 3)

Output: 

#t

(complete-fermat-test 4)

Output: 

#f

(complete-fermat-test 5)

Output: 

#t

(complete-fermat-test 6)

Output: 

#f

(complete-fermat-test 7)

Output: 

#t

(complete-fermat-test 109)

Output: 

#t

(complete-fermat-test 111)

Output: 

#f


Now check some Carmichael numbers: 

(complete-fermat-test 561)

Output: 

#t

(complete-fermat-test 1105)

Output: 

#t

(complete-fermat-test 1729)

Output: 

#t

(complete-fermat-test 2465)

Output: 

#t

(complete-fermat-test 2821)

Output: 

#t

(complete-fermat-test 6601)

Output: 

#t


Credits

Thanks to Ryan Davis for reporting a bug in the original solution; complete-fermat-test-helper was not recursing.

Retrieved from "http://wiki.drewhess.com/wiki/SICP_exercise_1.27"
Personal tools