Partition function P: Difference between revisions
Content added Content deleted
m (→{{header|Racket}}: stub) |
|||
Line 1,206: | Line 1,206: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
Backwards range was used to get responsive feedback for progress. |
|||
<lang racket>#lang racket |
|||
(require math/number-theory) |
|||
(define σ |
|||
(let ((memo (make-hash))) |
|||
(λ (z) |
|||
(hash-ref! memo z |
|||
(λ () (apply + (divisors z))))))) |
|||
(define p |
|||
(let ((memo (make-hash '((0 . 1))))) |
|||
(λ (n) |
|||
(hash-ref! |
|||
memo n |
|||
(λ () |
|||
(let ((r (if (zero? n) 1 |
|||
(/ (for/sum ((k (in-range (sub1 n) -1 -1))) |
|||
(* (σ (- n k)) |
|||
(p k))) |
|||
n)))) |
|||
(when (zero? (modulo n 1000)) (displayln (cons n r) (current-error-port))) |
|||
r)))))) |
|||
(map p (range 1 30)) |
|||
(p 666) |
|||
(p 1000) |
|||
(p 10000)</lang> |
|||
{{out}} |
|||
<pre>'(1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 297 385 490 627 792 1002 1255 1575 1958 2436 3010 3718 4565) |
|||
11956824258286445517629485 |
|||
(1000 . 24061467864032622473692149727991) |
|||
24061467864032622473692149727991 |
|||
(2000 . 4720819175619413888601432406799959512200344166) |
|||
(3000 . 496025142797537184410324879054927095334462742231683423624) |
|||
(4000 . 1024150064776551375119256307915896842122498030313150910234889093895) |
|||
(5000 . 169820168825442121851975101689306431361757683049829233322203824652329144349) |
|||
(6000 . 4671727531970209092971024643973690643364629153270037033856605528925072405349246129) |
|||
(7000 . 32856930803440615786280925635924166861950151574532240659699032157432236394374450791229199) |
|||
(8000 . 78360264351568349490593145013364599719010769352985864331118600209417827764524450990388402844164) |
|||
(9000 . 77133638117808884907320791427403134961639798322072034262647713694605367979684296948790335590435626459) |
|||
(10000 . 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435144) |
|||
36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435144</pre> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |