SICP Exercise 1.33

sicp

Question

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:

  1. the sum of the squares of the prime numbers in the interval \(a\) to \(b\) (assuming that you have a prime? predicate already written)
  2. 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\)).

Answer

(define (filtered-accumulate filter combiner null-value term a next b)
  (cond ((> a b) null-value)
        ((filter a)
         (combiner (term a)
                   (filtered-accumulate filter combiner null-value term (next a) next b)))
        (else
         (filtered-accumulate filter combiner null-value term (next a) next b))))

If the filter check is true, we run the combiner operation, if not, we do nothing and go to the next iteration.

Let us now solve the two problems stated in the question.

First, the sum of squares of the prime numbers:

(define (square x) (* x x))

(define (sum-of-squares-prime a b)
  (filtered-accumulate prime? + 0 square a inc b))

(sum-of-squares-prime 1 10)

And the result:

88

Next, all relative prime numbers to \(n\). An important thing to note here is that we use block notation to define the relative-prime? filter. It has to be done this way, because filter can only take a single parameter. If we had outsourced this function, it would need n as a second parameter.

(define (identity x) x)

(define (all-relative-primes n)
  (define (relative-prime? i)
    (= (gcd i n) 1))
  (filtered-accumulate relative-prime? * 1 identity 1 inc n))

(all-relative-primes 10)

Result:

189