SICP問題3.66

append のストリーム版(教科書で定義)

(define (stream-append s1 s2)
  (if (stream-null? s1)
      s2
      (cons-stream (stream-car s1)
                   (stream-append (stream-cdr s1) s2))))

第二のストリームを取り込む前に第一のストリームから全ての要素を取るので無限ストリームには不向き
=> 二つのストリームから要素を交互にとるinterleave手続き(教科書で定義)

(define (interleave s1 s2)
  (if (stream-null? s1)
      s2
      (cons-stream (stream-car s1)
                   (interleave s2 (stream-cdr s1)))))

i<=j, i+jが素数である全ての整数(i, j)の対のストリーム
整数の対はLispの対ではなく、リストで表現する(教科書で定義)

(define (pairs s t)
  (cons-stream
   (list (stream-car s) (stream-car t))
   (interleave
    (stream-map (lambda (x) (list (stream-car s) x))
                (stream-cdr t))
    (pairs (stream-cdr s) (stream-cdr t)))))

で、ここからが問題。
(pairs integers integers)について、対がストリームに置かれる順につき、一般的に述べることが出来るか。
例えば対(1, 100), 対(100, 100)の前に近似的に何個の対が来るか。(数学的に厳密な表現が出きれば大いによい。しかし分からなくなったら定性的な答えを出すのでもよい)

ということで、何も考えずに実行。

(stream-ref-range (pairs integers integers) 0 50)
; (1 1)  ;  1
; (1 2)  ;  2
; (2 2)  ;  3
; (1 3)  ;  4
; (2 3)  ;  5
; (1 4)  ;  6
; (3 3)  ;  7
; (1 5)  ;  8
; (2 4)  ;  9
; (1 6)  ; 10
; (3 4)  ; 11
; (1 7)  ; 12
; (2 5)  ; 13
; (1 8)  ; 14
; (4 4)  ; 15
; (1 9)  ; 16
; (2 6)  ; 17
; (1 10) ; 18
; (3 5)  ; 19
; (1 11) ; 20
; (2 7)  ; 21
; (1 12) ; 22
; (4 5)  ; 23
; (1 13) ; 24
; (2 8)  ; 25
; (1 14) ; 26
; (3 6)  ; 27
; (1 15) ; 28
; (2 9)  ; 29
; (1 16) ; 30
; (5 5)  ; 31
; (1 17) ; 32
; (2 10) ; 33
; (1 18) ; 34
; (3 7)  ; 35
; (1 19) ; 36
; (2 11) ; 37
; (1 20) ; 38
; (4 6)  ; 39
; (1 21) ; 40
; (2 12) ; 41
; (1 22) ; 42
; (3 8)  ; 43
; (1 23) ; 44
; (2 13) ; 45
; (1 24) ; 46
; (5 6)  ; 47
; (1 25) ; 48
; (2 14) ; 49
; (1 26) ; 50
; #<undef>

結果から考えると

i = 1 が現れるのは  0,  1,  3,  5,  7,  9, ... と一つおき
   0     1     3     5     7     9 ....
(1 1) (1 2) (1 3) (1 4) (1 5) (1 6)
i = 2 が現れるのは  2,  4,  8, 12, 16, 20, ...
   2     4     8    12    16    20
(2 2) (2 3) (2 4) (2 5) (2 6) (2 7)
i = 3 が現れるのは  6, 10, 18, 26, 34, 42, ...
   6    10    18    26    34    42
(3 3) (3 4) (3 5) (3 6) (3 7) (3 8)
i = 4 が現れるのは 14, 22, 38, 
  14    22    38    54?
(4 4) (4 5) (4 6) (4 7)
i = 5 が現れるのは 30, 46, 
  30    46    78?  110?
(5 5) (5 6) (5 7) (5 8)

数学的には等比級数っぽいけど、その辺りは忘却の彼方なので、定性的なとこで見てみる。
(m, n)が現れる位置について(i, j)が出現する順番を,とすると
の場合

の場合

の場合

の場合

という感じなので以下のような手続きを実装。

(define (index-pairs x y)
  (cond ((> x y) (error "error x larger than y" x y))
        ((and (= x 0) (= y 0))
         0)
        ((and (>= x 1) (= x y))
         (+ (index-pairs (- x 1) (- y 1)) (expt 2 (- x 1))))
        ((= x 1)
         (* 2 (- y 1)))
        ((= x (- y 1)) 
         (+ (index-pairs x (- y 1)) (expt 2 (- x 1))))
        (else
         (+ (index-pairs x (- y 1)) (expt 2 x)))))

で(1, 100), (100, 100)でそれぞれ実行。

(index-pairs 1 100)
; 198
(index-pairs 100 100)
; 1267650600228229401496703205375