Skip to content

joshroybal/sicp-streams

Repository files navigation

sicp-streams

SICP style streams implemented in Common Lisp.
Special thanks to Abelson, the Sussmans, Eli Bendersky, and jcs at irreal.org.
I ported the SICP code from MIT Scheme to CL, but periodically checked how badly
I had gone astray at https://eli.thegreenplace.net/2007/11/05/sicp-sections-351-352
and https://irreal.org/blog/?p=3632 .
So far I have finding the nth prime and nth twin-prime pair as demos.
Many more that have not been uploaded as of now.
(main driver demo) Usage: sbcl --script driver.lisp
Usage: sbcl --script nth-prime.lisp n
Usage: sbcl --script nth-twin-prime-pair.lisp n
Usage: sbcl --script nth-triangular.lisp n
Below yields prime-factorization of n.
Usage: sbcl --script prime-factorization.lisp n
Below yields prime-factorizations of first n composite numbers.
Usage: sbcl --script prime-factorizations.lisp n
Below yields first n semiprimes and their prime-factorization.
Usage: sbcl --script semiprimes.lisp n
Example runs:

sbcl --script driver.lisp
 2 digits
 74 (2 37)
 49 (7 7)
 18 (2 3 3)
 27 (3 3 3)
 48 (2 2 2 2 3)
 77 (7 11)
 26 (2 13)
 24 (2 2 2 3)
 32 (2 2 2 2 2)
 76 (2 2 19)
 96 (2 2 2 2 2 3)
 94 (2 47)
 31 (31)
 16 (2 2 2 2)
 50 (2 5 5)
 82 (2 41)
 55 (5 11)
 45 (3 3 5)
 50 (2 5 5)
 51 (3 17)
 3 digits
 364 (2 2 7 13)
 792 (2 2 2 3 3 11)
 264 (2 2 2 3 11)
 166 (2 83)
 814 (2 11 37)
 595 (5 7 17)
 585 (3 3 5 13)
 718 (2 359)
 383 (383)
 271 (271)
 421 (421)
 686 (2 7 7 7)
 566 (2 283)
 330 (2 3 5 11)
 254 (2 127)
 768 (2 2 2 2 2 2 2 2 3)
 546 (2 3 7 13)
 841 (29 29)
 899 (29 31)
 907 (907)
 4 digits
 2158 (2 13 83)
 2288 (2 2 2 2 11 13)
 4321 (29 149)
 3289 (11 13 23)
 7109 (7109)
 8081 (8081)
 2315 (5 463)
 9960 (2 2 2 3 5 83)
 1044 (2 2 3 3 29)
 5072 (2 2 2 2 317)
 9083 (31 293)
 8836 (2 2 47 47)
 2310 (2 3 5 7 11)
 6058 (2 13 233)
 1375 (5 5 5 11)
 2039 (2039)
 4002 (2 3 23 29)
 8569 (11 19 41)
 8373 (3 2791)
 7825 (5 5 313)
 5 digits
 56091 (3 7 2671)
 43642 (2 21821)
 55298 (2 43 643)
 28981 (73 397)
 38368 (2 2 2 2 2 11 109)
 41430 (2 3 5 1381)
 97920 (2 2 2 2 2 2 2 3 3 5 17)
 82465 (5 16493)
 61671 (3 61 337)
 10135 (5 2027)
 76604 (2 2 11 1741)
 16776 (2 2 2 3 3 233)
 97360 (2 2 2 2 5 1217)
 68459 (17 4027)
 75745 (5 15149)
 98856 (2 2 2 3 3 1373)
 65081 (151 431)
 17652 (2 2 3 1471)
 70525 (5 5 7 13 31)
 24990 (2 3 5 7 7 17)
 6 digits
 750551 (281 2671)
 948065 (5 189613)
 677697 (3 223 1013)
 854607 (3 13 17 1289)
 834074 (2 417037)
 413009 (413009)
 782008 (2 2 2 239 409)
 670278 (2 3 7 15959)
 482919 (3 17 17 557)
 343371 (3 7 83 197)
 697034 (2 13 17 19 83)
 192606 (2 3 47 683)
 867884 (2 2 17 12763)
 430874 (2 97 2221)
 541408 (2 2 2 2 2 7 2417)
 728229 (3 17 109 131)
 667485 (3 3 5 7 13 163)
 538664 (2 2 2 7 9619)
 369010 (2 5 36901)
 832572 (2 2 3 3 3 13 593)
 7 digits
 3050073 (3 3 13 131 199)
 1253607 (3 417869)
 9637636 (2 2 19 211 601)
 8246375 (5 5 5 37 1783)
 5626343 (5626343)
 9725270 (2 5 193 5039)
 1797843 (3 599281)
 7621857 (3 3 3 3 73 1289)
 8708069 (8708069)
 1620864 (2 2 2 2 2 2 2 3 3 3 7 67)
 8180979 (3 397 6869)
 4290166 (2 2145083)
 9916849 (9916849)
 8805975 (3 5 5 117413)
 6199945 (5 1239989)
 5216753 (5216753)
 5699551 (11 13 39857)
 6912631 (11 53 71 167)
 3958549 (7 565507)
 4809071 (19 253109)
 8 digits
 86477531 (7 19 163 3989)
 45881951 (45881951)
 62944153 (62944153)
 89637070 (2 5 41 218627)
 45415235 (5 9083047)
 87476875 (5 5 5 5 67 2089)
 16146050 (2 5 5 322921)
 83158967 (293 463 613)
 50536085 (5 193 52369)
 71912782 (2 35956391)
 97091288 (2 2 2 7 389 4457)
 12785143 (7 29 62981)
 37132200 (2 2 2 3 3 5 5 7 7 421)
 38021587 (38021587)
 93740795 (5 37 47 10781)
 83766331 (11 269 28309)
 47606090 (2 5 7 23 29569)
 55846211 (55846211)
 52404862 (2 59 444109)
 59753554 (2 7 31 131 1051)
 9 digits
 186504250 (2 5 5 5 746017)
 445492364 (2 2 111373091)
 124590361 (7 2341 7603)
 610426939 (17 61 588647)
 774112078 (2 387056039)
 243670192 (2 2 2 2 271 56197)
 849464288 (2 2 2 2 2 29 457 2003)
 956403641 (23 163 337 757)
 411889902 (2 3 68648317)
 816385304 (2 2 2 7 149 97841)
 909856601 (20443 44507)
 506930557 (7 23 61 71 727)
 247195424 (2 2 2 2 2 7 61 79 229)
 739600647 (3 246533549)
 600076596 (2 2 3 7 283 25243)
 425712814 (2 43 1697 2917)
 263115620 (2 2 5 13155781)
 456739542 (2 3 3 7 3624917)
 568039914 (2 3 3 13 2427521)
 704196440 (2 2 2 5 17 137 7559)
 10 digits
 5673223579 (37 153330367)
 8994754770 (2 3 5 299825159)
 2181649217 (11 19 941 11093)
 4149114981 (3 11 733 171529)
 6660427340 (2 2 5 7 47 173 5851)
 8559322352 (2 2 2 2 7 7 10917503)
 8694115856 (2 2 2 2 71 7653271)
 5698784990 (2 5 569878499)
 3641152980 (2 2 3 5 37 47 34897)
 9666630133 (19 508770007)
 2126770194 (2 3 127 2791037)
 3663808438 (2 29 79 799609)
 2812426707 (3 937475569)
 5970315801 (3 23629 84223)
 7267040722 (2 37 98203253)
 8027159360 (2 2 2 2 2 2 5 11 11 379 547)
 5655807471 (3 1885269157)
 6994590449 (7 11 17 587 9103)
 6182599609 (27061 228469)
 8622255826 (2 8123 530731)
 11 digits
 68983154633 (73 367 773 3331)
 39771532980 (2 2 3 3 3 3 3 5 17 481379)
 36482517441 (3 3 44579 90931)
 94323891588 (2 2 3 857 9171907)
 38941205112 (2 2 2 3 3 3 180283357)
 65827091087 (41 1483 1082629)
 47981306436 (2 2 3 7 571206029)
 86685724308 (2 2 3 521 997 13907)
 21124608345 (3 3 5 71 2311 2861)
 21920838425 (5 5 53 97 170557)
 26474271454 (2 269 49208683)
 70138297807 (23 11047 276047)
 64110865414 (2 10723 2989409)
 34635700129 (479 72308351)
 66091714573 (1949 33910577)
 49133773031 (7 17 412888849)
 88859494016 (2 2 2 2 2 2 2 1361 510077)
 86453406198 (2 3 3 4802967011)
 15476078839 (13 13 13 23 29 59 179)
 76037135126 (2 131 1601 181273)
 12 digits
 357177925089 (3 3 127 312491623)
 863351094036 (2 2 3 191 2657 141769)
 321827085405 (3 3 5 7 1021673287)
 127548160323 (3 42516053441)
 203163629742 (2 3 3 19 193 787 3911)
 233472056888 (2 2 2 7 1747 2386459)
 841152613396 (2 2 131 1605253079)
 974368905862 (2 11 59 541 971 1429)
 606665191146 (2 3 7 14444409313)
 621704302358 (2 47 6613875557)
 844134380464 (2 2 2 2 52758398779)
 332203068519 (3 7 15819193739)
 143564113520 (2 2 2 2 5 1741 1030759)
 818805884522 (2 733 558530617)
 142414862282 (2 7 11 23 40207471)
 313626840785 (5 62725368157)
 794352731688 (2 2 2 3 3 3 3 89 13773629)
 870054830610 (2 3 5 7 43 96351587)
 833284033139 (191 277 15749977)
 140763030010 (2 5 1109 12692789)
 13 digits
 6823528775197 (23 137 157 13793071)
 8224927469677 (8224927469677)
 3897881749319 (37 105348155387)
 1684219726959 (3 7 11 68507 106427)
 9136134786197 (23159 394496083)
 9239262981815 (5 29 151 421980497)
 6095019323165 (5 47 743 34907473)
 5348948776665 (3 5 13 809 5419 6257)
 2378079641436 (2 2 3 198173303453)
 7475139277958 (2 11 17 19987003417)
 3334536249892 (2 2 833634062473)
 5748522075165 (3 5 383234805011)
 1950374807581 (1021 1910259361)
 8158695107036 (2 2 2039673776759)
 3174165721643 (7 241 1881544589)
 7839138005636 (2 2 7 73 643 5964533)
 7513989902056 (2 2 2 11 15383 5550689)
 9789440304945 (3 5 7 47 83 1013 23593)
 2761925742592 (2 2 2 2 2 2 2 2 2 2 2 2 19 53 669611)
 2772201789668 (2 2 693050447417)
 14 digits
 79396448488895 (5 401 39599226179)
 24636178277488 (2 2 2 2 47 271 457 264527)
 78759349216786 (2 7 919 1249 4901129)
 59999156689863 (3 31357 637807153)
 69407988871730 (2 5 129803 53471791)
 88234081498516 (2 2 17 631 2056355027)
 67326372291717 (3 3 7 11 97152052369)
 70290251152375 (5 5 5 29 57223 338857)
 34232052984199 (7 4890293283457)
 83357381571201 (3 3 3 193 15996427091)
 58073445163881 (3 3 3 7 65993 4656053)
 58542756667731 (3 3 3 7 491 7351 85819)
 87045622172954 (2 43522811086477)
 12137251315091 (7 23 71 211 5032151)
 37008423526610 (2 5 3700842352661)
 42127241663594 (2 10061 2093591177)
 45324787578705 (3 3 5 4637 217213177)
 54266543418683 (5563 6719 1451839)
 54273987288793 (899401 60344593)
 98061239417090 (2 5 9806123941709)
 15 digits
 691647412847213 (17 23 71 2741 9089513)
 768091619157859 (4156039 184813381)
 261387358518106 (2 113 1201 27763 34687)
 287380118480708 (2 2 11 6531366329107)
 260143500801268 (2 2 7 151 1553 39619277)
 592651174658219 (37 263 397 153409117)
 471447311525012 (2 2 117861827881253)
 857293357773382 (2 107 811 10163 486041)
 337800220316065 (5 13 5196926466401)
 166333230384531 (3 7 7920630018311)
 317641716347960 (2 2 2 5 457 21787 797561)
 235765951605377 (235765951605377)
 306159497126123 (286673 1067974651)
 152745097584779 (7 36383 599750659)
 426411948661698 (2 3 967 9631 7630979)
 910898240197021 (910898240197021)
 315333950536315 (5 933061 67591283)
 138211330100654 (2 719 3041 31605913)
 854105150602715 (5 11 11 1411744050583)
 123928983373598 (2 13 2087 2283900029)
 16 digits
 1201619245005448 (2 2 2 31 131 36986556421)
 6862744757315507 (6862744757315507)
 3312585998514577 (25307 130896036611)
 9303974372998527 (3 13719857 226046437)
 2917465870400392 (2 2 2 307 1187893269707)
 6868609522427071 (89 77175387892439)
 2618638199944015 (5 25309 20693335967)
 1734034014297791 (83 4157 5025733961)
 9504850326069910 (2 5 7 211 643524057283)
 6962595161223692 (2 2 773 2251809560551)
 5295961539248603 (107 49494967656529)
 4882893935352426 (2 3 3 7 41 945198206611)
 5223817550638304 (2 2 2 2 2 101 2029 796589543)
 9409511100599741 (9409511100599741)
 3936427693840670 (2 5 7 1831 8123 3780937)
 1231656301285630 (2 5 11 83 2777 48578363)
 5299558182531787 (103 1060393 48521653)
 6835883936994349 (17 13901 28926754897)
 9557843177112055 (5 7 7 907 43011692177)
 4067442882575334 (2 3 3 2063 109534197301)
 17 digits
 17158552779175444 (2 2 7 13 47138881261471)
 73992266581026427 (96677939 765347993)
 37941651747293440 (2 2 2 2 2 2 2 2 5 7789 3805612457)
 25315618633899361 (43 4423 115727 1150187)
 84531504668405604 (2 2 3 139 197 521 1511 326779)
 41350158317757026 (2 23 211 2129 7529 265781)
 79719812453462041 (7 1901 5990817799163)
 32572681344887231 (47 137 223 50363 450421)
 66594879596592025 (5 5 7 283 209861 6407441)
 19230669809299994 (2 31 83 127 5641 5216327)
 84268652849439501 (3 5419 1146049 4522957)
 50592148986723909 (3 89 1223 154933527449)
 98445428318431268 (2 2 72901 213229 1583273)
 53388714512361197 (73 463 1579594500203)
 33559816343950730 (2 5 32299 103903577027)
 96151567959654884 (2 2 17 19 41 811 2238149777)
 29025207431546170 (2 5 13 271 8011 102843289)
 10047404095127361 (3 3 41 3067 8877971107)
 71744699994531988 (2 2 23 779833695592739)
 17849309674088954 (2 41 179 239 41011 124067)
 18 digits
 131886396162853173 (3 3 19597 80387 9302123)
 977771984811849087 (3 7 46560570705326147)
 900402360750478388 (2 2 11 8377 2442842308351)
 519381454634884690 (2 5 51938145463488469)
 645899360838641453 (991 941123 692539921)
 329096707292861621 (233 5101259 276879143)
 158867917465944622 (2 13 41 43 47 73741621727)
 638702069953088117 (83 14767 521108259097)
 864388141028588606 (2 71 727 8373095501759)
 258721521580954948 (2 2 1249 51785732902513)
 232863260134678527 (3 77621086711559509)
 598010210723484530 (2 5 47 71 84629 211754761)
 583192753783220936 (2 2 2 173 421382047531229)
 153706039989351497 (53327111 2882324527)
 482686936539405029 (23 14533063 1444044421)
 831013681041445245 (3 5 74383 744806099101)
 966208336045431545 (5 11 599 1059433 27682657)
 816924905250621128 (2 2 2 13 7129 1101844180933)
 438515453711988175 (5 5 353 1319 37672582561)
 726421979290418501 (2503 8168101 35530967)

sbcl --script nth-prime.lisp 4000
37813

sbcl --script nth-twin-prime-pair.lisp 4000
(424769. 424771)

sbcl --script nth-triangular.lisp 4000
 8002000

sbcl --script prime-factorization.lisp 281474976710619
(3 3 1187 26347933793)

sbcl --script prime-factorizations.lisp 20
 4 (2 2)
 6 (2 3)
 8 (2 2 2)
 9 (3 3)
 10 (2 5)
 12 (2 2 3)
 14 (2 7)
 15 (3 5)
 16 (2 2 2 2)
 18 (2 3 3)
 20 (2 2 5)
 21 (3 7)
 22 (2 11)
 24 (2 2 2 3)
 25 (5 5)
 26 (2 13)
 27 (3 3 3)
 28 (2 2 7)
 30 (2 3 5)
 32 (2 2 2 2 2)

sbcl --script semiprimes.lisp 20
 4 (2 2)
 6 (2 3)
 9 (3 3)
 10 (2 5)
 14 (2 7)
 15 (3 5)
 21 (3 7)
 22 (2 11)
 25 (5 5)
 26 (2 13)
 33 (3 11)
 34 (2 17)
 35 (5 7)
 38 (2 19)
 39 (3 13)
 46 (2 23)
 49 (7 7)
 51 (3 17)
 55 (5 11)
 57 (3 19)

About

SICP style streams implemented in Common Lisp

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages