Chapter 2, Building Abstractions with Data

Section - 2.1 - Introduction to Data Abstraction

Exercise 2.5


We have to show that any pair of non-negative integers, and , can be represented using a single integer: .

Since any number can be represented as a product of a unique combination of prime numbers, it follows that any number will result in a unique number i.e. no other number will have same combination of and .

Thus we can get back the pair using the number . To get back the pair we need to find the number of times we can divide the number by and to get and respectively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#lang sicp

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

(define (log base x)
  (define (count c n)
      (if (= (remainder n base) 0)
          (count (+ c 1) (/ n base))
          c
      )
  )
  (count 0 x)      
  
)

(define (car x)
  (log 2 x)
)

(define (cdr x)
  (log 3 x)
)

Output:

1
2
3
4
5
6
> (cons 4 6)
11664
> (car 11664)
4
> (cdr 11664)
6