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:

(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

$52 + 7 2 + 11 2 = 25 + 49 + 121 = 195$

respectively.

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

Output:

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

Output:

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