SICP exercise 1.33

From Drewiki

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:

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:

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

1 + 2² + 3² + 5² + 7² = 1 + 4 + 9 + 25 + 49 = 88

and

5² + 7² + 11² = 25 + 49 + 121 = 195

respectively.

Output:

88

Output:

195

Those answers are correct.

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

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

and

respectively.

Output:

105

Output:

3

Output:

2240

Done.