21 lines
697 B
Common Lisp
21 lines
697 B
Common Lisp
;; Memoized computation via recurrence relation
|
|
(let ((memo (make-hash-table)))
|
|
(defun partition-count (n)
|
|
(or (gethash n memo)
|
|
(setf (gethash n memo)
|
|
(cond ((= n 0) 1)
|
|
((< n 0) 0)
|
|
(t
|
|
(flet ((lower-bound (n) (ceiling (- (/ (- (sqrt (+ (* 24 n) 1)) 1) 6))))
|
|
(upper-bound (n) (/ (+ (sqrt (+ (* 24 n) 1)) 1) 6)))
|
|
(loop for k from (lower-bound n) upto (upper-bound n)
|
|
unless (= k 0)
|
|
sum (* (expt -1 (1+ k))
|
|
(partition-count (- n (* k (/ (- (* 3 k) 1) 2)))))))))))))
|
|
|
|
(defun coin-partitions (&optional (divisor 1000000))
|
|
(loop for n upfrom 2
|
|
for p = (partition-count n)
|
|
until (= (mod p divisor) 0)
|
|
finally (return n)))
|