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, $a$ and $b$, can be represented using a single integer: $2^a 3^b$.
Since any number can be represented as a product of a unique combination of prime numbers, it follows that any number $2^a 3^b$ will result in a unique number i.e. no other number will have same combination of $2$ and $3$.
Thus we can get back the pair $(a,b)$ using the number $2^a 3^b$. To get back the pair we need to find the number of times we can divide the number by $2$ and $3$ to get $a$ and $b$ 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