; partition numbers

(define (partition n)
  (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
  (let ((len 1) (pv (vector 1)))
    (define (grow)
      (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)))
    (lambda (n)
      (do () ((< n len)) (grow))
      (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: 430 real time: 3400 gc time: 60