# sicp-ex-3.66

meteorgan

```

(1, 100) : 198
(100, 100): 99*2^200 - 1 + 2^99.
the equation for (m, n) is:
n = 1:   2^m - 1;
n = 2:   2^m - 1 + 2^(m-1);
n > 2:   2^m - 1 + 2^(m+1) + (n-2)*2^m
```
```@meteorgan  ---  You are Wrong !!!
(1,100):198;
(100,100):2^100 - 1;
---------------
f(n,m) m>=n (m,n is Z+)
(m-n=0): 2^n - 1
(m-n=1): (2^n - 1) + 2^(n - 1)
(m-n>1): (2^n - 1) + 2^(n - 1) + (m - n - 1) * 2^n
------------------------------------
1   2   3   4   5   6   7   8   9  ...  100
1 1   2   4   6   8  10  12  14  16       198
2     3   5   9  13  17  21  25  29
3         7  11  19  27  35  43  51
4            15  23  39  .....
5                31  .........
.
.
100 ------------------------------------- (2^100 - 1)

```

I can confirm zzd3zzd's formulas, but we should throw a -1 in (since the exercises asks for how many pairs *precede* (1,100) etc.). I add a somewhat simplified definition for f as a bonus:

```f(i,j) = 2^i - 2, i = j
f(i,j) = 2^i * (j-i) + 2^(i-1) - 2, i < j
```

I wrote this in Scheme:

```
(define (index-of-pair pair)
(let ((i (car pair))
(cond ((> i j) #f)
((= i j) (+ (expt 2 i) -1))
(else (+ (* (expt 2 i) (- j i))
(expt 2 (- i 1))
-1)))))
```

Thanks @zzd3zzd for the diagram. It was very useful to understand the pattern. Next time I'll try to figure patterns with diagrams like this.

Let (z m n) be the 0-based index of the pair (m n) in the stream (pairs integers integers). In other words, we want to find z such that

``` (equal? (list m n)
(stream-ref (pairs integers integers) (z m n)))
```

For m = 1, by a bit of simple inspection of the first few elements of the stream, we have

``` (= (z 1 n)
(* 2 (- n 3)))
```

For m = 2, by some further inspection, we have

``` (= (z 2 n)
(+ 2
(* 2
(z 1 (-1+ n)))))
```

Since the streams and interleaved sub-streams are self-similar, this relation holds for all m.

``` (= (z m n)
(+ 2
(* 2
(z (-1+ m) (-1+ n)))))
```

This recursion can be solved straightforwardly with pencil and paper to obtain

``` (define (z m n)
(+ -2
(* (expt 2 m)
(+ n 1/2 (- m)))))

;; for example:
(z 6 14) ; 542
(stream-ref (pairs integers integers) 542) ; (6 14)
```