1 ;; Exercise 1.33.  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:
2 
3 
4 
5 (define (filtered-accumulate combiner filter null-value term a next b)
6   (if (> a b)
7       null-value
8       (if (filter a)
9 	  (combiner (term a)
10 		    (filtered-accumulate combiner filter null-value term (next a) next b))
11 	  (filtered-accumulate combiner filter null-value term (next a) next b))))
12 
13 (define (sum-prime-squares a b)
14   (filtered-accumulate + 
15 		       prime?
16 		       0
17 		       (lambda (x) (* x x))
18 		       a
19 		       1+
20 		       b))
21 
22 (define (smallest-divisor n)
23   (find-divisor n 2))
24 
25 (define (find-divisor n test-divisor)
26   (cond ((> (square test-divisor) n) n)
27         (( divides? test-divisor n) test-divisor)
28         (else (find-divisor n (+ test-divisor 1)))))
29 
30 (define (divides? a b)
31   (= (remainder b a) 0))
32 
33 (define (prime? n)
34   (= n (smallest-divisor n)))
35 
36 
37 ;; (define (accumulate combiner null-value term a next b)
38 ;;   (if (> a b)
39 ;;       null-value
40 ;;       (combiner (term a)
41 ;; 		(accumulate combiner null-value term (next a) next b))))
42 
43 ;; (define (sum term a next b)
44 ;;   (accumulate + 0 term a next b))
45 ;; (define (product term a next b)
46 ;;   (accumulate * 1 term a next b))
47 
48 
49 ;; (define (accumulate combiner null-value term a next b)
50 ;;   (if (> a b)
51 ;;       null-value
52 ;;       (combiner (term a)
53 ;; 		(accumulate combiner null-value term (next a) next b))))
54 
55 ;; (define (accumulate-iter combiner null-value term a next b)
56 ;;   (define (iter i result)
57 ;;     (if (> a b)
58 ;; 	result
59 ;; 	(iter (next i) (combiner (term i) result))))
60 ;;   (iter a null-value))
61 
62 
63 ;; (define (factorial n)
64 ;;   (product (lambda (x) x)
65 ;; 	   1
66 ;; 	   (lambda (x) (+ x 1))
67 ;; 	   n))
68 
69 ;; (define (factorial-iter n)
70 ;;   (product-iter (lambda (x) x)
71 ;; 		1
72 ;; 		(lambda (x) (+ x 1))
73 ;; 		n))
74 
75 ;; pi/4 = 2*4*4*6*6*8*...
76 ;;        ---------------
77 ;;        3*3*5*5*7*7*...
78 
79 ;; (define (pi iterations)
80 ;;   (* 4.0
81 ;;      (product (lambda (x)
82 ;; 		(if (odd? x)
83 ;; 		    (/ (+ x 1) (+ x 2))
84 ;; 		    (/ (+ x 2) (+ x 1))))
85 ;; 	      1
86 ;; 	      (lambda (x) (+ x 1))
87 ;; 	      iterations)))
88 
89 (define (test-case actual expected)
90   (load-option 'format)
91   (newline)
92   (format #t "Actual: ~A Expected: ~A" actual expected))
93 
94 ;; (test-case (factorial 0) 1)
95 ;; (test-case (factorial 1) 1)
96 ;; (test-case (factorial 2) 2)
97 ;; (test-case (factorial 3) 6)
98 ;; (test-case (factorial 4) 24)
99 ;; (test-case (factorial 5) 120)
100 ;; (test-case (factorial 6) 720)
101 ;; (test-case (factorial 7) 5040)
102 ;; (test-case (factorial-iter 7) 5040)
103 
104 ;; (test-case (pi 10000) 3.1415)
105 
106 ;; 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)
107 
108 ;; 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). 
109 
110 (test-case (sum-prime-squares 2 17) 666)
111 
112 (define (relatively-prime-product n)
113   (filtered-accumulate * 
114 		       (lambda (i)
115 			 (= (gcd i n) 1))
116 		       1
117 		       (lambda (x) x) 
118 		       1
119       		       1+ 
120 		       n))
121 
122 (define (gcd a b)
123   (if (= b 0)
124       a
125       (gcd b (remainder a b))))
126 
127 (test-case (relatively-prime-product 20) 8729721)