SICP - Solution: Exercise 2.5

January 7, 2019

Exercise 2.5 #

Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair $a$ and $b$ as the integer that is the product ${2^a3^b}$. Give the corresponding definitions of the procedures cons, car, and cdr.

Solution #

This method can work not just with 2 and 3, but any relative prime numbers. For example, using $a=2$ and $b=3$, we have:

$$2^43^5=2\times2\times2\times2\times3\times3\times3\times3\times3=3888$$

By this definition, $3888$ can be divided $2^4=16$ before the result will have a remainder. Dividing by one more will give $\frac{3888}{2^5}=121.5$. We can use this to encode the number by computing cons using the formula:

(define (cons a b)
  (* (expt 2 a) (expt 3 b)))

The implementation of car and cdr looks very much alike: it just counts the number of times the number can be divided by 2 or 3 before returning a remainder:

(define (car x)
  (define (car-iter x count)
  (if (= 0 (remainder x 2))
      (car-iter (/ x 2) (+ 1 count))
      count))
  (car-iter x 0))

(define (cdr x)
  (define (cdr-iter x count)
  (if (= 0 (remainder x 3))
      (cdr-iter (/ x 3) (+ 1 count))
      count))
  (cdr-iter x 0))

(print (cons 3 18))       (newline)
(print (car (cons 3 18))) (newline)
(print (cdr (cons 3 18))) (newline)

I have not found more efficient methods than this.

The result of the evaluation:

3099363912
3
18