(define (f-iter n a b c i)
  (if (= (+ 1 n) i)
      a
      (f-iter n (+ a b b c c c) a b (+ 1 i))
      )
  )

(define (f n) (if (< n 3) 1 (f-iter n 1 1 1 3)))

; Exercise 1.11
(define (f n)
    (if (< n 3) n
        (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))


(define (g n)
    (g-iter 2 1 0 n))

(define (g-iter a b c count)
  (if (< count 3) a
      (g-iter (+ a (* 2 b) (* 3 c)) a b (- count 1))))

; Exercise 1.12

(define (pascals-triangle row col)
  (cond ((or (= col 0) (> col row)) 0)
        ((= col row ) 1)
        ((= row 1) 1)
        (else (+ (pascals-triangle (- row 1) (- col 1))
                 (pascals-triangle (- row 1) col)))))
 

; Exercise 1.16
(define (fast-iter-exp b n)
  (iter b n 1))

(define (iter b n a)
  (cond ((= n 0) a)
        ((even? n) (iter (square b) (/ n 2) a))
        (else (* b (iter b (- n 1) a)))))

; Exercise 1.17
(define (double n)
  (+ n n))

(define (halve n)
  (/ n 2))

(define (* a b)
  (cond ((= b 0) 0)
        ((even? b) (* (double a) (halve b)))
        (else (+ a (* (double a) (halve (- b 1)))))))

; Exercise 1.27
(define (square x) (* x x)) 
  
(define (expmod base exp m) 
  (cond ((= exp 0) 1) 
        ((even? exp) 
         (remainder (square (expmod base (/ exp 2) m)) m)) 
        (else 
          (remainder (* base (expmod base (- exp 1) m)) m))))         
  
(define (fermat-test n)
  (define (fermat-iter n a)
    (cond ((= n a) #t)
          ((= (expmod a n n) a ) (fermat-iter n (+ a 1)))
          (else #f)))
  (fermat-iter n 1))

;The Carmichael numbers do not fool it. So something is wrong.

;Exercise 1.10. 
(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))


;Exercise 1.11. 
(define (ex1p11r n)
  (cond ((< n 3) n)
        (else (+ (ex1p11r (- n 1))
                 (* 2 (ex1p11r (- n 2)))
		 (* 3 (ex1p11r (- n 3)))))))		 


(define (ex1p11i n)
(if (< n 3) n	
  (ex1p11-iter 0 1 2 n)))

(define (ex1p11-iter a b c count)
  (if (= count 2)
      c
      (ex1p11-iter b c (+ c (* 2 b) (* 3 a)) (- count 1))))


Exercise 1.12. 
(define (pascal r c)
(cond ((= c 1) 1)
((= r c) 1)
(else (+ (pascal (- r 1) c) (pascal (- r 1) (- c 1))))))



(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
   (if (not (> (abs angle) 0.1))
       angle
       (p (sine (/ angle 3.0)))))


;Exercise 1.17. 
(define (double x)(* x 2))
(define (halve x)(/ x 2))
(define (fast-mult a b)
  (cond ((= a 0) 0)
        ((even? a) (double (fast-mult (/ a 2) b)))
        (else (if (> a 0) (+ b (fast-mult (- a 1) b))
		  (- (fast-mult (+ a 1) b) b)))))

;1.19
(define (fib n)
  (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   (+ (* p p)   (* q q))      ; compute p'
                   (+ (* 2 p q) (* q q))      ; compute q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))


;exercise 1.21 
(define (square x) (* x x))
(define (smallest-divisor n)
  (find-divisor n 2))
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
  (= (remainder b a) 0))

;1.9
(+ 4 5)
((inc (+ (4-1) 5))))
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5))))
(inc (inc (inc (inc (5))))))
(inc (inc (inc (6))))
(inc (inc 7)))
(inc 8))
9
This is recursive

and

(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9
This is iterative

; 1.11
; Recursive
(define (f n)
  (cond ((< n 3) 3)
        (else (+ (f (- n 1)) 
                 (* 2 (f (- n 2))) 
                 (* 3 (f (- n 3)))))))


; Iterative
(define (f2 n)
  (f-iter 3 3 3 n))

(define (f-iter a b c count)
  (if (= count 0)
      c
      (f-iter (+ a (* 2 b) (* 3 c)) a b (- count 1))))


1.17
(define (double n) 
  (+ n n))

(define (half n) 
  (/ n 2))

(define (even2? n) 
  (= (remainder n 2) 0))

(define (fast* a b)
  (cond ((= a 0) 0)
        ((= b 0) 0)
        ((even2? b) (fast* (double a) (half b)))
        (else (+ a (fast* a (- b 1))))))

1.19
(define (fib n) 
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count) 
  (cond ((= count 0) b)
        ((even? count) 
         (fib-iter a
                   b
                   (+ (* p p) (* q q ))  ; compute p'
                   (+ (* 2 p q) (* q q)) ; compute q'
                   (/ count 2))) 
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q)) 
                        p
                        q
                        (- count 1)))))

1.27
(define (expmod base exp m) 
  (cond ((= exp 0) 1)
        ((even? exp) 
         (remainder (square (expmod base (/ exp 2) m)) m))
        (else (remainder (* base (expmod base (- exp 1) m)) m))))

(define (fermat-test-all n)
  (define (try-it a)
    (not (= (expmod a n n) a)))
  
  (define (fermat-iter n count)
    (cond ((= n count) (= 1 0))
          ((try-it count) (= 1 1))
          (else (fermat-iter n (+ count 1)))))
  
  (fermat-iter n 2))
  
; Returns true if any numbers satisfy Fermat's Test
; Sanity Check
(display "150 ")
(fermat-test-all 150)

; Carmichael numbers
(display "561 " )
(fermat-test-all 561)

(display "1105 ")
(fermat-test-all 1105)

(display "1729 ")
(fermat-test-all 1729)

(display "2465 ")
(fermat-test-all 2465)

(display "6601 ")
(fermat-test-all 6601)

Output:
150 #t
561 #f
1105 #f
1729 #f
2465 #f
6601 #f
          

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex1.9
;;
;;Procedure 1
(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

;;This is O(a) in time and space, and is thus recursive

;;Procedure 2
(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9

;;This is O(a) in time and O(1) in space.  Iterative

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex1.10

(A 1 10)
(A 0 (A 1 9))
(A 0 (A 0 (A 1 8)))
.
.
.
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2^2))))))))
.
.
.
2^10
1024

(A 2 4)
(A 1 (A 2 3))
2^(A 2 3)
2^(A 1 (A 2 2))
2^(2^(A 2 2))
2^(2^(A 1 (A 2 1)))
2^2^2^2
65536
;; We will write this function at f(2,n) = 2_1^2_2^...^2_n so it becomes
f(2 4)
(A 3 3)
(A 2 (A 3 2))
f(2 (A 3 2))
f(2 (A 2 (A 3 1)))
f(2 f(2 (A 3 1)))
f(2 f(2 2)))
(2^2^...^2_(2^2))
(2^2^2^2)
65536

;;(f n) computes 2n
;;(g n) computes 2^n
;;(h n) computes 2\{up_arrow}^{2}n or the tetration of m with n

;;The function given here is slightly different than Ackermann's
;;function seen elsewhere (check wolfram and wiki) but seems cleaner

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.11

;;Recursive
(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1))
         (* 2 
            (f (- n 2)))
         (* 3
            (f (- n 3))))
      )
  )


;;Iterative
(define (f_iter n)
  (define (f_n fn-1 fn-2 fn-3)
      (+ fn-1
         (* 2
            fn-2)
         (* 3
            fn-3)))
  (define (iter fn-1 fn-2 fn-3 count)
    (if (= count n)
        (f_n fn-1 fn-2 fn-3)
        (iter (f_n fn-1 fn-2 fn-3)
              fn-1
              fn-2 (inc count))))
  (if (< n 3)
      n
      (iter 2 1 0 3)))

;;For n = 20, the recursive program can almost keep up, but for anything
;;over that, the difference is obvious, and by n = 50 they are
;;remarkable.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.12

(define (pascal row element)
  (if (or (= element 1) (= row element))
      1
      (+ (pascal (dec row)
                 (dec element))
         (pascal (dec row)
                 element))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.13

;;Fib(N) = \frac{\phi^N-\psi^N }{\sqrt{5}} clearly holds for Fib(0) and
;;Fib(1).  Now checking Fib(N) = Fib(N-1)+Fib(N-2), Fib(N) =
;;\frac{\phi^{N-1}-\psi^{N-1}}{\sqrt{5}}+\frac{\phi^{N-2}-\psi^{N-2}}{\sqrt{5}}
;;= \frac{(\phi^{N-1}+\phi^{N-2})-(\psi^{N-1}+\psi^{N-2})}{\sqrt{5}}.  As
;;\psi and \phi are both roots of the equation x^2-x-1 = 0, we can
;;multiply by x^{N-2} and rearrange to get x^N = x^{N-1} + x^{N-2}, thus
;;showing:
;;\frac{\phi^N-\psi^N }{\sqrt{5}} =
;;\frac{\phi^{N-1}-\psi^{N-1}}{\sqrt{5}}+\frac{\phi^{N-2}-\psi^{N-2}}{\sqrt{5}}.

;;Now, as \abs{\psi}<1, \abs{\frac{\psi}{\sqrt{5}}}<\frac{1}{2}.  As
;;\abs{\phi^N} is a positive decreasing function, for all N,
;;\frac{\psi^N}{\sqrt{5}}< \frac{1}{2}.  Thus \frac{\phi^N}{\sqrt{5}} is
;;the closest integer to Fib(N) and we can calculate Fib(N)  by
;;rounding this function.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.14

;;The tree diagram is large enough that I think I will skip drawing it
;;here.  I originally throught that this was O(e^amount) in time as the
;;branches approximately double each step.  However, Bill the Lizard gives
;;a nice discussion of this on his blog in which he shows that the
;;branching is moderated by the number of coins available, and thus,
;;exponential in that.  The program is actually O(amount^5).  In space is
;;is O(amount)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.15

;;a. 12.15/3^5 = 0.05 so (p x) is called 5 times.

;;b. Angle/3^n ~0.1, so n~ ln(angle/0.1/3).  Thus n~ln(angle).  As n
;;counts both the number of steps and the number of calls to (p x), this
;;program is O(log(angle)) in space and time.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.16

;;We define the transform a b n (n even)-> a (square b) (/ n 2)
;;				(n odd)-> (* b a) b (dec n)
;;This preserves the product a*b^n and will give us an process which is
;;O(1) in space and still O(log(n)) in time.

(define (exp-iter base exp)
  (define (iter a b n)
    (cond ((= n 0) a)
          ((even? n)
           (iter a (square b) (/ n 2)))
          (else (iter (* b a) b (dec n)))))
  (iter 1 base exp))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.17

(define (fast-mult a b)
  (cond ((= b 1) a)
        ((even? b)
         (double (fast-mult a (halve b))))
        (else (+ a (fast-mult a (- b 1))))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.18

;; For state variables a b c, equation of state is ab+c and the
transform is 
;;		 a b c (b even)-> (double a) (halve b) c
;;		 a b c (b odd)-> a (dec b) (+ c a)

;; do this until (= b 1) and return (+ a c)

(define(fast-mult-iter a b)
  (define (iter x y z)
    (cond ((= y 1) (+ x z))
          ((even? y) (iter (double x) (halve y) z))
          (else (iter x (dec y) (+ z x)))))
  (iter a b 0))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.19

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   (+ (square p) (square q))
                   (+ (square q) (* 2 p q))
                   (/ count 2)))
        (else (fib-iter (+ (* b p) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

;;Admittedly, I don't really understand this transformation.  Does
;;anyone have any insight into this?

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.20

;;Normal-order
(gcd 206 40)
(gcd 40 (remainder 206 40))
(remainder 206 40)->6
(gcd (remainder 206 40)
     (remainder 40 (remainder 206 40)))
(remainder 40 (remainder 206 40))->4
(gcd (remainder 40 (remainder 206 40))
     (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
(remainder (remainder 206 40)
           (remainder 40 (remainder 206 40)))->2
(gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
     (remainder (remainder 40 (remainder 206 40))
                (remainder (remainder 206 40)
		           (remainder 40 (remainder 206 40))))
(remainder (remainder 40 (remainder 206 40))
           (remainder (remainder 206 40)
           (remainder 40 (remainder 206 40))))->0
(remainder (remainder 206 40)
	   (remainder 40 (remainder 206 40)))->2
;;Counting up the (remainder ) calls gives 18

;;Applicative order

(gcd 206 40)
(gcd 40 (remainder 206 40))
(gcd 40 6)
(gcd 6 (remainder 40 6))
(gcd 6 4)
(gcd 4 (remainder 6 4))
(gcd 4 2)
(gcd 2 (remainder 4 2))
(gcd 2 0)
2

;;That's 4 calls

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.21

> (smallest-divisor 199)
199
> (smallest-divisor 1999)
1999
> (smallest-divisor 19999)
7
> (/ 19999 7)
2857

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.22

(define (search-for-primes a b)
  (cond ((> a b) )
        ((even? a) (if (= a 2)
		     ((timed-prime-test a) (search-for-primes (+ a 1) b))
		     (search-for-primes (+ a 1) b)))
        (else (timed-prime-test a)
              (search-for-primes (+ a 2) b))))

;;Editted to pull just the primes

> (search-for-primes 1000 1020)

1009 *** 15
1013 *** 14
1019 *** 14done
(/ (+ 15 14 14) 3)
14.33

(search-for-primes 10000 10100)

10007 *** 42
10009 *** 42
10037 *** 41
(/ (+ 42 42 41) 3)
41.67

(search-for-primes 100000 100050)

100003 *** 125
100019 *** 128
100043 *** 126
(/ (+ 125 128 126) 3)
126.33

(search-for-primes 1000000 1000050)

1000003 *** 407
1000033 *** 396
1000037 *** 395
(/ (+ 407 396 395) 3)
399.33

;;Given that this program grows O(sqrt(n)), we would expect our times to
;;increase as sqrt(10) with each step.  Checking this as a fractional
;;difference from sqrt(10), t_10n/t_n~sqrt(10) so the fractional
;;difference is 1-t_10n/(sqrt(10)t_n).

;;10000/1000    1-41.33/(sqrt(10)14.67)=0.11

;;100000/10000  1-126.33/(sqrt(10)41.33)=0.03

;;1000000/100000  1-399.33/(sqrt(10)126.33)=0.0004

;;These are all shorter than the O(sqrt(n)) however as n increases,
;;agreement improves.  As the O(sqrt(n)) part of our program grows
;;larger, it dominates over smaller terms, giving better agreement.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex. 1.23

(define (next n)
  (if (= n 2)
      3
      (+ n 2)))

;;Pluging this in gives:
> (search-for-primes 1000 1020)

1009 *** 12
1013 *** 11
1019 *** 11
(/ (+ 12 11 11) 3)
11.33

> (search-for-primes 10000 10050)

10007 *** 28
10009 *** 28
10037 *** 28
28

> (search-for-primes 100000 100050)

100003 *** 84
100019 *** 90
100043 *** 82
(/ (+ 84 90 82) 3)
85.33

> (search-for-primes 1000000 1000040)

1000003 *** 256
1000033 *** 272
1000037 *** 251
(/ (+ 256 272 251) 3)
259.67

;;With the answers from the last question, the ratios between the times of
;;the two programs are:

;;1000
(/ 14.33 11.33)
1.26

;;10000
(/ 41.67 28)
1.49

;;100000
(/ 126.33 85.33)
1.48

;;1000000
(/ 399.33 259.67)
1.54

;;These are all substantially less than 2. I suppose it is that we also
;; added n/2 function calls

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex. 1.24

;;This gave

1009 *** 44
1013 *** 48
1019 *** 46
	 46
10007 *** 60
10009 *** 52
10037 *** 54
	  55.33
100003 *** 59
100019 *** 60
100043 *** 62
	   60.33
1000003 *** 66
1000033 *** 71
1000037 *** 68
	    68.33

;;Given that the procedure displays O(log n) growth, I would expect each
;;of these to differ by a constant value which is approximately what we
;;see.  Times for 1000000 and 1000 should differ by O(log 1000), or
;;1000000 should be approximately twice the time we see for 1000.  As at
;;1000, lower terms contribute much more than they do at 1000000, The
;;ratio between them should be slightly less than two, which is what we
;;observe.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex. 1.25

While this procedure will work, it will be far from fast.  The remainder
calls which I believe grow in time with O(n) will be to the result of
the exponent rather than multiple calls to a value mod m.  This will
cause the program to slow down significantly.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex. 1.26

Louis's program will evaluate (expmod base (/ exp 2) m) twice.  Thus,
while in the original program we were halving out work each time, in
Josh's implementation we are preceding to do that work twice, and we end
up with a process that grows with O(n).

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex. 1.27


(define (carmichael-test n)
  (define (check-iter m)
    (cond ((= m n) true)
          ((= (expmod m n n) m) (check-iter (+ m 1)))
          (else false)))
  (check-iter 1))


> (carmichael-test 561)
#t
> (carmichael-test 1105)
#t
> (carmichael-test 1729)
#t
> (carmichael-test 2465)
#t
> (carmichael-test 2821)
#t
> (carmichael-test 6601)
#t

Exercise 1.11
(define (f n)  (cond ((< n 3) n)
        (else (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3)))))))

(f 4)

(define (fi n)
  (iter-f 2 1 0 n))
 
(define (iter-f n nmo nmt ind)
  (cond ((< ind 3) n)
        (else (iter-f (+ n (* 2 nmo) (* 3 nmt)) n nmo (- ind 1))))
  )

(fi 4)

;State is held in args

Exercise 1.17
(define (fast-mul a b addr)  (cond ((= b 1) (+ a addr))
        ((= b -1) (+ a addr))
        ((even b) (fast-mul (double a) (half b) addr))
        (else (fast-mul a (- b 1) (+ addr a)))))

(define (half n)
  (/ n 2))

(define (double n)
  (* n 2))

(define (even n)
  (= (remainder n 2) 0))

(fast-mul 64 64 0)

Exercise 1.23
(define (square n)  (* n n))

(define (next n)
  (cond ((= n 2) 3)
        (else (+ n 2))))

Results were the same but again cannot verify time or difference.

Exercise 1.27
(define (square n)  (* n n))

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))     


(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (define (fermat-iter a)
    (cond ((= a 0) #f)
          ((not (try-it a)) #t)
          (else (fermat-iter (- a 1)))))
  (fermat-iter (- n 1)))

(fermat-test 4)
(fermat-test 561)
(fermat-test 1105)
(fermat-test 1729)
(fermat-test 2465)
(fermat-test 6601)

1.11

recursive:

(define (f n)
(if (< n 3) n 
(+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3)))))
)

iterative:

(define (f-iter count sum1 sum2 sum3)
(cond ((= count 0) sum1)
(else (f-iter (- count 1) (+ sum1 (* 2 sum2) (* 3 sum3)) sum1 sum2)))
)

(define (f n)
(cond ((= n 0) 0)
((= n 1) 1)
((= n 2) 2)
(else (f-iter (- n 2) 2 1 0)))
)

;1.9
inc(+ 4 5)
inc(inc(+ 3 5))
inc(inc(inc(+ 2 5)))
inc(inc(inc(inc(+ 1 5))))
inc(inc(inc(inc(inc(0 5)))))
inc(inc(inc(inc(5))))
inc(inc(inc(6)))
inc(inc(7))
inc(8)

;1.11
(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1))
	 (* 2 (f (- n 2)))
	 (* 3 (f (- n 3))))))

;1.13
;Skipped this one

;1.15, part a
;p will be applied 5 times
(sine 12.15)
(p (sine 4.05))
(p (p (sine 1.35)))
(p (p (p (sine 0.45))))
(p (p (p (p (sine 0.15)))))
(p (p (p (p (p (sine 0.05))))))

;1.15, part b
;Growth in space = a^(1/3)
;Growth in steps = 2*a^(1/3)

;1.17
;Not sure...

;1.19
;Skipped

;1.21
;199: 199
;1999: 1999
;19999: 7

;1.25
;Not sure

;1.27
;Skipped

;; Exercise 1-9

;; The length of the chain of deferred additions
;; grows linearly with n. A linearly recursive process

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

(+ 3 10)
(inc (+ 2 10))
(inc (inc (+ 1 10)))
(inc (inc (inc 10)))
(inc (inc 11))
(inc 12)
13

;; The program variables provide a complete description
;; between steps. A linearly iterative process.

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

;; (+ 3 10)
;; (+ 2 11)
;; (+ 1 12)
;; (+ 0 13)
;; 13

;; Exercise 1-11

(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))
(f 0) ;Value: 0
(f 1) ;Value: 1
(f 2) ;Value: 2
(f 3) ;Value: 4
(f 4) ;Value: 11

(define (f n)
  (define (f-iter a b c n)
    (if (= n 0)
	c
	(f-iter (+ a (* 2 b) (* 3 c)) a b (- n 1))))
  (f-iter 2 1 0 n))
(f 0) ;Value: 0
(f 1) ;Value: 1
(f 2) ;Value: 2
(f 3) ;Value: 4
(f 4) ;Value: 11

;; Exercise 1-15

(sine 12.15)
(p (sine 4.05))
(p (p (sine 1.35)))
(p (p (p (sine 0.45))))
(p (p (p (p (sine 0.15)))))
(p (p (p (p (p (sine 0.05))))))
(p (p (p (p (p 0.05)))))

;; The procedure p is applied 5 times.

;; Both space and time increases by 1 whenever the angle 
;; is multiplied by 3. The orders of growth are logarithmic.


;; Exercise 1-17

(define (double x) (+ x x))

(define (halve x) (/ x 2))

(define (* a b)
  (cond ((= b 0) 0)
	((even? b) (* (double a) (halve b)))
	(else (+ a (* a (- b 1))))))

;; Exercise 1-19

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

(define (even? n)
  (= (remainder n 2) 0))

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
	((even? count)
	 (fib-iter a
		   b
		   (+ (square p) (square q)) ; compute p'
		   (+ (* 2 p q) (square q))  ; compute q'
		   (/ count 2)))
	(else (fib-iter (+ (* b q) (* a q) (* a p))
			(+ (* b p) (* a q))
			p
			q
			(- count 1)))))


;; Exercise 1-21

(smallest-divisor 199) ;Value: 199
(smallest-divisor 1999) ;Value: 1999
(smallest-divisor 19999) ;Value: 7

;; Exercise 1-27

(define (expmod base exp m)
  (cond ((= exp 0) 1)
	((even? exp)
	 (remainder (square (expmod base (/ exp 2) m))
		    m))
	(else
	 (remainder (* base (expmod base (- exp 1) m))
		    m))))

(define (carmichael-test n)
  (define (try-it a)
    (cond ((= a n) true)
	  ((= (expmod a n n) a) (try-it (+ 1 a)))
	  (else false)))
  (try-it 0))

(carmichael-test 561) ;Value: #t
(carmichael-test 1105) ;Value: #t
(carmichael-test 6601) ;Value: #t

#lang planet neil/sicp

;;;  Ex 1.9
;;

;(define (+ a b)
;  (if (= a 0)
;      b
;      (inc (+ (dec a) b))))

;(+ 4 5)
;(inc (+ (dec 4) 5))
;(inc (+ 3 5))
;(inc (inc (+ (dec 3) 5)))
;(inc (inc (+ 2 5)))
;(inc (inc (inc (+ (dec 2) 5))))
;(inc (inc (inc (+ 1 5))))
;(inc (inc (inc (inc (+ 0 5)))))
;(inc (inc (inc (inc 5))))
;(inc (inc (inc 6)))
;(inc (inc 7))
;(inc 8)
;9 => recursive


;
;(define (+ a b)
;  (if (= a 0)
;      b
;      (+ (dec a) (inc b))))

;(+ 4 5)
;(+ (dec 4) (inc 5))))
;(+ 3 6))
;(+ (dec 3) (inc 6))
;(+ 2 7)
;(+ (dec 2) (inc 7))))
;(+ 1 8)
;(+ (dec 1) (inc 8))))
;(+ 0 9)
;9 => iterative


;;;  Ex 1.10
;;
(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

; (A 1 10) => 1024
; (A 2 4)  => 65536
; (A 3 3)  => 65536

(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))
(define (k n) (* 5 n n))

; (f n) = 2n
; (g n) = 2^n
; (h n) = 2^(2^(2^....)) or 2^[h(n-1)]
; (k n) = 5n^2

;;;  Ex 1.11
;; f(n) = n if n<3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n> 3.
;;
(define (f1 n) (f-rec n))
(define (f2 n) 
  (if (< n 3) 
      n
      (f-iter 0 1 2 (- n 2))))

(define (f-rec n)
  (if (< n 3) 
      n
      (+ (* 1 (f-rec (- n 1)))
         (* 2 (f-rec (- n 2)))
         (* 3 (f-rec (- n 3))))))

(define (f-iter a b c count)
  (if (zero? count) 
      c
      (f-iter b 
              c  
              (+ c (* 2 b) (* 3 a))
              (- count 1))))

;;;  Ex 1.12
;; 
(define (pascal row col)
  (cond ((= row 1) 1)
        ((= col 1) 1)
        ((= col row) 1)
        (else (+ (pascal (- row 1) (- col 1))
                 (pascal (- row 1) col)))))


;;;  Ex 1.13
;
; r5 = sqrt 5
; ? = (1+r5)/2
; ? = (1-r5)/2
; 
; ?^2 = (1+r5)^2/4 = (1 + 2r5 + 5)/4 = (3+r5)/2  (1)
; ?^2 = (1-r5)^2/4 = (3-r5)/2                    (2)
;
; Induction:
; Base cases:
; Fib(0)= (?^0 - ?^0)/r5 = 0
; Fib(1)= (? - ?)/r5 = [(1+r5)/2 - (1-r5)/2] / r5 = 1
;
; Fib(k)   = (?^k - ?^k)/r5             (3)
; Fib(k+1) = (?.?^k-?.?^k)/r5           (4)
; Fib(k+2) = [?^k(1+?)-?^k(1+?)] / r5   (3) + (4)
; (1+?) = 1 + (1+r5)/2 = (3+r5)/2 = ?^2     from (1)
; (1+?) = 1 + (1-r5)/2 = (3-r5)/2 = ?^2     from (2)
; Fib(k+2) = ?^k.?^2-?^k.?^2 / r5 = (?^k+2 - ?^k+2) / r5
;
; ? = (1-r5)/2
; 4 < 5 < 9         => 2 < r5 < 3
; -1 > (1-r5) > -2  => |?| < 1
; as n -> inf (1-?)^n -> 0
; Fib(n) -> (? - 0)^n/r5 
; Fib(n) -> ?^n/r5



;;;  Ex 1.14
;; 
(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))

;; US coins
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

;;; UK coins
;(define (first-denomination kinds-of-coins)
;  (cond ((= kinds-of-coins 1) 1)
;        ((= kinds-of-coins 2) 2)
;        ((= kinds-of-coins 3) 5)
;        ((= kinds-of-coins 4) 10)
;        ((= kinds-of-coins 5) 20)
;        ((= kinds-of-coins 6) 50)
;        ((= kinds-of-coins 7) 100)
;        ((= kinds-of-coins 8) 200)))

;;;  Ex 1.15
;;

(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
   (if (not (> (abs angle) 0.1))
       angle
       (p (sine (/ angle 3.0)))))

; a) p is applied 5 times for (sine 12.15)  with values 4.05, ~1.35 ~0.45 ~0.15, ~0.05
; b) since the angle is being divided by 3 each time the space is (log n)
;    since this is a tail recursive procedure time will also be (log n)

;;;  Ex 1.16
;;;
(define (square x) (* x x))

(define (expt b n)
  (expt-iter b n 1))

(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                 (- counter 1)
                 (* b product)))) 

; b^n = [ b^(n/2) ]^ 2 : even n
;     = b.b^(n-1)      : odd n
(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

(define (fast-expt-iter b n a)
  (cond ((= n 0) a)
        ((even? n) (fast-expt-iter (square b) (/ n 2) a))
        (else (fast-expt-iter b (- n 1) (* a b)))))

;;;  Ex 1.17
;;;
(define (my-* a b)
  (if (= b 0)
      0
      (+ a (my-* a (- b 1)))))

(define (double n) (+ n n))
(define (halve n) (/ n 2))

(define (fast-* b n)
  (cond ((= n 0) 0)
        ((even? n) (double (fast-* b (halve n))))
        (else (+ b (fast-* b (- n 1))))))

;;;  Ex 1.18
;;;
(define (fast-*-iter b n a)
  (cond ((= n 0) a)
        ((even? n) (fast-*-iter (double b) (halve n) a))
        (else (fast-*-iter b (- n 1) (+ a b)))))


;;;  Ex 1.19
;;;
(define (fib-rec n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib-rec (- n 1))
                 (fib-rec (- n 2))))))

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   (+ (square p) (square q))  ; p'
                   (+ (* 2 p q)  (square q))  ; q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

;;;  Ex 1.20
;;;
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
  (= (remainder b a) 0))

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

; normal order
; =============
; (gcd 206 40)
;01: zero? 40 
;(gcd 40 (remainder 206 40))
;02: zero? (remainder 206 40)                                                  
;(gcd (remainder 206 40) (remainder 40 (remainder 206 40)))
;03: zero? (remainder 40 (remainder 206 40))                                   
;04: zero? (remainder 40 6)
;zero? 4                                                                   
;(gcd (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
;05: zero? (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))    
;06: zero? (remainder 6 (remainder 40 (remainder 206 40)))                     
;07: zero? (remainder 6 (remainder 40 6))                                      
;08: zero? (remainder 6 4)                                                     
;zero? 2
;(gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))
;09: zero? (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
;10: zero? (remainder (remainder 40 6) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))  
;11: zero? (remainder 4 (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))                 
;12: zero? (remainder 4 (remainder (remainder 206 40) (remainder 40 6)))                                  
;13: zero? (remainder 4 (remainder (remainder 206 40) 4))                                                 
;14: zero? (remainder 4 (remainder 6 4))                                                                  
;15: zero? (remainder 4 2)                                                                                
;zero? 2                                                                                              
;(gcd (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) 
;     (remainder (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))))
;16: zero? (remainder (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))))
;17: zero? (remainder (remainder 6 (remainder 40 (remainder 206 40))) (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))))
;18: zero? (remainder (remainder 6 (remainder 40 6)) (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))))
;19: zero? (remainder (remainder 6 4) (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))))
;20: zero? (remainder 2 (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))))
;21: zero? (remainder 2 (remainder (remainder 40 6) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))))
;22: zero? (remainder 2 (remainder 4 (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))))
;23: zero? (remainder 2 (remainder 4 (remainder 6 (remainder 40 (remainder 206 40)))))
;24: zero? (remainder 2 (remainder 4 (remainder 6 (remainder 40 6))))
;25: zero? (remainder 2 (remainder 4 (remainder 6 4)))
;26: zero? (remainder 2 (remainder 4 2))
;27: zero? (remainder 2 2)
;zero? 0
;-> (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
;28: -> (remainder (remainder 40 6) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
;29: -> (remainder 4 (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
;30: -> (remainder 4 (remainder 6 (remainder 40 (remainder 206 40))))
;31: -> (remainder 4 (remainder 6 (remainder 40 6)))
;32: -> (remainder 4 (remainder 6 4))
;32: -> (remainder 4 2)
;33: -> (remainder 4 2)
;-> 2
;
; applicative order
; ==================
; (gcd 206 40)
;(gcd 206 40)
;
;zero? 40
;(gcd (40 (remainder 206 40)))
;rc 01:: (gcd 40 6)
;zero? 6
;(gcd 6 (remainder 40 6))
;rc 02:: (gcd 6 4)
;(gcd 6 4)
;zero? 4
;(gcd 4 (remainder 6 4))
;rc 03:: (gcd 4 2)
;zero? 2
;(gcd 2 (remainder 4 2))
;rc 04:: (gcd 2 2)
;zero? 2
;(gcd (2 (remainder 2 2)))
;rc 05:: (gcd (2 0))
;zero? 0
;-> 2


;;;  Ex 1.21
;;;
(define (smallest-divisor n)
  (define (find-divisor n test-divisor)
    (define (divides? a b) (= (remainder b a) 0))
    (cond ((> (square test-divisor) n) n)
          ((divides? test-divisor n) test-divisor)
          (else (find-divisor n (+ test-divisor 1)))))
  (find-divisor n 2))

;(smallest-divisor 199)
;199
;(smallest-divisor 1999)
;1999
;(smallest-divisor 19999) 
;7


;;;  Ex 1.22
;;;
(define null '())

(define (prime? n)
  (= n (smallest-divisor n)))

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))
(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

(define (search-for-primes start max-primes)
  (define (primes-from n count)
    (cond ((zero? count) null)
          ((prime? n) (cons n (primes-from (+ n 2) (- count 1))))
          (else (primes-from (+ n 2) count))))
  (primes-from (if (even? start) 
                   (+ 1 start) 
                   start)
               max-primes))

;;;  Ex 1.23
;;;
(define (smallest-odd-divisor n)
  (find-odd-divisor n 2))

(define (find-odd-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (next-divisor test-divisor)))))

(define (next-divisor n)
  (+ n (if (= n 2) 1 2)))

(define (prime-odd? n)
  (= n (smallest-odd-divisor n)))

(define (search-for-odd-primes start max-primes)
  (define (primes-from n count)
    (cond ((zero? count) null)
          ; ((timed-odd-prime? n) (cons n (primes-from (+ n 2) (sub1 count))))
          ((prime? n) (cons n (primes-from (+ n 2) (- count 1))))
          (else (primes-from (+ n 2) count))))
  (primes-from (if (even? start) 
                   (+ 1 start) 
                   start)
               max-primes))

;Exercise 1.9.
(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9

;Exercise 1.11
;recursive version
(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1))
         (* 2 (f (- n 2)))
         (* 3 (f (- n 3))))))

;iterative version
(define (f n)
  (f-iter 0 0 1 2 n))
(define (f-iter cnt a b c max)
  (if (= cnt max)
      a
      (f-iter (+ cnt 1)
              b
              c
              (+ c
                 (* 2 b)
                 (* 3 a))
              max)))

;Exercise 1.12
;row and col start from zero
(define (triangle row col)
  (if (or (= row col) (= col 0))
      1
      (+ (triangle (- row 1)
                   (- col 1))
         (triangle (- row 1)
                   col))))
				   
;Exercise 1.16
(define (exp b n)
  (exp-iter b n 1))
(define (exp-iter b n a)
  (cond ((= n 0) a)
        ((even? n) (exp-iter (square b) 
                             (/ n 2) 
                             a))
        (else (exp-iter b 
                        (- n 1) 
                        (* a b)))))

;Exercise 1.17
(define (multiply x y)
  (cond ((= y 0) 0)
        ((even? y) (multiply (double x) (halve y)))
        (else (+ x (multiply x (- y 1))))))
		
;Exercise 1.18
(define (multiply x y)
  (mul-iter x y 0))
(define (mul-iter x y a)
  (cond ((= y 0) a)
        ((even? y) (mul-iter (double x) (halve y) a))
        (else (mul-iter x (- y 1) (+ a x)))))
		
;Exercise 1.22
;low gives the lower bound and cnt says how much prime numbers it has to output
(define (search-for-primes low cnt)
  (cond ((even? low) (search-for-primes (+ low 1) cnt))
        ((> cnt 0)
         (cond ((prime? low)
                (timed-prime-test low) ;it's computed twice..
                (search-for-primes (+ low 2) (- cnt 1)))
               (else
                (search-for-primes (+ low 2) cnt))))))
				
;Exercise 1.23
(define (next n)
  (if (= n 2)
      3
      (+ n 2)))
(define (divisor n div)
  (cond ((> (square div) n) n)
        ((divides n div) div)
        (else (divisor n (next div)))))
		
;Exercise 1.27
;every carmichael number passes the test
(define (fool carmichael)
  (test 0 carmichael))
(define (test a n)
  (cond ((= a n) #t)
        ((= (expmod a n n) a) (test (+ a 1) n))
        (else #f)))