Factoring
Last Updated: July 18, 2016
Author: Aaron Blumenfeld
This is a small Python script that implements a variant of the Pollard-Rho algorithm for factoring integers. It tends to find smaller factors faster. It seems to work well on test input though (the test input I have in the source file is a 44 digit integer). It should find a factor within O(sqrt(n)) iterations, otherwise it chooses a new random function f of the form f(x) = ax^2 + b. In addition to finding all prime factors, there's a function that takes in all prime factors and spits out all factors.
Below is the sample output:
Let's factor 65971141111103266108117109101110102101108100.
The factors are: [2, 2, 3, 5, 5, 29, 71, 647753, 7030757, 118428421, 198019944741939433].
Let's multiply the factors together to make sure our result is correct. The product over our list is: 65971141111103266108117109101110102101108100.
...and the original number minus this product is 0.
Now let's generate a list of all factors of 65971141111103266108117109101110102101108100.
There are 1152 factors, and they are:
[1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 25, 29, 30, 50, 58, 60, 71, 75, 87, 100, 116, 142, 145, 150, 174, 213, 284, 290, 300, 348, 355, 426, 435, 580, 710, 725, 852, 870, 1065, 1420, 1450, 1740, 1775, 2059, 2130, 2175, 2900, 3550, 4118, 4260, 4350, 5325, 6177, 7100, 8236, 8700, 10295, 10650, 12354, 20590, 21300, 24708, 30885, 41180, 51475, 61770, 102950, 123540, 154425, 205900, 308850, 617700, 647753, 1295506, 1943259, 2591012, 3238765, 3886518, 6477530, 7030757, 7773036, 9716295, 12955060, 14061514, 16193825, 18784837, 19432590, 21092271, 28123028, 32387650, 35153785, 37569674, 38865180, 42184542, 45990463, 48581475, 56354511, 64775300, 70307570, 75139348, 84369084, 91980926, 93924185, 97162950, 105461355, 112709022, 118428421, 137971389, 140615140, 175768925, 183961852, 187848370, 194325900, 203891953, 210922710, 225418044, 229952315, 236856842, 275942778, 281772555, 351537850, 355285263, 375696740, 407783906, 421845420, 459904630, 469620925, 473713684, 499183747, 527306775, 551885556, 563545110, 592142105, 611675859, 689856945, 703075700, 710570526, 815567812, 919809260, 939241850, 998367494, 1019459765, 1054613550, 1127090220, 1149761575, 1184284210, 1223351718, 1333723427, 1379713890, 1408862775, 1421141052, 1497551241, 1776426315, 1878483700, 1996734988, 2038919530, 2109227100, 2299523150, 2368568420, 2446703436, 2495918735, 2667446854, 2759427780, 2817725550, 2960710525, 2995102482, 3058379295, 3434424209, 3449284725, 3552852630, 4001170281, 4077839060, 4599046300, 4991837470, 5097298825, 5334893708, 5635451100, 5921421050, 5990204964, 6116758590, 6668617135, 6868848418, 6898569450, 7105705260, 7487756205, 8002340562, 8408417891, 8882131575, 9983674940, 10194597650, 10303272627, 11842842100, 12233517180, 12479593675, 13337234270, 13737696836, 13797138900, 14476328663, 14975512410, 15291896475, 16004681124, 16816835782, 17172121045, 17764263150, 20005851405, 20389195300, 20606545254, 24959187350, 25225253673, 26674468540, 28952657326, 29951024820, 30583792950, 33343085675, 33633671564, 34344242090, 35528526300, 37438781025, 40011702810, 41213090508, 42042089455, 43428985989, 49918374700, 50450507346, 51516363135, 57905314652, 61167585900, 66686171350, 68688484180, 72381643315, 74877562050, 80023405620, 84084178910, 85860605225, 86857971978, 100029257025, 100901014692, 103032726270, 126126268365, 133372342700, 144763286630, 149755124100, 168168357820, 171721210450, 173715943956, 200058514050, 206065452540, 210210447275, 217144929945, 243844118839, 252252536730, 257581815675, 289526573260, 343442420900, 361908216575, 400117028100, 420420894550, 434289859890, 487688237678, 504505073460, 515163631350, 630631341825, 723816433150, 731532356517, 840841789100, 868579719780, 975376475356, 1030327262700, 1085724649725, 1219220594195, 1261262683650, 1447632866300, 1463064713034, 2171449299450, 2438441188390, 2522525367300, 2926129426068, 3657661782585, 4342898598900, 4554193939021, 4876882376780, 6096102970975, 7315323565170, 9108387878042, 12192205941950, 13662581817063, 14630647130340, 18216775756084, 18288308912925, 22770969695105, 24384411883900, 27325163634126, 36576617825850, 45541939390210, 54650327268252, 68312909085315, 73153235651700, 76712364988013, 91083878780420, 113854848475525, 132071624231609, 136625818170630, 153424729976026, 227709696951050, 230137094964039, 264143248463218, 273251636341260, 306849459952052, 323347769670491, 341564545426575, 383561824940065, 396214872694827, 455419393902100, 460274189928078, 528286496926436, 646695539340982, 660358121158045, 683129090853150, 767123649880130, 792429745389654, 832641449944697, 920548379856156, 970043309011473, 1150685474820195, 1293391078681964, 1320716242316090, 1366258181706300, 1534247299760260, 1584859490779308, 1616738848352455, 1665282899889394, 1917809124700325, 1940086618022946, 1981074363474135, 2224658584652377, 2301370949640390, 2497924349834091, 2641432484632180, 3233477696704910, 3301790605790225, 3330565799778788, 3835618249400650, 3880173236045892, 3962148726948270, 4163207249723485, 4449317169304754, 4602741899280780, 4850216545057365, 4995848699668182, 5446577914148923, 5753427374100975, 6466955393409820, 6603581211580450, 6673975753957131, 7671236498801300, 7924297453896540, 8083694241762275, 8326414499446970, 8898634338609508, 9377085320444239, 9700433090114730, 9905371817370675, 9991697399336364, 10893155828297846, 11123292923261885, 11506854748201950, 12489621749170455, 13207162423160900, 13347951507914262, 16167388483524550, 16339733742446769, 16652828998893940, 18754170640888478, 19400866180229460, 19810743634741350, 20816036248617425, 21786311656595692, 22246585846523770, 23013709496403900, 24146602048396213, 24251082725286825, 24979243498340910, 26695903015828524, 27232889570744615, 28131255961332717, 32334776967049100, 32679467484893538, 33369878769785655, 37508341281776956, 39621487269482700, 41632072497234850, 44493171693047540, 46885426602221195, 48293204096792426, 48502165450573650, 49958486996681820, 54465779141489230, 55616464616309425, 56262511922665434, 59117542946073487, 62448108745852275, 65358934969787076, 66739757539571310, 72439806145188639, 81698668712233845, 83264144994469700, 93770853204442390, 96586408193584852, 97004330901147300, 108931558282978460, 111232929232618850, 112525023845330868, 118235085892146974, 120733010241981065, 124896217491704550, 133479515079142620, 136164447853723075, 140656279806663585, 144879612290377278, 157950759510318767, 163397337424467690, 166849393848928275, 177352628838220461, 187541706408884780, 198019944741939433, 222465858465237700, 234427133011105975, 236470171784293948, 241466020483962130, 249792434983409100, 272328895707446150, 281312559613327170, 289759224580754556, 295587714730367435, 315901519020637534, 326794674848935380, 333698787697856550, 354705257676440922, 362199030725943195, 396039889483878866, 408493343561169225, 468854266022211950, 473852278530956301, 482932040967924260, 544657791414892300, 562625119226654340, 591175429460734870, 594059834225818299, 603665051209905325, 631803038041275068, 667397575395713100, 703281399033317925, 709410515352881844, 724398061451886390, 789753797551593835, 792079778967757732, 816986687122338450, 886763144191102305, 937708532044423900, 947704557061912602, 990099723709697165, 1182350858921469740, 1188119668451636598, 1207330102419810650, 1406562798066635850, 1448796122903772780, 1477938573651837175, 1579507595103187670, 1633973374244676900, 1714408745436131123, 1773526288382204610, 1810995153629715975, 1895409114123825204, 1980199447419394330, 2369261392654781505, 2376239336903273196, 2414660204839621300, 2813125596133271700, 2955877147303674350, 2970299171129091495, 3159015190206375340, 3428817490872262246, 3547052576764409220, 3621990307259431950, 3948768987757969175, 3960398894838788660, 4433815720955511525, 4738522785309563010, 4950498618548485825, 5143226236308393369, 5742578397516243557, 5911754294607348700, 5940598342258182990, 6857634981744524492, 7243980614518863900, 7897537975515938350, 8572043727180655615, 8867631441911023050, 9477045570619126020, 9900997237096971650, 10286452472616786738, 11485156795032487114, 11846306963273907525, 11881196684516365980, 14059416076677699743, 14851495855645457475, 15795075951031876700, 17144087454361311230, 17227735192548730671, 17735262883822046100, 19801994474193943300, 20572904945233573476, 22970313590064974228, 23692613926547815050, 25716131181541966845, 28118832153355399486, 28712891987581217785, 29702991711290914950, 34288174908722622460, 34455470385097461342, 42178248230033099229, 42860218635903278075, 47385227853095630100, 51432262363083933690, 56237664306710798972, 57425783975162435570, 59405983422581829900, 68910940770194922684, 70297080383388498715, 84356496460066198458, 85720437271806556150, 86138675962743653355, 102864524726167867380, 114851567950324871140, 128580655907709834225, 140594160766776997430, 143564459937906088925, 168712992920132396916, 171440874543613112300, 172277351925487306710, 210891241150165496145, 257161311815419668450, 281188321533553994860, 287128919875812177850, 344554703850974613420, 351485401916942493575, 407723066223653292547, 421782482300330992290, 430693379813718266775, 514322623630839336900, 539345997126027315841, 574257839751624355700, 702970803833884987150, 815446132447306585094, 843564964600661984580, 861386759627436533550, 1054456205750827480725, 1078691994252054631682, 1223169198670959877641, 1405941607667769974300, 1618037991378081947523, 1630892264894613170188, 1722773519254873067100, 2038615331118266462735, 2108912411501654961450, 2157383988504109263364, 2446338397341919755282, 2696729985630136579205, 3236075982756163895046, 4077230662236532925470, 4217824823003309922900, 4892676794683839510564, 5393459971260273158410, 6115845993354799388205, 6472151965512327790092, 8090189956890409737615, 8154461324473065850940, 10193076655591332313675, 10786919942520546316820, 12231691986709598776410, 13483649928150682896025, 15641033916654792159389, 16180379913780819475230, 20386153311182664627350, 24463383973419197552820, 26967299856301365792050, 30579229966773996941025, 31282067833309584318778, 32360759827561638950460, 38293565795947939424711, 40450949784452048688075, 40772306622365329254700, 46923101749964376478167, 53934599712602731584100, 61158459933547993882050, 62564135666619168637556, 76587131591895878849422, 78205169583273960796945, 80901899568904097376150, 93846203499928752956334, 114880697387843818274133, 122316919867095987764100, 128268013266425493544049, 153174263183791757698844, 156410339166547921593890, 161803799137808194752300, 187692406999857505912668, 191467828979739697123555, 229761394775687636548266, 234615508749821882390835, 256536026532850987088098, 312820678333095843187780, 382935657959479394247110, 384804039799276480632147, 391025847916369803984725, 459522789551375273096532, 469231017499643764781670, 513072053065701974176196, 574403486939219091370665, 641340066332127467720245, 765871315918958788494220, 769608079598552961264294, 782051695832739607969450, 938462034999287529563340, 957339144898698485617775, 1110513408082490243316619, 1148806973878438182741330, 1173077543749109411954175, 1282680132664254935440490, 1392230112634003862140781, 1539216159197105922528588, 1564103391665479215938900, 1914678289797396971235550, 1924020198996382403160735, 2221026816164980486633238, 2297613947756876365482660, 2346155087498218823908350, 2565360265328509870880980, 2784460225268007724281562, 2872017434696095456853325, 3206700331660637338601225, 3331540224247470729949857, 3719772384726339312777421, 3829356579594793942471100, 3848040397992764806321470, 4176690337902011586422343, 4442053632329960973266476, 4692310174996437647816700, 5552567040412451216583095, 5568920450536015448563124, 5744034869392190913706650, 6413400663321274677202450, 6663080448494941459899714, 6961150563170019310703905, 7439544769452678625554842, 7696080795985529612642940, 8353380675804023172844686, 9107028941916210041627479, 9620100994981912015803675, 11105134080824902433166190, 11159317154179017938332263, 11488069738784381827413300, 12826801326642549354404900, 13326160896989882919799428, 13922301126340038621407810, 14879089538905357251109684, 16657701121237353649749285, 16706761351608046345689372, 18214057883832420083254958, 18598861923631696563887105, 19240201989963824031607350, 20883451689510057932111715, 22210268161649804866332380, 22318634308358035876664526, 23451189382295139527825293, 27321086825748630124882437, 27762835202062256082915475, 27844602252680077242815620, 33315402242474707299498570, 34805752815850096553519525, 36428115767664840166509916, 37197723847263393127774210, 38480403979927648063214700, 40374673266386112002082649, 41766903379020115864223430, 44637268616716071753329052, 45535144709581050208137395, 46902378764590279055650586, 54642173651497260249764874, 55525670404124512165830950, 55796585770895089691661315, 66630804484949414598997140, 69611505631700193107039050, 70353568146885418583475879, 74395447694526786255548420, 80749346532772224004165298, 83288505606186768248746425, 83533806758040231728446860, 91070289419162100416274790, 92994309618158482819435525, 93804757529180558111301172, 98848337997014274211995451, 104417258447550289660558575, 109284347302994520499529748, 111051340808249024331661900, 111593171541790179383322630, 117255946911475697639126465, 121124019799158336006247947, 136605434128743150624412185, 139223011263400386214078100, 140707136293770837166951758, 161498693065544448008330596, 166577011212373536497492850, 182140578838324200832549580, 185988619236316965638871050, 197696675994028548423990902, 201873366331930560010413245, 208834516895100579321117150, 223186343083580358766645260, 227675723547905251040686975, 234511893822951395278252930, 242248039598316672012495894, 264103839315570091207196891, 273210868257486301248824370, 278982928854475448458306575, 281414272587541674333903516, 296545013991042822635986353, 333154022424747072994985700, 351767840734427092917379395, 371977238472633931277742100, 395393351988057096847981804, 403746732663861120020826490, 417669033790201158642234300, 455351447095810502081373950, 469023787645902790556505860, 484496079196633344024991788, 494241689985071371059977255, 528207678631140182414393782, 546421736514972602497648740, 557965857708950896916613150, 586279734557378488195632325, 593090027982085645271972706, 605620098995791680031239735, 680084492086559046306933497, 683027170643715753122060925, 703535681468854185834758790, 792311517946710273621590673, 807493465327722240041652980, 910702894191621004162747900, 988483379970142742119954510, 1009366831659652800052066225, 1056415357262280364828787564, 1115931715417901793833226300, 1172559469114756976391264650, 1186180055964171290543945412, 1211240197991583360062479470, 1320519196577850456035984455, 1360168984173118092613866994, 1366054341287431506244121850, 1407071362937708371669517580, 1482725069955214113179931765, 1584623035893420547243181346, 1665034446142954906475595803, 1758839203672135464586896975, 1976966759940285484239909020, 2018733663319305600104132450, 2040253476259677138920800491, 2345118938229513952782529300, 2422480395983166720124958940, 2471208449925356855299886275, 2641038393155700912071968910, 2720337968346236185227733988, 2732108682574863012488243700, 2866601801913413952147868079, 2965450139910428226359863530, 3028100494978958400156198675, 3169246071786841094486362692, 3330068892285909812951191606, 3400422460432795231534667485, 3517678407344270929173793950, 3961557589733551368107953365, 4037467326638611200208264900, 4080506952519354277841600982, 4942416899850713710599772550, 4995103338428864719426787409, 5282076786311401824143937820, 5733203603826827904295736158, 5930900279820856452719727060, 6056200989957916800312397350, 6602595982889252280179922275, 6660137784571819625902383212, 6800844920865590463069334970, 7035356814688541858347587900, 7413625349776070565899658825, 7923115179467102736215906730, 8161013905038708555683201964, 8325172230714774532377979015, 8599805405740241856443604237, 9884833799701427421199545100, 9990206676857729438853574818, 10201267381298385694604002455, 11466407207653655808591472316, 12112401979915833600624794700, 13205191965778504560359844550, 13601689841731180926138669940, 14333009009567069760739340395, 14827250699552141131799317650, 15846230358934205472431813460, 16650344461429549064755958030, 17002112302163976157673337425, 17199610811480483712887208474, 19807787948667756840539766825, 19980413353715458877707149636, 20402534762596771389208004910, 24975516692144323597133937045, 26410383931557009120719689100, 28666018019134139521478680790, 29654501399104282263598635300, 33300688922859098129511916060, 34004224604327952315346674850, 34399221622960967425774416948, 39615575897335513681079533650, 40805069525193542778416009820, 41625861153573872661889895075, 42999027028701209282218021185, 48285998938145692287792278287, 49951033384288647194267874090, 51006336906491928473020012275, 57332036038268279042957361580, 68008449208655904630693349700, 71665045047835348803696701975, 79231151794671027362159067300, 83251722307147745323779790150, 85998054057402418564436042370, 96571997876291384575584556574, 99902066768577294388535748180, 102012673812983856946040024550, 124877583460721617985669685225, 143330090095670697607393403950, 144857996814437076863376834861, 166503444614295490647559580300, 171996108114804837128872084740, 193143995752582769151169113148, 204025347625967713892080049100, 214995135143506046411090105925, 241429994690728461438961391435, 249755166921443235971339370450, 286660180191341395214786807900, 289715993628874153726753669722, 429990270287012092822180211850, 482859989381456922877922782870, 499510333842886471942678740900, 579431987257748307453507339444, 724289984072185384316884174305, 859980540574024185644360423700, 901821232149013903713277315093, 965719978762913845755845565740, 1207149973453642307194806957175, 1448579968144370768633768348610, 1803642464298027807426554630186, 2414299946907284614389613914350, 2705463696447041711139831945279, 2897159936288741537267536697220, 3607284928596055614853109260372, 3621449920360926921584420871525, 4509106160745069518566386575465, 4828599893814569228779227828700, 5410927392894083422279663890558, 7242899840721853843168841743050, 9018212321490139037132773150930, 10821854785788166844559327781116, 13527318482235208555699159726395, 14485799681443707686337683486100, 15190578275949823514567417016629, 18036424642980278074265546301860, 22545530803725347592831932877325, 26152815732321403207685042137697, 27054636964470417111398319452790, 30381156551899647029134834033258, 45091061607450695185663865754650, 45571734827849470543702251049887, 52305631464642806415370084275394, 54109273928940834222796638905580, 60762313103799294058269668066516, 64029307482579987163642689371603, 67636592411176042778495798631975, 75952891379749117572837085083145, 78458447196964209623055126413091, 90182123214901390371327731509300, 91143469655698941087404502099774, 104611262929285612830740168550788, 128058614965159974327285378743206, 130764078661607016038425210688485, 135273184822352085556991597263950, 151905782759498235145674170166290, 156916894393928419246110252826182, 164879613907897228301234373536801, 182286939311397882174809004199548, 192087922447739961490928068114809, 227858674139247352718511255249435, 256117229930319948654570757486412, 261528157323214032076850421376970, 270546369644704171113983194527900, 303811565518996470291348340332580, 313833788787856838492220505652364, 320146537412899935818213446858015, 329759227815794456602468747073602, 379764456898745587864185425415725, 384175844895479922981856136229618, 392292235984821048115275632065455, 440526770002544881922455093482241, 455717348278494705437022510498870, 494638841723691684903703120610403, 523056314646428064153700842753940, 640293074825799871636426893716030, 653820393308035080192126053442425, 659518455631588913204937494147204, 759528913797491175728370850831450, 768351689790959845963712272459236, 784584471969642096230551264130910, 824398069539486141506171867684005, 881053540005089763844910186964482, 911434696556989410874045020997740, 960439612238699807454640340574045, 989277683447383369807406241220806, 1078531057592437469534286608180659, 1139293370696236763592556276247175, 1280586149651599743272853787432060, 1307640786616070160384252106884850, 1321580310007634645767365280446723, 1519057827594982351456741701662900, 1569168943939284192461102528261820, 1600732687064499679091067234290075, 1648796139078972283012343735368010, 1762107080010179527689820373928964, 1856849916994819627745637991776487, 1920879224477399614909280681148090, 1961461179924105240576378160327275, 1978555366894766739614812482441612, 2157062115184874939068573216361318, 2202633850012724409612275467411205, 2278586741392473527185112552494350, 2473194208618458424518515603052015, 2615281573232140320768504213769700, 2643160620015269291534730560893446, 3201465374128999358182134468580150, 3235593172777312408602859824541977, 3297592278157944566024687470736020, 3713699833989639255491275983552974, 3841758448954799229818561362296180, 3922922359848210481152756320654550, 4121990347697430707530859338420025, 4314124230369749878137146432722636, 4405267700025448819224550934822410, 4557173482784947054370225104988700, 4781508803329019620735796832567229, 4802198061193499037273201702870225, 4946388417236916849037031206104030, 5286321240030538583069461121786892, 5392655287962187347671433040903295, 5570549750984458883236913975329461, 6402930748257998716364268937160300, 6471186345554624817205719649083954, 6607901550038173228836826402233615, 7427399667979278510982551967105948, 7845844719696420962305512641309100, 8243980695394861415061718676840050, 8810535400050897638449101869644820, 9284249584974098138728189958882435, 9563017606658039241471593665134458, 9604396122386998074546403405740450, 9892776834473833698074062412208060, 10785310575924374695342866081806590, 11013169250063622048061377337056025, 11141099501968917766473827950658922, 11706452587460703209387640521112871, 12365971043092292122592578015260075, 12942372691109249634411439298167908, 13215803100076346457673652804467230, 14344526409987058862207390497701687, 16177965863886562043014299122709885, 16487961390789722830123437353680100, 18568499169948196277456379917764870, 19126035213316078482943187330268916, 19208792244773996149092806811480900, 21570621151848749390685732163613180, 22026338500127244096122754674112050, 22282199003937835532947655901317844, 23412905174921406418775281042225742, 23907544016645098103678984162836145, 24731942086184584245185156030520150, 26431606200152692915347305608934460, 26963276439810936738357165204516475, 27852748754922294416184569876647305, 28689052819974117724414780995403374, 31277400670180686616494311637239111, 32355931727773124086028598245419770, 33039507750190866144184132011168075, 35119357762382109628162921563338613, 37136998339896392554912759835529740, 44052677000254488192245509348224100, 46421247924870490693640949794412175, 46825810349842812837550562084451484, 47815088033290196207357968325672290, 49463884172369168490370312061040300, 53926552879621873476714330409032950, 55705497509844588832369139753294610, 57378105639948235448829561990806748, 58532262937303516046938202605564355, 62554801340361373232988623274478222, 64711863455546248172057196490839540, 66079015500381732288368264022336150, 70238715524764219256325843126677226, 71722632049935294311036952488508435, 80889829319432810215071495613549425, 92842495849740981387281899588824350, 93832202010542059849482934911717333, 95630176066580392414715936651344580, 107853105759243746953428660818065900, 111410995019689177664738279506589220, 117064525874607032093876405211128710, 119537720083225490518394920814180725, 125109602680722746465977246548956444, 132158031000763464576736528044672300, 139263743774611472080922849383236525, 140477431049528438512651686253354452, 143445264099870588622073904977016870, 156387003350903433082471558186195555, 161779658638865620430142991227098850, 175596788811910548140814607816693065, 185684991699481962774563799177648700, 187664404021084119698965869823434666, 234129051749214064187752810422257420, 239075440166450981036789841628361450, 278527487549222944161845698766473050, 286890528199741177244147809954033740, 292661314686517580234691013027821775, 312774006701806866164943116372391110, 323559317277731240860285982454197700, 339487125036360393072241575112273259, 351193577623821096281629215633386130, 358613160249676471555184762442542175, 375328808042168239397931739646869332, 469161010052710299247414674558586665, 478150880332901962073579683256722900, 557054975098445888323691397532946100, 585322629373035160469382026055643550, 625548013403613732329886232744782220, 678974250072720786144483150224546518, 702387155247642192563258431266772260, 717226320499352943110369524885084350, 781935016754517165412357790930977775, 877983944059552740704073039083465325, 938322020105420598494829349117173330, 1018461375109081179216724725336819777, 1170645258746070320938764052111287100, 1357948500145441572288966300449093036, 1434452640998705886220739049770168700, 1563870033509034330824715581861955550, 1697435625181801965361207875561366295, 1755967888119105481408146078166930650, 1876644040210841196989658698234346660, 2036922750218162358433449450673639554, 2345805050263551496237073372792933325, 3127740067018068661649431163723911100, 3394871250363603930722415751122732590, 3511935776238210962816292156333861300, 4073845500436324716866898901347279108, 4691610100527102992474146745585866650, 5092306875545405896083623626684098885, 6789742500727207861444831502245465180, 8487178125909009826806039377806831475, 9383220201054205984948293491171733300, 10184613751090811792167247253368197770, 16974356251818019653612078755613662950, 20369227502181623584334494506736395540, 25461534377727029480418118133420494425, 33948712503636039307224157511227325900, 50923068755454058960836236266840988850, 101846137510908117921672472533681977700, 106801264547682153323809469161583458153, 213602529095364306647618938323166916306, 320403793643046459971428407484750374459, 427205058190728613295237876646333832612, 534006322738410766619047345807917290765, 640807587286092919942856814969500748918, 1068012645476821533238094691615834581530, 1281615174572185839885713629939001497836, 1602018968215232299857142037423751872295, 2136025290953643066476189383231669163060, 2670031613692053833095236729039586453825, 3097236671882782446390474605685920286437, 3204037936430464599714284074847503744590, 5340063227384107666190473458079172907650, 6194473343765564892780949211371840572874, 6408075872860929199428568149695007489180, 7582889782885432885990472310472425528863, 8010094841076161499285710187118759361475, 9291710015648347339171423817057760859311, 10680126454768215332380946916158345815300, 12388946687531129785561898422743681145748, 15165779565770865771980944620944851057726, 15486183359413912231952373028429601432185, 16020189682152322998571420374237518722950, 18583420031296694678342847634115521718622, 22748669348656298657971416931417276586589, 30331559131541731543961889241889702115452, 30972366718827824463904746056859202864370, 32040379364304645997142840748475037445900, 37166840062593389356685695268231043437244, 37914448914427164429952361552362127644315, 45497338697312597315942833862834553173178, 46458550078241736695857119085288804296555, 61944733437655648927809492113718405728740, 75828897828854328859904723104724255288630, 77430916797069561159761865142148007160925, 90994677394625194631885667725669106346356, 92917100156483473391714238170577608593110, 113743346743281493289857084657086382932945, 151657795657708657719809446209448510577260, 154861833594139122319523730284296014321850, 185834200312966946783428476341155217186220, 189572244572135822149761807761810638221575, 219903803703677553693723697003700340337027, 227486693486562986579714169314172765865890, 232292750391208683479285595426444021482775, 309723667188278244639047460568592028643700, 379144489144271644299523615523621276443150, 439807607407355107387447394007400680674054, 454973386973125973159428338628345531731780, 464585500782417366958571190852888042965550, 568716733716407466449285423285431914664725, 659711411111032661081171091011101021011081, 758288978288543288599047231047242552886300, 879615214814710214774894788014801361348108, 929171001564834733917142381705776085931100, 1099519018518387768468618485018501701685135, 1137433467432814932898570846570863829329450, 1319422822222065322162342182022202042022162, 2199038037036775536937236970037003403370270, 2274866934865629865797141693141727658658900, 2638845644444130644324684364044404084044324, 3298557055555163305405855455055505105055405, 4398076074073551073874473940074006806740540, 5497595092591938842343092425092508508425675, 6597114111110326610811710910111010210110810, 10995190185183877684686184850185017016851350, 13194228222220653221623421820222020420221620, 16492785277775816527029277275277525525277025, 21990380370367755369372369700370034033702700, 32985570555551633054058554550555051050554050, 65971141111103266108117109101110102101108100]