## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 1.33

## Problem

You can obtain an even more general version of `accumulate` (see 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)

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

## Solution

Here's a filtered `accumulate` procedure that generates an iterative process:

(define (filtered-accumulate combiner null-value predicate term a next b) (define (iter a result) (if (> a b) result (iter (next a) (if (predicate a) (combiner (term a) result) result)))) (iter a null-value))

Here's the requested solution to part a. of the problem, including all necessary helper functions, all of which have been defined in previous exercises or in the text:

(define (square x) (* x x)) (define (smallest-divisor n) (find-divisor n 2)) (define (divides? a b) (= (remainder b a) 0)) (define (find-divisor n test-divisor) (cond ((> (square test-divisor) n) n) ((divides? test-divisor n) test-divisor) (else (find-divisor n (next test-divisor))))) (define (next n) (if (= n 2) 3 (+ n 2))) (define (prime? n) (= n (smallest-divisor n))) (define (inc n) (+ n 1)) (define (sum-of-squares-of-primes a b) (filtered-accumulate + 0 prime? square a inc b))

Here are some tests for intervals [1, 10] and [4, 11]. Their answers should be

1 + 2^{2} + 3^{2} + 5^{2} + 7^{2} = 1 + 4 + 9 + 25 + 49 = 88

and

5^{2} + 7^{2} + 11^{2} = 25 + 49 + 121 = 195

respectively.

(sum-of-squares-of-primes 1 10)

*Output:*

`
`

88

(sum-of-squares-of-primes 4 11)

*Output:*

`
`

195

Those answers are correct.

Here's the requested solution to part b., using the `gcd` procedure from exercise 1.20:

(define (identity n) n) (define (gcd a b) (if (= b 0) a (gcd b (remainder a b)))) (define (product-of-relative-primes n) (define (relatively-prime-to-n? a) (= (gcd a n) 1)) (filtered-accumulate * 1 relatively-prime-to-n? identity 2 inc (- n 1)))

And a couple of tests using *n* = 8, 4 and 9. The answers should be

and

respectively.

(product-of-relative-primes 8)

*Output:*

`
`

105

(product-of-relative-primes 4)

*Output:*

`
`

3

(product-of-relative-primes 9)

*Output:*

`
`

2240

Done.