## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 2.05

## Problem

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 <math>2^a3^b</math>. Give the corresponding
definitions of the procedures `cons`, `car`, and `cdr`.

## Solution

For this exercise we'll need one of our exponentiation procedures from chapter 1 of the text.

(define (square x) (* x x)) (define (fast-expt b n) (fast-expt-iter 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)))))

The exercise asks us to represent the pair as the product <math>2^a3^b</math>,
so `cons` is straightforward:

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

For any given pair *a* and *b* represented in this fashion, there are *a*
factors of 2 and *b* factors of 3. We can use the fact that 2 and 3
are relatively prime (i.e., they share no common factors) to implement `car` and `cdr`. Assume that *p* is
the pair represented by <math>2^a3^b</math>. When *a* is greater than zero (i.e.,
when *p* is a multiple of 2), then the remainder of *p* divided by 2 is
zero; but when *a* is zero (i.e., when *p* contains no multiples of 2),
the remainder of *p* divided by 2 is non-zero. Therefore, by
repeatedly dividing by 2 until the remainder is non-zero, we can
determine the value of *a*: in fact, *a'*s value is the number of times
we can repeatedly divide by 2, starting with pair *p*, such that the remainder is zero.

By the same argument, we can repeatedly divide a pair *p* by 3 until the
remainder is non-zero to determine *b*.

Here are implementations of `car` and `cdr` which implement this
strategy:

(define (car p) (if (= (remainder p 2) 0) (+ 1 (car (/ p 2))) 0)) (define (cdr p) (if (= (remainder p 3) 0) (+ 1 (cdr (/ p 3))) 0))

Test:

(car (cons 0 2))

*Output:*

`
`

0

(cdr (cons 0 2))

*Output:*

`
`

2

(car (cons 3 6))

*Output:*

`
`

3

(cdr (cons 3 6))

*Output:*

`
`

6

car and cdr are nearly the same and can be simplified using the techniques we learned in chapter 1 of the text:

(define (car p) (count-factors p 2)) (define (cdr p) (count-factors p 3)) (define (count-factors p n) (if (= (remainder p n) 0) (+ 1 (count-factors (/ p n) n)) 0))

Test again:

(car (cons 0 2))

*Output:*

`
`

0

(cdr (cons 0 2))

*Output:*

`
`

2

(car (cons 3 6))

*Output:*

`
`

3

(cdr (cons 3 6))

*Output:*

`
`

6