SICP Exercise 1.33: Filtered Accumulator

From SICP section 1.3.1 Procedures as Arguments

Exercise 1.33 asks us to us to write an even more general form of the accumulate procedure that we wrote in 1.32. A filtered accumulate procedure should combine only those terms in a specified range that meet a specified condition. The new procedure will take the same arguments as the old one, plus an additional argument that specifies the filtering function.

Once we've written the new procedure we need to test it by using it to write two additional procedures. The first will find the sum of the squares of the prime numbers in a given range, and the second will find the product of all the positive integers less than n that are relatively prime to n.

The filtered-accumulate procedure should be very similar to what we saw in the last exercise. The only difference is that we check each new value to see if it passes through the filter before applying the combiner function.

(define (filtered-accum filter combiner null-value term a next b)
  (if (> a b)
      null-value
      (if (filter a)
          (combiner (term a)
                    (filtered-accum filter combiner null-value term (next a) next b))
          (filtered-accum filter combiner null-value term (next a) next b))))

Note that we're filtering on the value of a, not the value of (term a).

Sum of squared primes

We came up with several different ways to test if a number is prime in section 1.2.6. You can choose any implementation you like, but I'm going to use the fast-prime? procedure from exercises 1.22 and 1.23 (shown here in block structure).

(define (fast-prime? n)
   (define (smallest-divisor n)
      (define (find-divisor n test-divisor)
         (define (next x)
            (if (= x 2) 3 (+ x 2)))
         (define (divides? a b)
            (= (remainder b a) 0))
         (cond ((> (square test-divisor) n) n)
               ((divides? test-divisor n) test-divisor)
               (else (find-divisor n (next test-divisor)))))
      (find-divisor n 2))
   (= n (smallest-divisor n)))

Using fast-prime? as a filtering function, we can implement a procedure to sum the square of primes in a given range.

(define (sum-squared-primes a b)
   (filtered-accum fast-prime? + 0 square a inc b))

(define (inc x) (+ x 1))

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

We can use a few small examples to test with.

2² + 3² = 13
2² + 3² + 5² = 38
2² + 3² + 5² + 7² = 87

> (sum-squared-primes 2 3)
13
> (sum-squared-primes 2 6)
38
> (sum-squared-primes 2 10)
87

Procuct of coprimes

The second challenge was to find the product of all the positive integers less than n that are relatively prime (coprime) to n. In other words, multiply together all positive integers i < n such that

gcd(i, n) = 1

As luck would have it, we've already seen a gcd procedure too. SICP section 1.2.5 was all about finding greatest common divisors using Euclid's algorithm.

(define (gcd a b)
   (if (= b 0)
       a
       (gcd b (remainder a b))))

We can use gcd to define a coprime? procedure, and use that as our filter. Note that normally a coprime? procedure should take two parameters. Since filtered-accum expects the filter function to take only one parameter, coprime? is borrowing one of its input parameters, n, from product-of-coprimes.

(define (product-of-coprimes n)
  (define (coprime? i)
     (= 1 (gcd i n)))
  (filtered-accum coprime? * 1 identity 1 inc (- n 1)))

(define (identity x) x)

Again, I'm only going to test with a few small samples, since the results can potentially get very big, very fast. A quick mental check reveals that 3, 7, and 9 are the only values less than 10 that are also coprime to 10.

> (product-of-coprimes 10)
189

All values less than a prime number are coprime to that number, so the product of coprimes to 11 should result in the product of all the values from 2 to 10, or 10!.

> (product-of-coprimes 11)
3628800

You can check that and any other inputs with a calculator.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.