sicp-ex-3.66

(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)

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

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

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

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

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

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

 (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) 

This is how I confirm draeklae's answer.

For an integer pair (m, n), the number of its predecessors is given by

f(m,n) = 2^{m} - 2, for m=n,

f(m,n) = (n-m)*2^{m} + 2^{m-1} - 2, for m<n.

Let's just take a look at the index (i,j) starting from (0,0) since it's easy to substitute (i,j) for the integer pair (m,n) with m=i+1 and n=j+1.

 (0,0)|(0,1) (0,2) (0,3) ... 
 --------------------------- 
      |(1,1) (1,2) (1,3) ... 
      |      (2,2) (2,3) ... 

The triangular matrix have three parts:

I. (0,0), the leading pair.

II. (0,1) (0,2) (0,3) ..., the rest of the first row.

III. (1,1) (1,2) (1,3) ..., except the first row.

This structure remains whenever we focus on a specified row. For the ith row, the procedure `interleave` always interleaves part II with part III. It's clear that `interleave` will double the distance between adjoint pairs. That means, interleaving the part II of the ith row with the rows after it will scale the distance between (i,i+1) and (i,j) from 1 to 2 for any j>i+1.

After collapsing rows after the ith row, the coordinate of (i,j) relative to (i,i) is given by:

 0,        for i=j, 
 2(j-i)-1, for i<j. 
  
 ... rows precede the ith row ... 
 -------------------------------------- 
 (i,i)|(i,i+1) (i,i+2) (i,i+3) ... 
 -------------------------------------- 
      |... rows after  ... 
      |... the ith row ... 
      | interleaving these pairs 
      | doubles the distance 
      | between (i,j) and (i,j+1) 
      | for any j>0 
 After collapsing => 
   ... rows precede the ith row ... 
   --------------------------------------------- 
   (i,i)|(i,i+1) (?,?) (i,i+2) (?,?) (i,i+3) ... 
 D:   --1--- ------2------ ------2-------------- 

Interleaving the collapsed ith row with the part II of the (i-1)th row will double the distance between (i,i) and (i,j). If we do this i times, the distance will be doubled i items as well. The total distance from (i,i) to (i,j) where i<j is hence (2j-2i-1)*2^{i}.

What left is to figure out the distance from (0,0) to (i,i).

If we interleave the collapsed ith row with the (i-1)th row recursively, the pair (i,i) will shift to the right with a pattern:

 - 0, counter=i 
 - 2, counter=i-1 
 - 2*2+2, counter=i-2 
 ... 
 - 2^{i}+2^{i-1}+...+2, counter=0 

This pattern gives the distance from (0,0) to (i,i),

2^{i+1}-2.

Adding up the distance from (0,0) to (i,i) and the distance from (i,i) to (i,j) gives

(j-i)*2^{i+1}+2^{i}-2.

Here we get the formulas

f(i,j)=2^{i+1}-2, for i=j,

f(i,j)=(j-i)*2^{i+1}+2^{i}-2, for i<j.

Substituting (i,j) for (m-1,n-1) should give the count of integer pairs before (m,n).

f(m,n)=2^{m}-2, for m=n,

f(m,n)=(n-m)*2^{m}+2^{m-1}-2, for m<n.

 (define (count-integer-pairs m n) 
   (if (= m n) 
       (- (expt 2 m) 2) 
       (+ (* (- n m) (expt 2 m)) (expt 2 (- m 1)) -2))) 

I arrived at a similar answer to @zzd3zzd.

Note that I used 0-based indexing. Thus, pair (1,1) is at position 0.

My equations:

k(i,n) is the position of pair (i,n).

if (i==n)   : k(i,n)=(2^i) - 2
if (n==i+1) : k(i,n)=k(i,i) + 2^(i-1)
else        : k(i,n)=k(i,i+1) + (n-i-1)*2^i

Therefore:

k(1,1)     = 2^1 - 2 = 0

k(1,2)     = k(1,1) + 2^0
           = 0 + 1 = 1

k(1,100) = k(1,2) + (100-1-1)*2^1
         = 1 + (98)*2
         = 197


k(99,99)  = 2^99 - 2

k(99,100) = k(99,99) + 2^98
        = 2^99 - 2 + 2^98

k(100,100) = 2^100 - 2

How I arrived at this answer: TODO

consider pair (m, n), when at level m, the pos would be 1 if (n-m) = 0, otherwise 2(n-m).

when finishing the pos calculation at the current level, decrease m by 1} to step up a level, calculating the new pos pos = 2*pos' +1, where pos' is the old pos.

loop until m = 1.

below is the procedure to compute the pos,

(define (pos m n) 
  (define init (if (= m n) 1 (* 2 (- n m))))
  (define (inner x res) 
    (if (= x 1)
      res
      (inner (- x 1) (+ 1 (* 2 res)))))
  (inner m init))

as for the precede pair number,

(define (pnum m n)
  (- (pos m n) 1))

thus

(1,   100): 197
(99,  100): 950737950171172051122527404030
(100, 100): 1267650600228229401496703205374

same answer @brandon