Exercise 3.66 in SICP

exercise3.66.scm

; Exercise 3.66

(define (index i j)
  (if (= i j)
      (- (expt 2 (+ i 1)) 2)
      (- (* (expt 2 i) (+ (* 2 (- j i)) 1)) 2)))

(map
 (lambda (p)
   (let ((i (- (car p) 1))
         (j (- (cadr p) 1)))
     (index i j)))
'((1 1) (1 2) (2 2) (1 3) (2 3) (1 4) (3 3) (1 5) (2 4) (1 6) (3 4) (1 7) 
(2 5) (1 8) (4 4) (1 9) (2 6) (1 10) (3 5) (1 11) (2 7) (1 12) (4 5) (1 13)
(2 8) (1 14) (3 6) (1 15) (2 9) (1 16) (5 5) (1 17) (2 10) (1 18) (3 7) (1 19)
(2 11) (1 20) (4 6) (1 21) (2 12) (1 22) (3 8) (1 23) (2 13) (1 24) (5 6) (1 25)
(2 14) (1 26) (3 9) (1 27) (2 15) (1 28) (4 7) (1 29) (2 16) (1 30) (3 10) (1 31)
(2 17) (1 32) (6 6) (1 33) (2 18) (1 34) (3 11) (1 35) (2 19) (1 36) (4 8) (1 37)
(2 20) (1 38) (3 12) (1 39) (2 21) (1 40) (5 7) (1 41) (2 22) (1 42) (3 13) (1 43)
(2 23) (1 44) (4 9) (1 45) (2 24) (1 46) (3 14) (1 47) (2 25) (1 48) (6 7) (1 49)
(2 26) (1 50) (3 15) (1 51)))

(define (rec-index i j)
  (cond
    ((or (< i 0) (< j 0) (> i j)) -1)
    ((and (= i 0) (= j 0)) 0)
    ((and (= i 0) (> j 0)) (- (* 2 j) 1))
    (else (+ (* 2 (rec-index (- i 1) (- j 1))) 2))))

(define (test-index i j)
  (= (index i j) (rec-index i j)))

(test-index 0 0)
(test-index 0 1)
(test-index 1 3)
(test-index 2 4)