Fermat numbers: Difference between revisions
Added Common Lisp
No edit summary |
(Added Common Lisp) |
||
Line 207:
F(8): 1238926361552897, 93461639715357977769163558199606896584051237541638188580280321
</pre>
=={{header|Common Lisp|}}==
{{trans|Lisp}}
This uses the 'factor' function defined in the page Prime Decomposition
http://rosettacode.org/wiki/Prime_decomposition#Common_Lisp
<lang Lisp>
(defun fermat-number (n)
"Return the n-th Fermat number"
(1+ (expt 2 (expt 2 n))) )
(defun factor (n &optional (acc '()))
"Return the list of factors of n"
(when (> n 1) (loop with max-d = (isqrt n)
for d = 2 then (if (evenp d) (1+ d) (+ d 2)) do
(cond ((> d max-d) (return (cons (list n 1) acc)))
((zerop (rem n d))
(return (factor (truncate n d) (if (eq d (caar acc))
(cons
(list (caar acc) (1+ (cadar acc)))
(cdr acc))
(cons (list d 1) acc)))))))))
</lang>
{{out}}
<pre>
(dotimes (i 8) (format t "~d: ~d = ~d~%" i (fermat-number i) (factors (fermat-number i))))
0: 3 = (3)
1: 5 = (5)
2: 17 = (17)
3: 257 = (257)
4: 65537 = (65537)
5: 4294967297 = (641 6700417)
6: 18446744073709551617 = (274177 (67280421310721))
7: 340282366920938463463374607431768211457 = ((340282366920938463463374607431768211457))
8: 115792089237316195423570985008687907853269984665640564039457584007913129639937 = ((115792089237316195423570985008687907853269984665640564039457584007913129639937))
9: 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097 = ((13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097))
10: 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137217 = ((179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137217))
11: 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230657 = (319489
(101152171346465785365739905563790778275446424351747584524444802254614885454171789617787158279386499891040749324458425859713854183244152133860909616251101863039512713637405344446131784663602352840930541077733717180487566766438342966931062084574042206368862921265008513729385286790910065162204496552694867070609361616173540692858549041708993328392702647150062512506151403207406283761595736673720405375033810606080158013948717662760215065784116654734290374983906448207065425365852408720566771005345821995341556493590254118091846659097349200248570452085641250044738949182704974520704370036542579394575574913724915713))
12: 1044388881413152506691752710716624382579964249047383780384233483283953907971557456848826811934997558340890106714439262837987573438185793607263236087851365277945956976543709998340361590134383718314428070011855946226376318839397712745672334684344586617496807908705803704071284048740118609114467977783598029006686938976881787785946905630190260940599579453432823469303026696443059025015972399867714215541693835559885291486318237914434496734087811872639496475100189041349008417061675093668333850551032972088269550769983616369411933015213796825837188091833656751221318492846368125550225998300412344784862595674492194617023806505913245610825731835380087608622102834270197698202313169017678006675195485079921636419370285375124784014907159135459982790513399611551794271106831134090584272884279791554849782954323534517065223269061394905987693002122963395687782878948440616007412945674919823050571642377154816321380631045902916136926708342856440730447899971901781465763473223850267253059899795996090799469201774624817718449867455659250178329070473119433165550807568221846571746373296884912819520317457002440926616910874148385078411929804522981857338977648103126085903001302413467189726673216491511131602920781738033436090243804708340403154190337 = (114689
(9106268965752186405773463110818163752233991481723476361152625650968740750826648212547208641935996986118024454955917854702609434541985662158212523327009262247869952450049350838706079834460006786304075107567909269645531121898331250125751682239313156601738683820643686003638396435055834553570682260579462973839574318172464558815116581626749391315641251152532705571615644886981829338611134458123396450764186936496833100701185274214915961723337127995182593580031119299575446791424418154036863609858251201843852076223383379133238000289598800458955855329052103961332983048473420515918928565951506637819342706575976725030506905683310915700945442329953941604008255667676914945655757474715779252371155778495946746587469464160684843488975918662295274965457887082037460184558511575570318625886351712499453155527762335682281851520733417380809781252979478377941937578568481859702438295520231435016188495646093490407803983345420364088331996467459309353537828143080691834120737157445502646809195267166779721413577366833939771467773331873590129210913628329073978766992198221682739812652450408607796042492802295258713711959073218748776359806123717024800451461326745599716651128725627280643537507664130920416107218492950792456907321580171946770433))</pre>
=={{header|Crystal|}}==
| |||