 JAMES LONG

# SICP 2.5

December 14, 2011

Today I'm working through exercise 2.5 from Section 2.1: Introduction to Data Abstraction. The problem sounds intruiging to me.

I'll be honest: I couldn't figure it out. I knew how to do it, but I couldn't figure out the math to solve it. I looked up the solution and it took my a while to understand it. It was interesting enough that I still wanted to write about it!

The problem asks to implement the pair data structure (a container that holds elements `x` and `y`) as an integer that represents `2^x * 3^y`.

Implementing the `cons` procedure which creates the pair is easy:

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

Now we need to implement `car` and `cdr` procedures which extract the first and second element. We need to solve for `x` and `y`.

I'm not sure what the mathematical solution is, but we can solve it with code. Here is the solution from schemewiki, assuming that `expt` is an exponent procedure:

``````(define (count-0-remainder-divisions n divisor)
(define (iter try-exp)
(if (= 0 (remainder n (expt divisor try-exp)))
(iter (+ try-exp 1))  ;; Try another division.
(- try-exp 1)))

;; Start at 1, as 0 will obviously pass.
(iter 1))

(define (car z) (count-0-remainder-divisions z 2))
(define (cdr z) (count-0-remainder-divisions z 3))
``````

It's a bit confusing, so let's dig through it. The key idea is that `2^x` will always produce an even number, while `3^y` will always produce an odd number. If we need to find `x`, we can test each iteration of `2^1 .. 2^n` and when the consed integer divided by `2^n` produces a remainder, we know that `x=n-1` which is the last divisible number. We can do the same thing for `y`.

Say we have `(cons 3 4)`. Our representation turns into:

``````(cons 3 4)
(2^3) * (3^4)
(2*2*2) * (3*3*3*3)

(2*2*2)     <- always even
(3*3*3*3) <- always odd
``````

An even number is never divisible by an odd number, and vice versa. Knowing this, we can iteratively test values for `x` or `y` like this:

``````
;; Test equation, where %= means "the remainder equals"
(2*2*2) * (3*3*3*3) / (2^i) %= 0

i=1

(2*2*2) * (3*3*3*3) / 2 %= 0
(2*2) * (3*3*3*3) / 1 %= 0
;; True

i=2

(2*2*2) * (3*3*3*3) / (2*2) %= 0
2 * (3*3*3*3) / 1 %= 0
;; True

i=3

(2*2*2) * (3*3*3*3) / (2*2*2) %= 0
3*3*3*3 / 1 %= 0
;; True

i=4

(2*2*2) * (3*3*3*3) / (2*2*2*2) %=0
(3*3*3*3) / 2 %= 0
;; False
``````

We know the last equation is false because an odd number is never divisible by 2. So `x` is `i-1` at the point of the last iteration, which is 3. Because we also know that an even number is never divisible by an odd number, you can deduce `y` the same way.

This works:

``````(define a (cons 40 76))

(car a)
40

(cdr a)
76
``````

Clever.

Update: A friend pointed out on twitter that it's not so much about even/odd numbers, but about prime factorization. This makes sense because 2 and 3 are prime numbers, and concepts here would work with any primes. Thanks for pointing out the real definition of this!