# sicp-ex-1.33

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

poly

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.

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

; so the accumulate can be:
(define (accumulate combiner null-value term a next b)
(filtered-accumulate (lambda (x) true)
combiner null-value term a next b))
```

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

cgb

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

ctz

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.