SICP Exercise 2.5

Question

Show that we can represent pairs of non-negative integers using only numbers and arithmetic operations if we represent the pair \(a\) and \(b\) as the integer that is the product \({2^a}{3^b}\). Give the corresponding definitions of the procedures cons, car, and cdr.

Answer

The actual constructor for this is simple enough:

(define (cons x y)
  (* (expt 2 x) (expt 3 y)))

For retrieving the two numbers, it helps to remember that since 2 and 3 are prime numbers, an exponentiation of one can never equal an exponentiation of the other. In fact, you don’t even have to use 2 and 3, any two prime numbers will do. You may copy this code and try 11 and 19, and it will work as well.

(define (iterate num counter divisor)
  (if (= (modulo num divisor) 0)
      (iterate (/ num divisor) (+ counter 1) divisor)
      counter))

(define (car z) (iterate z 0 2))
(define (cdr z) (iterate z 0 3))

Let’s test it:

(define z (cons 5 9))
(car z)
(cdr z)

Results:

5
9