; partition numbers

(define (partition n) ; naive version
  (if (negative? n) 0
    (if (zero? n) 1
      (let loop ((k 1) (sum 0))
        (if (< n k) sum
          (loop (+ k 1)
                (+ sum (* (expt -1 (+ k 1))
                          (+ (partition (- n (* k (- (* 3 k) 1) 1/2)))
                             (partition (- n (* k (+ (* 3 k) 1) 1/2))))))))))))

(display (partition 10)) (newline)

(define partition ; memoized version
  (let ((len 1) (pv (vector 1)))
    (lambda (n)
      (do () ((< n len))
        (let* ((new-len (+ len len)) (new-pv (make-vector new-len #f)))
          (do ((i 0 (+ i 1))) ((= i len))
            (vector-set! new-pv i (vector-ref pv i)))
          (set! len new-len) (set! pv new-pv)))
      (cond ((negative? n) 0) ((zero? n) 1)
            ((and (< n len) (vector-ref pv n)) => (lambda (x) x))
            (else (let loop ((k 1) (sum 0))
                    (if (< n k) (begin (vector-set! pv n sum) sum)
                      (loop (+ k 1) (+ sum (* (expt -1 (+ k 1))
                        (+ (partition (- n (* k (- (* 3 k) 1) 1/2)))
                           (partition (- n (* k (+ (* 3 k) 1) 1/2))))))))))))))

(display (partition 10)) (newline)

(time (display (partition 1000)) (newline))

42
42
24061467864032622473692149727991
cpu time: 240 real time: 1451 gc time: 30