Fermat numbers: Difference between revisions

=={{header|Nim}}==

{{trans|Kotlin}}

{{libheader|bignum}}

<lang Nim>import math

import bignum

import strformat

import strutils

import tables

import times

const Composite = {9: "5529", 10: "6078", 11: "1037", 12: "5488", 13: "2884"}.toTable

const Subscripts = ["₀", "₁", "₂", "₃", "₄", "₅", "₆", "₇", "₈", "₉"]

let One = newInt(1)

#---------------------------------------------------------------------------------------------------

func fermat(n: int): Int {.inline.} = 2^(culong(2^n)) + 1

#---------------------------------------------------------------------------------------------------

template isProbablyPrime(n: Int): bool = n.probablyPrime(25) != 0

#---------------------------------------------------------------------------------------------------

func pollardRhoG(x, n: Int): Int {.inline.} = (x * x + 1) mod n

#---------------------------------------------------------------------------------------------------

proc pollardRhoFast(n: Int): Int =

let start = getTime()

var

x = newInt(2)

y = newInt(2)

count = 0

z = One

while true:

x = pollardRhoG(x, n)

y = pollardRhoG(pollardRhoG(y, n), n)

result = abs(x - y)

z = z * result mod n

inc count

if count == 100:

result = gcd(z, n)

if result != One: break

z = One

count = 0

let duration = (getTime() - start).inMilliseconds

echo fmt" Pollard rho try factor {n} elapsed time = {duration} ms (factor = {result})."

if result == n:

result = newInt(0)

#---------------------------------------------------------------------------------------------------

proc factors(fermatIndex: int; n: Int): seq[Int] =

var n = n

var factor: Int

while true:

if n.isProbablyPrime():

result.add(n)

break

if fermatIndex in Composite:

let stop = Composite[fermatIndex]

let s = $n

if s.startsWith(stop):

result.add(newInt(-s.len))

break

factor = pollardRhoFast(n)

if factor.isZero():

result.add(n)

break

result.add(factor)

n = n div factor

#---------------------------------------------------------------------------------------------------

func `$`(factors: seq[Int]): string =

if factors.len == 1:

result = fmt"{factors[0]} (PRIME)"

else:

result = $factors[0]

let start = result.high

for factor in factors[1..^1]:

result.addSep(" * ", start)

result.add(if factor < 0: fmt"(C{-factor})" else: $factor)

#---------------------------------------------------------------------------------------------------

func subscript(n: Natural): string =

var n = n

while true:

result.insert(Subscripts[n mod 10], 0)

n = n div 10

if n == 0: break

#———————————————————————————————————————————————————————————————————————————————————————————————————

echo "First 10 Fermat numbers:"

for i in 0..9:

echo fmt"F{subscript(i)} = {fermat(i)}"

echo ""

echo "First 12 Fermat numbers factored:"

for i in 0..12:

echo fmt"F{subscript(i)} = {factors(i, fermat(i))}"</lang>

{{out}}

<pre>First 10 Fermat numbers:

F₀ = 3

F₁ = 5

F₂ = 17

F₃ = 257

F₄ = 65537

F₅ = 4294967297

F₆ = 18446744073709551617

F₇ = 340282366920938463463374607431768211457

F₈ = 115792089237316195423570985008687907853269984665640564039457584007913129639937

F₉ = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097

First 12 Fermat numbers factored:

F₀ = 3 (PRIME)

F₁ = 5 (PRIME)

F₂ = 17 (PRIME)

F₃ = 257 (PRIME)

F₄ = 65537 (PRIME)

Pollard rho try factor 4294967297 elapsed time = 0 ms (factor = 641).

F₅ = 641 * 6700417

Pollard rho try factor 18446744073709551617 elapsed time = 1 ms (factor = 274177).

F₆ = 274177 * 67280421310721

Pollard rho try factor 340282366920938463463374607431768211457 elapsed time = 516705 ms (factor = 59649589127497217).

F₇ = 59649589127497217 * 5704689200685129054721

Pollard rho try factor 115792089237316195423570985008687907853269984665640564039457584007913129639937 elapsed time = 20765 ms (factor = 1238926361552897).

F₈ = 1238926361552897 * 93461639715357977769163558199606896584051237541638188580280321

Pollard rho try factor 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097 elapsed time = 3 ms (factor = 2424833).

F₉ = 2424833 * (C148)

Pollard rho try factor 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137217 elapsed time = 46 ms (factor = 45592577).

Pollard rho try factor 3942951359960012586542991835686376608231592127249807732373409846031135195659174148737161255930050543559319182152642816343958573976075461198274610155058226350701077796608546283231637018483208223116080561800334422176622099740983337736621316898600121619871377542107047343253864459964167331555646795960321 elapsed time = 595 ms (factor = 6487031809).

F₁₀ = 45592577 * 6487031809 * (C291)

Pollard rho try factor 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230657 elapsed time = 1 ms (factor = 974849).

Pollard rho try factor 33150781373639412155846573868024639672856106606987835072026893834352453701925006737655987144186344206834820532125383540932102878651453631377873037143648178457002958783669056532601662155256508553423204658756451069116132055982639112479817996775373591674794399801442382402697828988429044712163168243619196804348072710121945390948428910309765481110260333687910970886853046635254307274981520537180895290310783635953818082306553996934497908037349010876970379631341148456045116407475229712217130141926525362871253437794629422541384355185626695660779797862427347553871011957167960991543632376506466281643163047416635393 elapsed time = 11 ms (factor = 319489).

F₁₁ = 974849 * 319489 * (C606)

Pollard rho try factor 1044388881413152506691752710716624382579964249047383780384233483283953907971557456848826811934997558340890106714439262837987573438185793607263236087851365277945956976543709998340361590134383718314428070011855946226376318839397712745672334684344586617496807908705803704071284048740118609114467977783598029006686938976881787785946905630190260940599579453432823469303026696443059025015972399867714215541693835559885291486318237914434496734087811872639496475100189041349008417061675093668333850551032972088269550769983616369411933015213796825837188091833656751221318492846368125550225998300412344784862595674492194617023806505913245610825731835380087608622102834270197698202313169017678006675195485079921636419370285375124784014907159135459982790513399611551794271106831134090584272884279791554849782954323534517065223269061394905987693002122963395687782878948440616007412945674919823050571642377154816321380631045902916136926708342856440730447899971901781465763473223850267253059899795996090799469201774624817718449867455659250178329070473119433165550807568221846571746373296884912819520317457002440926616910874148385078411929804522981857338977648103126085903001302413467189726673216491511131602920781738033436090243804708340403154190337 elapsed time = 11 ms (factor = 114689).

Pollard rho try factor 9106268965752186405773463110818163752233991481723476361152625650968740750826648212547208641935996986118024454955917854702609434541985662158212523327009262247869952450049350838706079834460006786304075107567909269645531121898331250125751682239313156601738683820643686003638396435055834553570682260579462973839574318172464558815116581626749391315641251152532705571615644886981829338611134458123396450764186936496833100701185274214915961723337127995182593580031119299575446791424418154036863609858251201843852076223383379133238000289598800458955855329052103961332983048473420515918928565951506637819342706575976725030506905683310915700945442329953941604008255667676914945655757474715779252371155778495946746587469464160684843488975918662295274965457887082037460184558511575570318625886351712499453155527762335682281851520733417380809781252979478377941937578568481859702438295520231435016188495646093490407803983345420364088331996467459309353537828143080691834120737157445502646809195267166779721413577366833939771467773331873590129210913628329073978766992198221682739812652450408607796042492802295258713711959073218748776359806123717024800451461326745599716651128725627280643537507664130920416107218492950792456907321580171946770433 elapsed time = 18 ms (factor = 26017793).

Pollard rho try factor 350001591824186871106763863899530746217943677302816436473017740242946077356624684213115564488348300185108877411543625345263121839042445381828217455916005721464151569276047005167043946981206545317048033534893189043572263100806868980998952610596646556521480658280419327021257968923645235918768446677220584153297488306270426504473941414890547838382804073832577020334339845312084285496895699728389585187497914849919557000902623608963141559444997044721763816786117073787751589515083702681348245404913906488680729999788351730419178916889637812821243344085799435845038164784900107242721493170135785069061880328434342030106354742821995535937481028077744396075726164309052460585559946407282864168038994640934638329525854255227752926198464207255983432778402344965903148839661825873175277621985527846249416909718758069997783882773355041329208102046913755441975327368023946523920699020098723785533557579080342841062805878477869513695185309048285123705067072486920463781103076554014502567884803571416673251784936825115787932810954867447447568320403976197134736485611912650805539603318790667901618038578533362100071745480995207732506742832634459994375828162163700807237997808869771569154136465922798310222055287047244647419069003284481 elapsed time = 114 ms (factor = 63766529).

F₁₂ = 114689 * 26017793 * 63766529 * (C1213)</pre>