Exercise 3.66

pairs starts with ((car s) (car t)) and then interleaves
a) the stream formed by mapping ((car s) _) against (cdr t) i.e (1 _) (2 3 4 …) or (1 2) (1 3) (1 4) …
b) the stream formed by (pairs (cdr s) (cdr t))
The pair (1 n) is in position:

  1    + 2(n-1) 
(1 1)  + interleaved items from a) and b)

The number of pairs preceding (1 n) is therefore 2(n – 1) – 1 so (1 100) has 197 preceding pairs.
The first 20 pairs are:
(1 1)
(1 2)
(2 2)
(1 3)
(2 3)
(1 4)
(3 3)
(1 5)
(2 4)
(1 6)
(3 4)
(1 7)
(2 5)
(1 8)
(4 4)
(1 9)
(2 6)
(1 10)
(3 5)
(1 11)
The pair (x y) won’t come from the even numbered items in the result stream as they are all (1 n) so for now ignore those. The remaining items come from (pairs (2 3 4 …) (2 3 4 …))
(2 2)
(2 3)
(3 3)
(2 4)
(3 4)
(2 5)
(4 4)
(2 6)
(3 5)
In this stream (2 m) is in position
1+2(m-1) and so has 2(m-1) – 1 preceding pairs. These are interleaved with the (1 n) stream (which appear in every 2nd position) which means (2 m) pairs have 2(2[m-1]-1) preceding pairs.
There is a pattern emerging:
(3 m) will have 2(m-1)-1 preceding items interleaved and so has about 4(2[m-1]-1) preceding items.
In general then pair (x y) has 2x-1(2[y-1]-1) preceding items.

(1 100) : 20(2*99 – 1) = 197
(99 100) : 298(2*99 – 1) = 99 * 299 – 298
(100 100) : 299(2*99 – 1) = 99 * 299 – 299

I don’t have huge confidence in these values. I think it’s more accurate to say 2(…2(2(2(m-1)-1)-1)…-1 but these are probably close enough though.

Advertisements

One thought on “Exercise 3.66

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s