Chapter 1, Building Abstractions with Procedures

Section - Procedures and the Processes They Generate

Exercise 1.27


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
#lang sicp

(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))

(define (carmichael-test num)
  (define (carmi-iter n a)
     (if (= n a)
         true
         (if (= (expmod a n n) a)
             (carmi-iter n (+ a 1))
             false
         )
     )
  )
  (carmi-iter num 1)
)

;> (carmichael-test 561)
;#t
;> (carmichael-test 1105)
;#t
;> (carmichael-test 1729)
;#t
;> (carmichael-test 2465)
;#t
;> (carmichael-test 2821)
;#t
;> (carmichael-test 6601)
;#t