# 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


$$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.