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