sicp exercise 3.71

;; Exercise 3.71.  Numbers that can be expressed as the sum of two cubes in more than one way are sometimes called Ramanujan numbers, in honor of the mathematician Srinivasa Ramanujan.70 Ordered streams of pairs provide an elegant solution to the problem of computing these numbers. To find a number that can be written as the sum of two cubes in two different ways, we need only generate the stream of pairs of integers (i,j) weighted according to the sum i3 + j3 (see exercise 3.70), then search the stream for two consecutive pairs with the same weight. Write a procedure to generate the Ramanujan numbers. The first such number is 1,729. What are the next five?


(define (display-line str)
  (display str)
  (newline))

(define (display-stream str num)
  (define (internal index)
    (if (> index num) 'printed
        (begin
          (display-line (stream-ref str index))
          (internal (+ 1 index)))))
  (newline)
  (internal 0))

(define (integers-from-n n)
  (cons-stream n (integers-from-n (+ 1 n))))

(define integers (integers-from-n 1))

(define (merge-weighted s1 s2 weight)
  (cond ((stream-null? s1) s2)
        ((stream-null? s2) s1)
        (else
         (let ((s1car (stream-car s1))
               (s2car (stream-car s2)))
           (cond ((< (weight s1car) (weight s2car))
                  (cons-stream s1car (merge-weighted (stream-cdr s1) s2 weight)))
                 (else
                  (cons-stream s2car (merge-weighted s1 (stream-cdr s2) weight))))))))

(define (f1 s t)
  (cons-stream (list (stream-car s) (stream-car t))
               (f1 s (stream-cdr t))))
(define (f0 s t weight)
  (cons-stream (list (stream-car s) (stream-car t))
               (merge-weighted (f1 s (stream-cdr t))
                               (f0 (stream-cdr s) (stream-cdr t) weight)
                               weight)))
(define (weighted-pairs s t weight) (f0 s t weight))

(define (cube x)(* x x x))
(define cube-weighted-pairs (weighted-pairs integers integers (lambda(s)(+ (cube (car s)) (cube (cadr s))))))
;(display-stream cube-weighted-pairs 20)

(define (check-eq-weight s weight)
  (let ((a (stream-car s))
        (b (stream-car (stream-cdr s))))
    (if (= (weight a) (weight b))
        (cons-stream (list (weight a) a b)
                     (check-eq-weight (stream-cdr s) weight))
        (check-eq-weight (stream-cdr s) weight))))

(define ramanujan-numbers (check-eq-weight cube-weighted-pairs (lambda(s)
                                                                 (+ (cube (car s))
                                                                    (cube (cadr s))))))

(display-stream ramanujan-numbers 4)

;Loading "sicp_prob_03.71.scm"...
;(1729 (9 10) (1 12))
;(4104 (9 15) (2 16))
;(13832 (18 20) (2 24))
;(20683 (19 24) (10 27))
;(32832 (18 30) (4 32))
;... done