## 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 + 22 + 32 + 52 + 72 = 1 + 4 + 9 + 25 + 49 = 88

and

52 + 72 + 112 = 25 + 49 + 121 = 195

respectively.

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

Output:

88

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

Output:

195


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

$1\cdot3\cdot5\cdot7 = 105$

$1\cdot3 = 3$

and

$1\cdot2\cdot4\cdot5\cdot7\cdot8 = 2240$

respectively.

(product-of-relative-primes 8)

Output:

105

(product-of-relative-primes 4)

Output:

3

(product-of-relative-primes 9)

Output:

2240


Done.