Sorry, forgot to post the following to the users list.
Hi,
count partitions, much faster and exact.
You may want to put the hash or part of it within function p such as to
avoid spllling much memory.
Jos
#lang racket
(require math/number-theory)
(define p-hash (make-hash '((0 . 1))))
(define (p n)
(hash-ref! p-hash n
(λ ()
(+
(let loop ((k 1) (m (sub1 n)) (s 0))
(if (< m 0) s
(loop (add1 k) (- m (add1 (* 3 k))) (if (odd? k) (+ s (p m)) (- s (p
m))))))
(let loop ((k -1) (m (- n 2)) (s 0))
(if (< m 0) s
(loop (sub1 k) (+ m (* 3 k) -2) (if (odd? k) (+ s (p m)) (- s (p
m))))))))))
(time (for ((n (in-range 0 1000))) (p n)))
(time (for ((n (in-range 0 1000))) (partitions n)))
(void (time (p 10000)))
(for/and ((n (in-range 0 1000))) (= (partitions n) (p n)))
(read-line)
; results with racket:
; cpu time: 16 real time: 16 gc time: 0
; cpu time: 8845 real time: 8845 gc time: 111
; cpu time: 577 real time: 578 gc time: 0
; #t
____________________
Racket Users list:
http://lists.racket-lang.org/users
