<< Previous exercise (1.32) | sicp-solutions | Next exercise (1.34) >>

a. The filtered_accumulate procedure is not optimized at all.. We'll use the *prime?* procedure defined earlier in the book with a small fix to make (prime? 1) -> #f.

(define (smallest-div n) (define (divides? a b) (= 0 (remainder b a))) (define (find-div n test) (cond ((> (sq test) n) n) ((divides? test n) test) (else (find-div n (+ test 1))))) (find-div n 2)) (define (prime? n) (if (= n 1) false (= n (smallest-div n))))

Filtered accumulate procedure:

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

A slightly dryer recursive version:

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

And an iterative version:

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

a. Sum of squares of prime numbers procedure:

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

Test example: (sum-of-prime-squares 1 5)

ans. 38

b. Product of all positive integers les than n that are relatively prime to n

(define (gcd m n) (cond ((< m n) (gcd n m)) ((= n 0) m) (else (gcd n (remainder m n))))) (define (relative-prime? m n) (= (gcd m n) 1)) (define (product-of-relative-primes n) (define (filter x) (relative-prime? x n)) (filtered-accumulate * 1 identity 1 inc n filter))

Example: (product-of-relative-primes 10) 189

a way to avoid code repetition both in the recursive and in the iterative version is to add a conditional in the first term of combiner. This way there is no need to call two versions of filtered-accumulate. The recursive version will be:

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

And the iterative version:

```
(define (filtered-accumulate combiner null-value term a next b filter)
(define (iter a result)
(if (> a b)
result
(iter (next a) (combiner result
(if (filter a)
(term a)
null-value)))))
(iter a null-value))
```

An alternative way making use of the accumulate procedure before:

```
(define (filtered-accumulate filter comb null-val term a next b)
(define (filtered-term k)
(if (filter k) (term k) null-val))
(accumulate comb null-val filtered-term a next b))
```

@poly: I don't see the point of defining accumulate in terms of filtered-accumulate.

We require the product of positive integers less than n, so the result should avoid multiplying by n.

```
(define (product-gcd n)
(define (gcd-filter x)
(gcd x n))
(filtered-accumulate * 1 identity 1 inc (- n 1) gcd-filter))
```

the solutions above:

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

There is no need to combine null-value with the later accumulating actually.

BTW: I can't stand the indent of the above guy's codes.