Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

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 <math>a^n</math> 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.

Personal tools