SICP Exercise 2.5: Prime Factor Pairs

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.

The reason we can use this method of representation comes down to the fact that the two numbers 2 and 3 are both prime numbers. As a result, the product 2^a3^b is a prime factorization of some number n. Now the fundamental theory of arithmetic states that each number >1 has a unique prime factorization. This implies that for any nonnegative integers a and b, 2^a3^b will produce a unique number. Alternatively, there are no two pairs of nonnegative integers, {a, b} and {c, d}, such that 2^a3^b=2^c3^d.

So if we represent the pair of nonnegative integers {a, b} as the integer value n=2^a3^b then this will be a unique representation of the pair. Provided we can then extract the a and b values out of n then this will be a viable representation.

So how can we do this?

Well, the simple way is to just count the number of times we can start from n and repeatedly divide by either 2 or 3, depending upon whether we're trying to find a or b, without leaving any remainder. Assuming we're happy with this approach we can define cons, car, and cdr as:

(define (cons a b)
  (if (and (>= a 0) (>= b 0))
      (* (expt 2 a) (expt 3 b))
      (error "a and b must be >= 0")))

(define (count-factors n f)
  (define (iter remaining result)
    (if (> (remainder remaining f) 0)
        result
        (iter (/ remaining f) (+ result 1))))
  (iter n 0))

(define (car p) (count-factors p 2))
(define (cdr p) (count-factors p 3))

Here's an example of it in practice:

> (define pair (cons 21 14))
> (car pair)
21
> (cdr pair)
14

Note that we don't have to use prime numbers in the representation here. Provided the numbers we use in the representation are coprime the representation will still work. For example, we could represent the pair of nonnegative integers {a, b} as the integer value n=20^a21^b. Neither 20 nor 21 are prime. However, 20 has the prime factorization 2×2×5, while 21 has the prime factorization 3×7. There are no common factors here, so all should still work. To test this, lets change the definitions of cons, car, and cdr to:

(define (cons a b)
  (if (and (>= a 0) (>= b 0))
      (* (expt 20 a) (expt 21 b))
      (error "a and b must be >= 0")))

(define (car p) (count-factors p 20))
(define (cdr p) (count-factors p 21))

...and give it a spin:

> (define pair (cons 12 10))
> (car pair)
12
> (cdr pair)
10