<< Previous exercise (3.65) | Index | Next exercise (3.67) >>
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
zzd3zzd
draeklae
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:
luckykoala
I wrote this in Scheme:
(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)))))mart256
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.
xdavidliu
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