sicp-ex-1.27

<< 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:

 ;; Parse error: Spurious closing paren found
(define (carmichel-test n)
  (define (iter a n)
    (cond ((= a n) #t)
          ((expmod a n n ) a) (iter (+ a 1) n))
          (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)

 (define (car-test n) 
   (define (car-test-iter n a) 
     (cond ((or (= n 1) (= n 0)) false) 
           ((= a n) true) 
           ((not (= (expmod a n n) (remainder a n))) false) 
           (else (car-test-iter n (+ a 1))))) 
   (car-test-iter n 1)) 
  
 (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 (square x) (* x x)) 
  
 ;; testing on Carmichael numbers 
 (car-test 561) 
 (car-test 1105) 
 (car-test 1729) 
 (car-test 2465) 
 (car-test 2821) 
 (car-test 6601) 
  
 ;; testing on 1 and random numbers <100,000,000 (courtesy of random.org) 
 (car-test 1) 
 (car-test 85230658) 
 (car-test 13828192) 
 (car-test 69911818) 
 (car-test 49141805) 
 (car-test 29170450)