Exercise 1.33 of SICP

2009-07-03

sicp

Exercise 1.33: You can obtain an even more general version of accumulate (exercise 1.32) by introducing the notion of a filter on the terms to be combined. That is, combine only those terms derived from values in the range that satisfy a specified condition. The resulting filtered-accumulate abstraction takes the same arguments as accumulate, together with an additional predicate of one argument that specifies the filter. Write filtered-accumulate as a procedure. Show how to express the following using filtered-accumulate:

a. the sum of the squares of the prime numbers in the interval a to b (assuming that you have a prime? predicate already written)

(define (smallest-divisor n)
  (find-divisor n 2))
(define (find-divisor n test-divisor)
  (define (square x) (* x x))
  (cond ((> (square test-divisor) n) n)
   	((divides? test-divisor n) test-divisor)
	(else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
  (= (remainder b a) 0))

(define (prime? n)
  (= n (smallest-divisor n)))

(define (filtered-accumulator pred? combiner null-value term a next b)
  (cond ((> a b) null-value)
   	((pred? a)
	 (combiner (term a) 
	   (filtered-accumulator pred? combiner null-value term (next a) next b)))
	(else
	  (filtered-accumulator pred? combiner null-value term (next a) next b))))

(define (sum-of-prime-squares a b)
  (define (square x) (* x x))
  (define (next x) (+ 1 x))
  (filtered-accumulator prime? + 0 square a next b))

> (sum-of-prime-squares 2 10)
87

$$ 2^2+3^2+5^2+7^2 = 4+9+25+49=89 $$

> (sum-of-prime-squares 2 20)
1027

b. the product of all the positive integers less than n that are relatively prime to n (i.e., all positive integers i < n such that GCD(i,n) = 1).

(define (filtered-accumulator pred? combiner null-value term a next b)
  (cond ((> a b) null-value)
   	((pred? a)
	 (combiner (term a) 
	   (filtered-accumulator pred? combiner null-value term (next a) next b)))
	(else
	  (filtered-accumulator pred? combiner null-value term (next a) next b))))

(define (gcd a b)
  (if (= b 0)
    a
    (gcd b (remainder a b))))

(define (product-of-coprimes i n)
  (define (coprime? a)
	(= (gcd n a) 1))
  (define (identity x) x)
  (define (next x) (+ 1 x))
  (filtered-accumulator coprime? * 1 identity i next n))

> (product-of-coprimes 2 10)
189

$$ 3\cdot7\cdot9=189 $$

Notice how coprime? binds n to itself.

Contents