이 문제는 라마누잔 수(정확하게는 Hardy-Ramanujan Number이네요.)를 나타내는

그런 스트림을 만드는 문제입니다.

라마누잔 수는 두 수를 세제곱하여 만들어낼 수 있는 방법이 두 가지인 수입니다.

예를 들어 1³ + 12³ = 9³ + 10³ = 1729와 같은 수입니다.

이런 수를 다섯 개 더 찾는 문제입니다.

잘 나오는군요.^^

그 다음 라마누잔 수로 4104, 13832, 20683, 32832, 39312입니다.

어떤 조합인지 확인해보려고 하였으나 다음 문제에서 그런 기회를 줍니다.^^

그래서 다음 문제를 풀었고, 그것을 가져와 수정하였습니다.

위와 같은 조합이군요.

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³

39312 = 15³ + 33³ = 2³ + 34³

복잡하네요.^^;;;;

참조

해럴드 애빌슨, 김재우 역, <컴퓨터 프로그램의 구조와 해석>, 인사이트, 2007, pp. 446

; stream
(define true (= 0 0))
(define false (= 1 0))

(define (cons-stream a b)
  (cons a (delay b)))
(define the-empty-stream '())
(define stream-null? null?)
(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))

; section 3.5
(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))

(define (stream-for-each proc s)
  (if (stream-null? s)
      'done
      (begin (proc (stream-car s))
             (stream-for-each proc (stream-cdr s)))))

(define (display-stream s)
  (stream-for-each display-line s))

(define (display-line x)
  (newline)
  (display x))

(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream
       low
       (stream-enumerate-interval (+ low 1) high))))

(define (stream-filter pred stream)
  (cond ((stream-null? stream) the-empty-stream)
        ((pred (stream-car stream))
         (cons-stream (stream-car stream)
                      (stream-filter pred
                                     (stream-cdr stream))))
        (else (stream-filter pred (stream-cdr stream)))))

(define (memo-proc proc)
  (let ((already-run? false) (result false))
    (lambda ()
      (if (not already-run?)
          (begin (set! result (proc))
                 (set! already-run? true)
                 result)
          result))))

(define (scale-stream stream factor)
  (stream-map (lambda (x) (* x factor)) stream))

; exercise 3.50
(define (stream-map proc . argstreams)
  (if (stream-null? (car argstreams))
      the-empty-stream
      (cons-stream
       (apply proc (map stream-car argstreams))
       (apply stream-map
              (cons proc (map stream-cdr argstreams))))))

;;;SECTION 3.5.2
(define (add-streams s1 s2)
  (stream-map + s1 s2))

(define ones (cons-stream 1 ones))
(define integers (cons-stream 1 (add-streams ones integers)))

; exercise 3.54
(define (mul-streams s1 s2)
  (stream-map * s1 s2))

; exercise 3.55
(define (partial-sums S)
  (cons-stream (stream-car S) (add-streams (stream-cdr S)
                                           (partial-sums S))))

; exercise 3.56
(define (merge s1 s2)
  (cond ((stream-null? s1) s2)
        ((stream-null? s2) s1)
        (else
         (let ((s1car (stream-car s1))
               (s2car (stream-car s2)))
           (cond ((< s1car s2car)
                  (cons-stream s1car (merge (stream-cdr s1) s2)))
                 ((> s1car s2car)
                  (cons-stream s2car (merge s1 (stream-cdr s2))))
                 (else
                  (cons-stream s1car
                               (merge (stream-cdr s1)
                                      (stream-cdr s2)))))))))

; print-stream-n
(define (print-stream-n S n l)
  (define (iter i)
    (if (= i n)
        'done
        (begin (display (stream-ref S i))
               (display "   ")
               (if (= (remainder (+ i 1) l) 0)
                   (newline))
               (iter (+ i 1)))))
  (iter 0))

; exercise 3.59
(define (div-streams s1 s2)
  (stream-map / s1 s2))

(define (integrate-series coff_stm)
  (let ((integrate_s (cons-stream 1 ; 상수 c
                                  (div-streams coff_stm integers))))
    (stream-cdr integrate_s)))

(define exp-series
  (cons-stream 1 (integrate-series exp-series)))
(define cosine-series
  (cons-stream 1
               (integrate-series (scale-stream sine-series -1))))
(define sine-series
  (cons-stream 0
               (integrate-series cosine-series)))

; exercise 3.60
(define (mul-series s1 s2)
  (cons-stream (* (stream-car s1) (stream-car s2))
               (add-streams (mul-series (stream-cdr s1) s2)
                            (scale-stream (stream-cdr s2) (stream-car s1)))))
; exercise 3.61
(define (invert-unit-series S)
  (define X
    (cons-stream 1
                 (scale-stream (mul-series (stream-cdr S) X) -1)))
  X)

; exercise 3.62
; s1 / s2
(define (div-series s1 s2)
  (if (= 0 (stream-car s2))
      (error "Divide by zero" s2)
      (mul-series s1 (invert-unit-series s2))))

; exercise 3.63
(define (sqrt-improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (sqrt-stream x)
  (define guesses
    (cons-stream 1.0
                 (stream-map (lambda (guess)
                               (sqrt-improve guess x))
                             guesses)))
  guesses)

; exercise 3.64
(define (stream-limit stm tolerance)
  (let ((element1 (stream-car stm)) ; 앞의 원소
        (element2 (stream-car (stream-cdr stm)))) ; 뒤의 원소
    (if (< (abs (- element1 element2)) tolerance)
        element2
        (stream-limit (stream-cdr stm) tolerance))))
(define (sqrt x tolerance)
  (stream-limit (sqrt-stream x) tolerance))

; exercise 3.65
(define ln2-stream
  (partial-sums (ln2-summands 1)))
(define (ln2-summands n)
  (cons-stream (/ 1.0 n)
               (stream-map - (ln2-summands (+ n 1)))))

(define (euler-transform s)
  (let ((s0 (stream-ref s 0))           ; Sn-1
        (s1 (stream-ref s 1))           ; Sn
        (s2 (stream-ref s 2)))          ; Sn+1
    (cons-stream (- s2 (/ (square (- s2 s1))
                          (+ s0 (* -2 s1) s2)))
                 (euler-transform (stream-cdr s)))))

(define (make-tableau transform s)
  (cons-stream s
               (make-tableau transform
                             (transform s))))

(define (accelerated-sequence transform s)
  (stream-map stream-car
              (make-tableau transform s)))

(define (square x) (* x x))

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

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

; exercise 3.70
(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 s2car)
                  (cons-stream s1car (merge-weighted (stream-cdr s1) s2 weight)))
                 (else
                  (cons-stream s2car (merge-weighted s1 (stream-cdr s2) weight))))))))

(define (weighted-pairs s t weight)
  (cons-stream
   (list (stream-car s) (stream-car t))
   (merge-weighted
    (stream-map (lambda (x) (list (stream-car s) x))
                (stream-cdr t))
    (weighted-pairs (stream-cdr s) (stream-cdr t) weight)
    weight)))

; exercise 3.71
(define (cube x) (* x x x))

(define (Ramanujan-stream-filter stream)
  (let ((x (stream-car stream))
        (y (stream-car (stream-cdr stream))))
    (cond ((stream-null? stream) the-empty-stream)
          ((= x y)
           (cons-stream (stream-car stream)
                        (Ramanujan-stream-filter (stream-cdr stream))))
          (else (Ramanujan-stream-filter (stream-cdr stream))))))

(define Ramanujan
  (Ramanujan-stream-filter
   (stream-map (lambda (x)
                 (let ((i (car x))
                       (j (cadr x)))
                   (+ (cube i) (cube j))))
               (weighted-pairs integers
                               integers
                               (lambda (x y)
                                 (let ((xi (car x))
                                       (xj (cadr x))
                                       (yi (car y))
                                       (yj (cadr y)))
                                   (< (+ (cube xi) (cube xj))
                                      (+ (cube yi) (cube yj)))))))))

(define (Ramanujan-list-stream-filter stream)
  (let ((x (stream-car stream))
        (y (stream-car (stream-cdr stream))))
    (let ((x_cube_sum (+ (cube (car x)) (cube (cadr x))))
          (y_cube_sum (+ (cube (car y)) (cube (cadr y)))))
      (cond ((stream-null? stream) the-empty-stream)
            ((= x_cube_sum y_cube_sum)
             (cons-stream (list x_cube_sum x y)
                          (Ramanujan-list-stream-filter (stream-cdr stream))))
            (else (Ramanujan-list-stream-filter (stream-cdr stream)))))))

(define Ramanujan-list
  (Ramanujan-list-stream-filter
   (weighted-pairs integers
                   integers
                   (lambda (x y)
                     (let ((xi (car x))
                           (xj (cadr x))
                           (yi (car y))
                           (yj (cadr y)))
                       (< (+ (cube xi) (cube xj))
                          (+ (cube yi) (cube yj))))))))

; execute
(print-stream-n Ramanujan 6 6)
(newline)
(print-stream-n Ramanujan-list 6 1)

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.