<< Previous exercise (1.26) | sicp-solutions | Next exercise (1.28) >>
To solve this exercise, we need to change fermat-test, making it test every integer number from 1 to n-1, not just a few random ones.
Then, we perform the test on Carmichael numbers and print whether the primality test has been fooled or not.
;; ex 1.27 (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)))) (define (full-fermat-prime? n) (define (iter a n) (if (= a n) true (if (= (expmod a n n) a) (iter (+ a 1) n) false))) (iter 1 n)) (define (test-fermat-prime n expected) (define (report-result n result expected) (newline) (display n) (display ": ") (display result) (display ": ") (display (if (eq? result expected) "OK" "FOOLED"))) (report-result n (full-fermat-prime? n) expected)) (test-fermat-prime 2 true) (test-fermat-prime 13 true) (test-fermat-prime 14 false) (test-fermat-prime 561 false) ; Carmichael number (test-fermat-prime 1105 false) ; Carmichael number (test-fermat-prime 1729 false) ; Carmichael number (test-fermat-prime 2465 false) ; Carmichael number (test-fermat-prime 2821 false) ; Carmichael number (test-fermat-prime 6601 false) ; Carmichael number
An alternative with no nested ifs:
(define (carmichel-test n) (define (iter a n) (cond ((and (= (expmod a n n ) a) (< a n)) (iter (+ a 1) n)) ((= a n) #t) (else #f))) (iter 1 n)) (carmichel-test 561) (carmichel-test 1105) (carmichel-test 1729) (carmichel-test 2465) (carmichel-test 2821) (carmichel-test 6601) ;; non-carmichel numbers to test if it works (carmichel-test 10) (carmichel-test 155) (carmichel-test 121)