Exercise 2.40: Define a procedure unique-pairs that, given an integer n, generates the sequence of pairs
\( (i,j) \) with \( 1\le j< i\le n \). Use unique-pairs to simplify the definition of prime-sum-pairs given
above. Using Miller-Rabin primality test as well as taking advantage of some lexical scoping here is the solution:
(define (prime? n times)
(define (miller-rabin-test n)
(define (random n) (random-integer n))
(define (expmod base exp m)
(define (square-mod x) (remainder (* x x) m))
(define (square-signal-root x)
(if (and
(not (or (= 1 x) (= x (- m 1))))
(= 1 (square-mod x)))
0
(square-mod x)))
(cond ((= exp 0) 1)
((even? exp)
(square-signal-root (expmod base (/ exp 2) m)))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
(define (try-it a)
(= (expmod a (- n 1) n) 1))
(try-it (+ 1 (random (- n 1)))))
(cond ((= times 0) #t)
((miller-rabin-test n) (fast-prime? n (- times 1)))
(else #f)))
(define (filter pred seq)
(cond ((null? seq) '())
((pred (car seq))
(cons (car seq) (filter pred (cdr seq))))
(else
(filter pred (cdr seq)))))
(define (range start end)
(define (iter end seq)
(if (> start end)
seq
(iter (- end 1) (cons end seq))))
(iter end '()))
(define (flatmap proc seq)
(define (accumulate fn init-value sequence)
(if (null? sequence)
init-value
(fn (car sequence)
(accumulate fn init-value (cdr sequence)))))
(accumulate append '() (map proc seq)))
(define (unique-pairs n)
(flatmap
(lambda (i)
(map (lambda (j) (list i j))
(range 1 (- i 1))))
(range 1 n)))
(define (prime-sum-pairs n)
(define (make-pair-sum pair)
(list (car pair) (cadr pair) (+ (car pair) (cadr pair))))
(define (prime-sum? pair)
(prime? (+ (car pair) (cadr pair)) 10))
(map make-pair-sum
(filter prime-sum?
(unique-pairs n))))
> (prime-sum-pairs 1)
()
> (prime-sum-pairs 2)
((2 1 3)
> (prime-sum-pairs 3)
((2 1 3) (3 2 5))
> (prime-sum-pairs 4)
((2 1 3) (3 2 5) (4 1 5) (4 3 7))
> (prime-sum-pairs 5)
((2 1 3) (3 2 5) (4 1 5) (4 3 7) (5 2 7))