Exercise 1.33 of 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
> (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
Notice how coprime? binds n to itself.