Introduction to Number Theory in Sage

This talk is on number theory basics, what you might find in an undergraduate level course or a first course on algebraic number theory. 

First up, factoring.  

Two ways to factor a number:

{{{id=12| for p in N.factor(): print p /// (2, 4) (113, 1) (254197, 1) (5668801, 1) (397019893, 1) (40962765623749, 1) (236014346439383903, 1) }}}

For the algorithm, you can choose from Pari or KASH.  You can also choose if you want the primality of each factor proven.

{{{id=4| N.factor( /// }}}

A few other useful function along the lines of factor are:

{{{id=7| N.divisors() /// [1, 2, 4, 8, 16, 113, 226, 452, 904, 1808, 254197, 508394, 1016788, 2033576, 4067152, 5668801, 11337602, 22675204, 28724261, 45350408, 57448522, 90700816, 114897044, 229794088, 397019893, 459588176, 640574513, 794039786, 1281149026, 1588079572, 2562298052, 3176159144, 5124596104, 6352318288, 10249192208, 44863247909, 89726495818, 179452991636, 358905983272, 717811966544, 1440992207797, 2881984415594, 5763968831188, 11527937662376, 23055875324752, 40962765623749, 81925531247498, 100921265740921, 162832119481061, 163851062494996, 201842531481842, 325664238962122, 327702124989992, 403685062963684, 651328477924244, 655404249979984, 807370125927368, 1302656955848488, 1614740251854736, 2250626766458293, 2605313911696976, 4501253532916586, 4628792515483637, 9002507065833172, 9257585030967274, 11404103028724073, 18005014131666344, 18515170061934548, 22808206057448146, 36010028263332688, 37030340123869096, 45616412114896292, 74060680247738192, 91232824229792584, 182465648459585168, 236014346439383903, 254320824609787109, 472028692878767806, 508641649219574218, 944057385757535612, 1017283298439148436, 1888114771515071224, 2034566596878296872, 3776229543030142448, 4069133193756593744, 10412612133260124553, 20825224266520249106, 26669621147650381039, 41650448533040498212, 53339242295300762078, 83300897066080996424, 106678484590601524156, 166601794132161992848, 213356969181203048312, 232209766730673954949, 426713938362406096624, 464419533461347909898, 572102572153398705721, 928839066922695819796, 1144205144306797411442, 1176625171058394074489, 1857678133845391639592, 2288410288613594822884, 2353250342116788148978, 3715356267690783279184, 4576820577227189645768, 4706500684233576297956, 9153641154454379291536, 9413001368467152595912, 16263032824924906238857, 18826002736934305191824, 26239703640566156909237, 32526065649849812477714, 52479407281132313818474, 59994138821852069990891, 64647590653334053746473, 65052131299699624955428, 104958814562264627636948, 119988277643704139981782, 129295181306668107492946, 130104262599399249910856, 209917629124529255273896, 239976555287408279963564, 258590362613336214985892, 260208525198798499821712, 419835258249058510547792, 479953110574816559927128, 517180725226672429971784, 959906221149633119854256, 1034361450453344859943568, 1337918363109925908710303, 1837722709216514404990841, 2675836726219851817420606, 3675445418433028809981682, 5351673452439703634841212, 6779337686869283908970683, 7350890836866057619963364, 10703346904879407269682424, 13558675373738567817941366, 14701781673732115239926728, 21406693809758814539364848, 27117350747477135635882732, 29403563347464230479853456, 54234701494954271271765464, 59027026073637127326170953, 93702390569829128154982379, 108469402989908542543530928, 118054052147274254652341906, 151184775031421627684264239, 187404781139658256309964758, 236108104294548509304683812, 302369550062843255368528478, 374809562279316512619929516, 472216208589097018609367624, 604739100125686510737056956, 749619124558633025239859032, 944432417178194037218735248, 1209478200251373021474113912, 1499238249117266050479718064, 2418956400502746042948227824, 4134014154997436391198732829, 6670053946320995387857317689, 8268028309994872782397465658, 10588370134390691481513008827, 13340107892641990775714635378, 16536056619989745564794931316, 21176740268781382963026017654, 26680215785283981551429270756, 33072113239979491129589862632, 42353480537562765926052035308, 53360431570567963102858541512, 66144226479958982259179725264, 84706961075125531852104070616, 92191896740967133411738800457, 106720863141135926205717083024, 169413922150251063704208141232, 184383793481934266823477600914, 340094834147453836216432891691, 368767586963868533646955201828, 467143599514710312205456809677, 680189668294907672432865783382, 737535173927737067293910403656, 934287199029420624410913619354, 1360379336589815344865731566764, 1475070347855474134587820807312, 1868574398058841248821827238708, 2720758673179630689731463133528, 3737148796117682497643654477416, 5441517346359261379462926267056, 7474297592235364995287308954832, 9667800357038782140591065112347, 10417684331729286075526484451641, 19335600714077564281182130224694, 20835368663458572151052968903282, 23818866575678854889612055794663, 38430716258662283492456916761083, 38671201428155128562364260449388, 41670737326917144302105937806564, 47637733151357709779224111589326, 76861432517324566984913833522166, 77342402856310257124728520898776, 83341474653834288604211875613128, 95275466302715419558448223178652, 153722865034649133969827667044332, 154684805712620514249457041797552, 166682949307668577208423751226256, 190550932605430839116896446357304, 307445730069298267939655334088664, 381101865210861678233792892714608, 531180205364637931514092265057579, 614891460138596535879310668177328, 1062360410729275863028184530115158, 1092461440345382381886790357695211, 2124720821458551726056369060230316, 2184922880690764763773580715390422, 2691531923051710602526162304796919, 4249441642917103452112738120460632, 4369845761381529527547161430780844, 5383063846103421205052324609593838, 8498883285834206904225476240921264, 8739691522763059055094322861561688, 10766127692206842410104649219187676, 17479383045526118110188645723123376, 21532255384413684820209298438375352, 23434903575863622411863767859768029, 43064510768827369640418596876750704, 46869807151727244823727535719536058, 60023363206204086261092425951506427, 93739614303454489647455071439072116, 120046726412408172522184851903012854, 187479228606908979294910142878144232, 240093452824816345044369703806025708, 374958457213817958589820285756288464, 480186905649632690088739407612051416, 960373811299265380177478815224102832, 2457525847358187303791826978363270359, 2648144104072589332540605768153787277, 4915051694716374607583653956726540718, 5296288208145178665081211536307574554, 9830103389432749215167307913453081436, 10592576416290357330162423072615149108, 19660206778865498430334615826906162872, 21185152832580714660324846145230298216, 39320413557730996860669231653812325744, 42370305665161429320649692290460596432, 54804836331781805237364770499937785947, 109609672663563610474729540999875571894, 135024414663074868277087711500841409063, 219219345327127220949459081999751143788, 270048829326149736554175423001682818126, 277700420751475165328476448555049550567, 438438690654254441898918163999502287576, 540097658652299473108350846003365636252, 555400841502950330656952897110099101134, 876877381308508883797836327999004575152, 1080195317304598946216701692006731272504, 1110801683005900661313905794220198202268, 2160390634609197892433403384013462545008, 2221603366011801322627811588440396404536, 3838309063296899082307775627660038918871, 4443206732023602645255623176880792809072, 6192946505491343991822219066492969812011, 7676618126593798164615551255320077837742, 12385893010982687983644438132985939624022, 15257758856927460115310911399595079224119, 15353236253187596329231102510640155675484, 24771786021965375967288876265971879248044, 30515517713854920230621822799190158448238, 30706472506375192658462205021280311350968, 49543572043930751934577752531943758496088, 61031035427709840461243645598380316896476, 61412945012750385316924410042560622701936, 99087144087861503869155505063887516992176, 122062070855419680922487291196760633792952, 244124141710839361844974582393521267585904, 433728924152549596300778645925584397832423, 867457848305099192601557291851168795664846, 1734915696610198385203114583702337591329692, 3469831393220396770406229167404675182659384, 6939662786440793540812458334809350365318768, 13931224981029939545922412566772685374369559, 27862449962059879091844825133545370748739118, 55724899924119758183689650267090741497478236, 111449799848239516367379300534181482994956472, 222899599696479032734758601068362965989912944, 975686648962881856025389641224298913060251587, 1574228422856383168689232620045313447303760167, 1951373297925763712050779282448597826120503174, 3148456845712766337378465240090626894607520334, 3902746595851527424101558564897195652241006348, 6296913691425532674756930480181253789215040668, 7805493191703054848203117129794391304482012696, 12593827382851065349513860960362507578430081336, 15610986383406109696406234259588782608964025392, 21758610256326524814685400785854856283334843671, 25187654765702130699027721920725015156860162672, 43517220512653049629370801571709712566669687342, 87034441025306099258741603143419425133339374684, 110252591332805649730869029458345777175808429331, 174068882050612198517483206286838850266678749368, 220505182665611299461738058916691554351616858662, 348137764101224397034966412573677700533357498736, 441010365331222598923476117833383108703233717324, 882020730662445197846952235666766217406467434648, 1764041461324890395693904471333532434812934869296, 2458722958964897304059450288801598760016837334823, 4917445917929794608118900577603197520033674669646, 9834891835859589216237801155206395040067349339292, 19669783671719178432475602310412790080134698678584, 39339567343438356864951204620825580160269397357168, 5530973451327433628318584823561946902654867256637187, 11061946902654867256637169647123893805309734513274374, 22123893805309734513274339294247787610619469026548748, 44247787610619469026548678588495575221238938053097496, 88495575221238938053097357176991150442477876106194992, 625000000000000000000000085062500000000000000000002131, 1250000000000000000000000170125000000000000000000004262, 2500000000000000000000000340250000000000000000000008524, 5000000000000000000000000680500000000000000000000017048, 10000000000000000000000001361000000000000000000000034096] }}} {{{id=13| M = next_prime(10^7)+next_prime(10^8) /// }}} {{{id=9| N.gcd(M) /// 2 }}} {{{id=14| N.lcm(M) /// 550000130000000000000000074855017693000000000000001875280443248 }}}

And now on the primes and primality testing . . .

I've used next_prime several times, so let's create a random prime.

{{{id=15| p = random_prime(10^9,10^10); p /// 839363467 }}}

And check . . .

{{{id=16| p.is_prime() #which just calls the pari isprime function /// True }}}

We can also get at a range of primes in various ways.

{{{id=18| #as a list prime_range(10^6,10^6+100) /// [1000003, 1000033, 1000037, 1000039, 1000081, 1000099] }}} {{{id=21| #as an iterator P = primes(50,100) print P for p in P: print p, /// 53 59 61 67 71 73 79 83 89 97 }}}

Proving primality can take a while and sometimes having a "probable prime" = "pseudo prime" is enough.

{{{id=22| time p = next_probable_prime(10^400); p /// Time: CPU 0.04 s, Wall: 0.04 s 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000069 }}} {{{id=24| time is_prime(p) /// True Time: CPU 21.52 s, Wall: 21.61 s }}}

The following is known to always give the correct answer for $n < 2^{64}$, and there are no known examples of $n$ which are "pseudo-primes" (in the sense used by Sage/PARI) but not primes.  Infinitely many such numbers are expected.

{{{id=25| time is_pseudoprime(p) /// True Time: CPU 0.01 s, Wall: 0.01 s }}} {{{id=28| proof.arithmetic(False) time is_prime(p) /// True Time: CPU 0.01 s, Wall: 0.01 s }}}

For more about primes, we have the prime counting function $\pi(x)$, 

$$\pi(x) = \#\{ p < x : p \text{ is prime} \}$$

{{{id=42| proof.arithmetic(True) time prime_pi(10^10) /// 455052511 Time: CPU 0.21 s, Wall: 0.21 s }}} {{{id=44| time prime_pi(10^12) /// 37607912018 Time: CPU 10.93 s, Wall: 10.99 s }}}

In 1798 Legendre conjecture that $$\pi(x) \cong \frac{x}{\log x - 1.08366}$$

 

We can plot $\pi(x)$ vs $\frac{x}{\log x - 1.08366}$

{{{id=45| l(x) = x/(log(x) - 1.08366) Q = plot(l, 0, 10^11, rgbcolor=(1, 0, 0)) points = [(n/20 * 10^11, prime_pi(n/20 * 10^11)) for n in srange(20)] pi_plot = line(points, xmin=0, ymin=0); pi_plot (pi_plot + Q).show() /// }}}

Or we could look at $\pi$ vs. Gauss's $Li$ function:

{{{id=49| @interact def f(x=(3, 10, .., 10^4)): show(plot(prime_pi, 2, x) + plot(Li, 2, x, color='red'), figsize=[8,2]) /// }}}

While we're in the area, let's look at the Riemann Zeta function.

$$\zeta(s) = \sum_{n = 1}^{\infty} \frac{1}{n^s}$$

{{{id=51| zeta(2) /// 1/6*pi^2 }}} {{{id=53| zeta(3) #transcendental /// zeta(3) }}} {{{id=52| CC(zeta(3)) #an approximation as a complex number /// 1.20205690315959 }}} {{{id=56| CC(zeta(1+I)) /// 0.582158059752004 - 0.926848564330807*I }}} {{{id=55| complex_plot(zeta, (-2, 2), (-2, 2), figsize=5) /// }}}

Moving on in number theory, continued fractions:

{{{id=29| c = continued_fraction(pi,nterms = 25); c /// [3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1] }}} {{{id=32| type(c) /// }}} {{{id=33| parent(c) /// Field of all continued fractions }}} {{{id=34| c.value() /// 8958937768937/2851718461558 }}} {{{id=35| RR(c.value()) == RR(pi) /// True }}} {{{id=36| c.convergents() /// [3, 22/7, 333/106, 355/113, 103993/33102, 104348/33215, 208341/66317, 312689/99532, 833719/265381, 1146408/364913, 4272943/1360120, 5419351/1725033, 80143857/25510582, 165707065/52746197, 245850922/78256779, 411557987/131002976, 1068966896/340262731, 2549491779/811528438, 6167950454/1963319607, 14885392687/4738167652, 21053343141/6701487259, 1783366216531/567663097408, 3587785776203/1142027682075, 5371151992734/1709690779483, 8958937768937/2851718461558] }}} {{{id=37| [RR(x) for x in c.convergents()] /// [3.00000000000000, 3.14285714285714, 3.14150943396226, 3.14159292035398, 3.14159265301190, 3.14159265392142, 3.14159265346744, 3.14159265361894, 3.14159265358108, 3.14159265359140, 3.14159265358939, 3.14159265358982, 3.14159265358979, 3.14159265358979, 3.14159265358979, 3.14159265358979, 3.14159265358979, 3.14159265358979, 3.14159265358979, 3.14159265358979, 3.14159265358979, 3.14159265358979, 3.14159265358979, 3.14159265358979, 3.14159265358979] }}} {{{id=40| [c.pn(i) for i in range(10)] #numerators of the i'th partial convergent /// [3, 22, 333, 355, 103993, 104348, 208341, 312689, 833719, 1146408] }}} {{{id=41| [c.qn(i) for i in range(10)] #denominators of the i'th partial convergent /// [1, 7, 106, 113, 33102, 33215, 66317, 99532, 265381, 364913] }}}

Due to David Harvey, we have very fast Bernoulli numbers and Bernoulli numbers mod $p$.

{{{id=31| time bernoulli(50000) /// WARNING: Output truncated! full_output.txt -15892622743101808685771841018411228037542708641239392421117954054169436312730031935785662506701820683536195951897362336245063118247409020088041050393772357478738284984540275100184268221990200845816148160796715700357364937899661731632563375280026423189254978465645236839479548234783122369345682688011711834675856001671142118700536792189082488363281673985098146183557368338203719803017535644519435077526085278202054969881515996371879498445398818168862093808572128503434344810384978869648257692461969692601646871033460538053938039781400201178860918781860738274680075550777013719140919283674700714995207527681734704490975897737425491202005517075568265877205847619208136651630759577970740901386914573968752005647464038431786906919950611481061953926028900563417187570829615157016895434615876665424464383558222487992126938449872326285998149836420620449791711321801175523029893314054896936126489958436131158874794631926155369487937805160020797420679162460335083642790825496334623996178530551064409930844756254921038421168749926278532295908316656681409346799093784030285515263192273804318281859019714752500931637015744598945119197470143048331664430811119525277187895774358568287769713201311918222158620482765226387333081614620648248778354371831931407385184693397511188252420341390932126986924257504321875186638359023911251016838975453668744035644052865121069167362477319166606598791133606404096206210498139255260248741513099621179596004863642611350600545181231762249056817100330944222865353195912370618624870391290172784158106139942962936365295047341309212631297635137756494612314711981726806144947884409295647392703009718906528016546002133070979187186488253688413506874074254023929579265126535468204201485596812369339895720732726932431065732595340957524870954191987117221157460303872245215758803824321629974124664619156859096593458129622868342825203851607125725207963208539199064546947018766427115552259067449667947769910870629111584381486787514067708673527663739189245839034821413310375105076730011916692979327241136765303134281496227220263744711238105106191574261716206368855314327060174485737087234821762958003844660458063561253663244667354076093409735669533880370194932254458658891583838469381506010800565033149445552927975080921594773043245528680279854609322631102979006309604433484563324297884830079937484506729799110342934047502114414310063105867669047908380807018807235771663668673230764745043032444405720025435257207564391978098757300573056340424373486002785934524928201640523149449124540301682355588219225997390559166144757837547210280942694011439769887146468320242052935043753070261208208847677966495937971607230930087744513874595417688036425048709666586989913603595853242244525442549443370587127569283918922529155720788465557930311761238195137161722714322695741964890519808642572386732520608524976059653091426325862985227625669762601359386264546991166681320662584013861873445976579229801565805420267692870154068553868909170338599554635374247509958825877447677464130202193102283430548018385325677300477949118413140320044320192694782500009673076908759008688980312803926760843659622340760242103463591270362248853514617061676064812179598012892651472763290766767233693916277463714554541125348436788552355454323222862522385350345072675129903992241128425511473107178904089813523445767584767017276152119747182993445445728610955837886669294464007159614013047302719492743612066034640477948367015673738720028172114726845593531115422813796544030063602294879824018509929606253869644600352587139445184204355237808144780684494002294039169245609033598620490179127908367683492054540365191325101150048899808093449148179725669489491137600958021544050987571663708852110083537168356999297941758212032381319324989416993348726480176982964103122444677093515363170466214432208891416859377214243606083082239901972883686871901213024483600299205544279909721876617619913202411770240279033811074345495532062554923792761455408350456523634375622443410475702095197833272689076679485486515972605670098455830969732779371791262516830631820566172236989748809367252400405802156131635188944288175364048537269886413982837391366360055863883702310193265852954243268221463143861514165800809579361703805907389684005743347678442774821119690386418405197878219747712789739534447082230308307798761918446520850877923364735006905540997875491963533436420797487324308475276965720560321123399819361349120984885523041426546268698517479432241575279948337068749711128174620280704577801494162765560911219252485822291707823537698753424563826216797416499030656456199604366049353207706474494132573781475483414020327924081452000940510168961483650062899215981007983357525898437582066617821561843287050960115213202753104158373005074624049444796654634137883406428499533534138172565879368769560988051949698568816865756559714484477992238518668077022995750496591479912396902354570916925295649273227238988842277857909644140366932332712346871132940567833217163585926327718339254808591847954700599419014917874249254711817279517652890186414885590595454448361927684206071963439441958457590111173671022651270464422122729158511207931596008978775605277740393937804678625772354999291135069571898351627229558542755864435406704598650399975538106166562264761203797667911578449861383209230267104917840587226453560396395244960275479822223981356324689656904286946582651810610106121037406567023117836232820743910551547092809854624183405245385249109330904399638979488850103863501418280064645160704380206954797834606041928557068359737452392171608578097453765273543901875451427182783454187724459277413856249329275990369608309521701170965031368248657995341770488393441865582108672715438114625702368702325468782293836555722024918660878129737580749479782933804210664222542539827131221268538430378509179719429012387508305959677098699031153266515113668141805956570262420025010412674385755822846330649777878754662424821252852469231482465533627026446131874948406157783461033423756104317423550435729104174775398246210668653510416979745633902138732639167773775575100257453972964614550895401725113926593667326854711766582781667272559991070480378743489315730613436267790268183912750812254095043774991346189840124443623932275152754099750462555658768821615560481553914046240309991747066320821523018021281435689792940770709573196801374289767078365090099938773784770662145087370249833419549362414276899160365937173723967316952361497070260896409923717187597496472398014179229047711594602167720252126262771642399308749037932348246147884605947698778077742663318352937829838014730879354979299701415106527247384610594752379423787477110499318991582864338596414293669956558885865294307890846792533448477461607899993707836406476848761293720156455611017452797081690936945612382742706687482004300897516775901615047586712599579751037926979928970187742790937365180810960112583933877188585337908473178578894248546797370520029469751725413431578129847732830032808448029195855787269027708840873966302333509788981173727214380734206572541796143619092934770088313031312832836000320963907856011792204183883098481108039942822522694869805429228445437748068830341289764393741519418617373440047534783572002410766665027605685534742141342001032666019048662746924795845584916745980968038248224102722528678990242391378809483413400481725537593026806721496875322836172001871951841325114238075497007218289702725149720730314810556030231534240101969557917880132998690732433748501736988455832832327261158480351876861861398153499620513158786790328003467243302052541307562090314735098113579292008758153862907527656720659151799941044593366042715429972329204381675895281838800920753868368634239165106415971167650026406671557813643756252086090171791053385091602329435849634049704783673646457817505578857331495066737835896423894638623620374491902127498448107872078208900419339577127979329080404657677082411393190341427737116737164049708488264102042173647560461167310432150942057069813911106132147025589415638004312431063655194705092615011688389702019560139300619976208680056834580284413109233451166603603826555635320162353466529385932891637153380380133194904821281194940040555215445386845502322997426991585194305796826628623021266818998227830393537844125582164025159321679576167575055089828557588848574881322238599142265942124496452591619040300633720208485271313340976777539786601180296022731026899947750277880962444723989617332732938352358617129260209618547596755217673972338678614069168689258560968410248765933211078070974997510711094839609637960536953654770810952389725802211164856302775144801589588339163396755836141632336257495013204329540486250863782927318192656654126655323663842817375088371367352915427553669387080729133660765970950566631810754747097769740951890282800809274334282764825461330699460311857807731376872701728781155537003757393728916231456533345266688514968253427547455854467525238318801450404391588989466058174237751409816037356279074302615121214194124985488636878648394498743117535965155799536034240427958957735641144967265775834874255698465954085751004819599377689379033662210965524129329505052158854896284726436646567876525680188218330654103786512141701534457289187179060620237878815654132324808337392362834415192453082068910212985151376750183899559827895473462684446842678908557155541010481247901366248752106559736964940958314749664670309050865682283608838068720168405117570807862870172933684389098815067706475417102408144589354102410732637424196210099402159917337697601288475386245070044014286511428121654317617162011221181946889988477201232730989701835014667521556607865198921387347840211064270616306952290071046112818029688267516180335228767575780278484257115418055142400219479964701903472416771436371232080713927800447263539993279746924231675077005944866671193200712556159506157630302314229904883920269847013128751182593274542649917750706596498448652650582098128363270333313494721266200970456052002902044454650893922229726165855106479678410398560975835871569327680774338341111338880293610670662048120173288605677171010871445289595977500694106399703542086761247613869855434386020695924003339299631025366903597493708555411584004953345920613240556105728261059258440819420368346424108064309275805703151330068083643631670420075286770514458607775054067676537619776929506111775701704775391534104754492011276477623020237987289782650921499803130544780310942731120397767004152259324528804745429963123751015570554449985704889724550808625870675526067184656612923501845513887427632785109882698059448657263420593337833936006456537736362086054612568567482675993595539203410649552350976947913112313289887665235550423457621330410573888689159226661097562025217422835526587067542038879679999262507923057448517218833217784038949257091515991176068672524491161614335859134942849534946818131827348120249382598805897199659491483833382762443179601088891032242265005024282843396072202208937738478769493690514615121924803551636270993444237279255687398223777411752606889049162524612845087417585097211797490928216991259613309565448013005212208346766007992147588238271996469010806530996655076611181773605147991066836134627727581878346914703242849921420657372182159734312028697417062886260981341796655459276971778104728063125742853061213318553544660504096482117768019878197772343069063148020885896708045560287636335727500454209273804073515669901278554061861060021193598658470168229627506637587781023409698026352736739935819045334166704508738778955922071331251782692943839103792647634950944772190474833871294948462027959475867773374757186255355258882277059310448312582213795104149189507132073695004668475421924370366881765547841960275994319626620260280455073499848221770596164272037168406348353618815069716360773104707911625629708106800573332503359934084526851206924850925358537156617429884838908771304880897894245366685080365408643330898313600569036263831932535412452263644881390839810901950662154370073284149333239496778713890450353011556496308731489717642116771568755226056097766944814465879626719289597324079710724250249033520958160931220829621435140778447638153421761522542817778222152110957308335745365758763235268673298261601336546961178360862069085264510296591303800233461481615993652534515173233410542207682396707147462332096548490707600510205895173292238053897817422668129472882074251212131332810641260857941395341679396414287075656066467732152089244445808165885984172189562834389656744174225747332958889209878594206666257575259495920569815412015179630156976553865085941855918575309697597332077391475058305484687463102982290440329781504866946452585040890634949739122732908002719822736620935020110948368178875771016640125442050494234477965526890511405599146342616185030967939724539469561586561750589482740306829378085083254248165072990080396163375808565669211078745891359059171530817892518406496533541887247636460192489045289911580452422595818877145766289255300691469506765154133893945423898337969026546775782066483457530001538878398630312760177686893434752822931208491752004476883835219833272976668744040708540307862134527918954886618438911080628306380083827958434013550312107051978870439335508177189734489440167375890827400826178971005630968474727303502558467129789136743694128421701311863358007864243942020963051820810888327086747242205894387251790651298452716795018613778944256623763447091731236831381039924933871564249569023684466683726892882866224339657068296837721053115235265450942196984253926816743544848785737239557261416422741289072392410903888645166107419783406405257312590248409889813634477271406391217235611224658392735465377298137802341053682090663019237650405893942440338821799287532842214766395562488781457658504021861354598953285245310946173874299855392455401320303248086891743536502019796203971555084015626419129500780835627164218353765651451725563020845619792053812826351627495403601361702512608718228879633274455013673444120781678495996193026318596229351334458881654191612381271617123233636527029236199522746504663504503097805213092673318018437368456770738700235602682221325088804238247841990386855455406866803570888906399238342880324989700106297367745769800426902168697789535759509488099708967370520310097223684431473338103419520338956473378969608326589958427789955267976100273512666915579579080039075028372718786832321291876773349637387641200139919178023921429995270582229516856255207619359498073476730698451101584946913243157512058377248055829333548947356185803907494736886266661717993997792917539261598988390833467677346675542732475657836025975965496938238508581074630747013891523671320989250052316391585230702966409294538001381215748943694096627510444082305208608682747566715273199971735117579737249338976360926792724383793578421203524214167728699058074126019877888075141438321191678156376491524148100251234393700067404485489757252436983628308983662495680073410589081278164727960324158974851189155145337069589434001381834274787732071247746130074216375977510668918163024396826328211642006510198955605498171826779202385437204636011828152346406810538049990401782390195213504251885124761593746670586588130901091604433035069567551942503216221882655902987942665621866364055326171777677447501022455132052782289468618123721881115652964953493221815430264068461492945031976008846560563012654553619365243094135782336319116955928944503823719980607634421387645095843364412757734108399166461173507192620160093264407314619543668330975784723479787015296262785315713655818940130712167395396527277728190693075222220039418656528935495876867050152460208405425767547904678298966856871988266779359369989701530515400861785508122362342943144861217008815491187454012304634764791742093295431096974079118850136689504776053644963083525349334144939948867456145895651506917627568155973808351663062629055232931157510633814009860037204678276819815167779999757290161384576725772487933509238511542670716130814618236382366011474713468996872333642956821107321794944945002919187626422179757996195562017689245507774812769504715364449177915214509201907408547311197972852770509226305135308780649630995292184373129670552787843032324957192493510415806654842657036475026472898377407522241192994037356872092440769143059410440055002123317386532272 ... 6903138964049520385597372323073745956422104165901671772704690326550147989099616479135369186070586047003286812570043546466427298693020728900541379199583189496415899320856523819744806662622220062381098554813350739712418588483199838460107111245758785230543142535819341495899004995582864063557687651297263603675268368334063097861870258816685054163059753304297873930853986758101449491251691494560013644040493521768980243886540330129030493507879405017454582502570970807947876588014351215198078281308876383767811235597020208091625950475719556539238359059359345548278536180996804283078884650418949969771987134204464704892850689430411390052099777681221495742930508084227444493857275066870528854311407613511489402790929008416119629431995046222837520094113624118424910456903927744300102882349107962933564024792270306980483510839304105696798472715326907560454353636660981859759289185513009689926470048963001375918768320227964977832536220561764286990571896270651416857360073609028341678339928529885760717372389042770938666943079669430665887674300153708210398076823964107951457115625534045402378934948276992828705244785419193671816640314483284083757172393326697998917953847879943929300922749086623432828902885872488795276030901825566058946855280299293008835827377764860556924923823864808747336035738064226436938380763357510235939461127638380284596218884551498456962514742253315469700986536009199391481985319161854721762173559184989896829677413655121801238170461300083011007809409308910546378562530233989790928282323140198722160128085661271805620652585865904640301697537615001559391121274365861233575533634712958313504912169853796359177598883947030955380552943842479458915447446265593028777571806164702465698505693395951974849990876978936234953520392445459381823109578599675554367597751363128037935486093007924972926319320049624988376456841002222665500216556508619321344024408745766288356928078567101798654945307153858750196002488216624293196478399083012445166762491871774448751219462512208598853671025195719699283566475462701057774799690504504563416749726152941242411952298265605179804239522189986359955380717931801417345471256849753068738288218744942162042585882190551812437513258049223545214164951407810190459972725035477130632021866069393418785019647237086853996972054093447030615618917953882329840957401554175526165366987836366726838624826247256521570318634304441330477460165302955353315593055209902132478434059983433457386468856895393067117467856187155757937113492541768414170437064387013563571778967663924027528166840533317503787057869301238748722468387911042832056958794236877707728239037456299189504834148047420753126549278277344809780832092378667612805528005081158940136587258256342078103299317923130334372507671556651302575226906891397861483716451885593148616653490759498742829345061337130091617646595454008741789229439137592825339564034854815048693971776202630390093065499014796716564935679034182774608094852096269897709513181460379069206769591024586713840708917407345111342447524289245283343996168241783372331571427137591994088632104625342594073926960490658276410917380198427956641520349164734772187006666297116492022738964440628955432683606769710850191132715904559957750765079510882290148254586308067393996946367842373648653122017484880795619760428614724958652132652297085191018126863259210187691515355434597890455370046997547101858394202052773707003788800500845398244663047124201692031764185508716677628743942370094701304507934852441041120010289414666706075347740523087480765645153782821669134117983455350663391853954443651146414423631785394714724653903385035673402236358639967518584827643846027709985859391819488939324065479523688732305969510463954177466662040111084301315188329910663734744625150086985885109509505269404581276646106639383902492858032016808716251766799062415827223560179144139139255622385328426566653583940614987945065412455391160897858544767918420168669806259151992870550082482270613715993986884051393342602392592930279193552475212431989273998553470359037009796297207092655880596729125793926789207610522252614843495132841075649240233404608292104178089091602823028660652204936586784376303504564972112416276382273047169628140445598016354355550753155448068046201634566589111397210293023473598907881269992869271296325400735608577109553042723862021345684288500230020456258096540340989118228556334678339723762487958771115141471985780337487112188750671175407710187995984985083454191801180667532263893476964974588669863014461855889839801940816224675548699954554515966204263645928178705484585237759691510954531790172489547617214896855861283091013507410322130219475734456359185934879159595936913420879177946018407011326388851799772460376001584867680633033744048346598462294233096043736517340579406182262265795151084527931750658133826138659289134929052548789395891609413518460001179138572066555211571953274440954937713444722150810326197307157142793417479543702365080194232461258170187929105862280092918021654843870874651260362489046385528930452815985442146551914159997507351773183621445587089979393324436281941984765961560055257565551843211688022404764050988253810730561072650024235977895139300147589055905886853006792261387508326463996990857120838966677621745490010492032151514433938737348181526135029251650961680507508718409427124739861202618665288852384267635878500066324880559783721563765044198923229284258474598252976195027611032327959463254392864426194283193987219316416392115220375018269830984311209663327481609960866280505298977116990470377249212201966524429308632659325807085242809977099839409398989725254948122639908519223305320252330933458470805041511360049122711123721046306090311630755015350124292375240068488889519461599217114986581369411445776200022119306110975317803731181978930286128064790973668385579876529177376516892715858471166426622378746414804382153580827385359549358871460602787578281049866283445385347307979994045409857531034100450409345130194920005369283147203408821959469293142053520346936445922714060198761582883581587406395162478409734673475737796957958288960686505665802245563271456239419083580275250112998803666187806541875289950610958258016343997677914054598604598492103883734384629596035881175141416139744191676584078828140811459194524593764484687554509134622673331022362275072377586863681320636737146555901861740797844766025507992288527918938852786953059949676890720095189952382903800221594733058458046822076483142988039218110715089527660139104671638925095046055696063505020240172464136277355944515938476801632668818467430387992122694366467506703032895745991147043482021667112230676357974710044374906632019812404567153673018958165108150013731219723266092475943221470011981552710645134682491215465395158751828634269629105783077396594624386677878458773248001807779381014322169932943729576355613171373350240631078948550838171641662291186776452860809751108921419797980744640159103870243414794081009358289200763915311570314476956048608555850889580342952746612913560724229483668584181689268377876228562386984370425318256896719109090617659737124904016159282864439207777853354369989876235574660464226364697580794600118919504070140000678841152061781229217702578017054546507062335438826284010104523281979359912972388426028204166629772040324204323110381895583062139461904673872910052642396378056018446667802621035124279855515432077986972390473226287174062927760226586382370288464835374847413623962231047583863764327917379336247171703923110626323110792636320495482622165427016871003822434601134953724878438884956491471299895838350055052682284077212651511032027253475634463131764009542968569071213024715841797886897939302610413241875449883394064491770624556182772546670273744561281034922199841000073094291979022241063226883365254357012527510860409369275824175201323163119413750198416570630455165570404862913573979526363223026532547149252448296668551724228599861118501739530526355356965915170804060153033831102296954362974549383276284997044512740743514094854670363586080114175089798913696383130115201522179632340488837450025552416892194942943582824627690762880328882449406277489840917951557433833993475522684381258372397668909742785285509371312595596260191836447448251673396502508167807692662450613210619225410842056850103594661725609009310246365700685356622046130086550596817009709027948667992316490553800935099301465471103587297580060696422169481425553175145435179598245593880381287676487564534533271211480963641957724521731806316130884816490424843012980706017257542600582841832465792378042404924460256694634530401092105057828251647257656051774531170467772386873014257957036858899298455915084649888157007984757759493599825747599589822387886185170477620017767713098980718318908826643641627479240382485905785015988826784854053865730794018189299317769412716595329855599858566964474775717086982125347185916512526905641286642184917486421566056920178376686981589831164024863524530997322605785183853105211817911327568309324198760792859062802796714227687028555274618609908299599180707681764380131203926324030185647513418123060838841268073944308421157423456167194167050635670564321436289007469905755254217634082350095948093163369689683770483125842479969452571880007544318343429014400503357149510721423132425916464746516128707904645735237765352050170678556446720581917042747588875364334752760721446285422685377225034246164127714580651355194486727964580464242017118548358160268574174037539113288087147211771630309597539107333081411492925674721133595327445664989201570751020814788094965980496188617653114030790177543645111322181251496319012850049654643982838040810287778897140448693746590458808012574479072635344786471310597239735049084897231727093418854684843981438642265373433090268797990698705885433221668322581318636491035347269047680475798407127260653820590871924001549026823085620142391194532690286777015935125532488016954463229589888457073499181280929795991586669205709495352735227458480816601371446944978773702554913842471225523992372730049740109351568453461634231835872457487814004205557296327478971169020919009470572877227901507404821597003068875485741540537726922041738171782695434475711251806943555992322464940276181647831686868427837420529221886208302344373224547782124602188772630844863114570999129647746437264085622958222706628767421379043025409011616814338271666959838797234793357024569953698971578811391630858344209350899831829253386006736795046300985752545110695907237448127463113814549640788943648190111678181075949695788445906863584315998300087482141495332186142881641712476581824141249130574944250228941484006313334207158492432539324903058224713711341474678846888412835394570329639783038848810739623671689907467146484004099970902476542050774595954209318570211609132880004738847668211432935999598194728734964660571937851184755199196943751677986836365180219470889942032272738921936833502010690986158703635540255123860542956163303096157568889003754402807488055249983151413581151575586462377746946520775958715134193267487385320640764392638949542421732965364783091029246483071222311332005806654396602791209991016072129836656067339217421237887600737287648821415842503125639004054819164454935921385174325839401943823903540847721424998292753261504756337024801182267635423097803961923988752624915438793334692055267616538237836126360562402604398470579663462666170763238469455439711315954806991865624322529349230631915654542245046825747943096195126464562410362128530981154296232556031672792791705312876706597963621019977672586416051068481789969408895058344365802634644214354049968088925951993824839571766040667750636195635517435172447013914271994438209239475788816525651617613548926526814094774362295454360508748539257760537956310974093921762858734985329221417763480319946619678306384258930748995178251895211677684779099156586252263962972321085383014861051045351702445981428687624887876159016437864675927436580192441635001432139213602840389229436078256411005446767237262053372712692659333634563259179288138049271026183818926656912457570040705022131691239339981670912191976546282325266264354880958946717391679287855911899951947652510970732453306634840667413963089542025742202208352548388769507998281428941441301228443013889724386420198362329512060561101980729683126457413593438747791824166697831191555990753654812422902440269246284430538591900330687852515016024608144043446948449188056852954459145325379978162383646148730477737782431342665124552565105605465300476042397444428386428483712460306066610595601971607236525367184104013600876048976016895964209299904788206304717100702509122792052498762384767108993966331719980532859676643877842826953652484907566982093583511661282108825275744963060342332329246472478292458805711077556935720529949673734592682612683550191618502920108512832033839832242071171819722424131776449510011706533398215973371528534766762490751983149709846333103225375325600844448291736967717766749877712367974724964232617522366172897186441951240946076272375246306227592179982467838305352755334493223515520492502112157284963487475474323043010722247751111622561089656935917377187670433354685646945121710477202061979878338910990178542073185737644682134208859804664653092951032194386450328043864849310967257126144155811264828433355786385252168943210644755347376211901250255118518858065425875182510965419302847215817629672899860848854207885462590663692165323930915821763828462239415419815485238511576001813721468023106849310233630995649486877573347716950391967491324154349686110114431406283023860993495418019327265239175583784710536527474808462909968810575010849657140682569598879226349601613316115647310995828875018577499285885017021305409996610495291819100186284271174769515348782794409773684604568576952479679548781829700130847685291236880639933913567779305762909442179172173875928298261027279540694286714939704226405946670352690312803326744506196563376108853690006937348618762878415470143842225984625433153250015304282893481641649141068825826145041153343388180400385495389409353365837485509296982897021240619280532999505479054011693918126137957863663317858751319293563719739344881368284860116273824132471890411782167301908054485742041491647254473891578268041445348685128692410806257729998640470620740152418355706034760660360805917194883190274855944416457631522293047859157306915160142157318392287994890314013053235988634620997511599874999440144724042076549395613539344508777721988577673106137156539732056264711706093632507762007528356656925879250877770049775420779624322191792595074754542351691090541392759691554649629017020535747606127808328885696172297208076463566485796557439345068139757417795265238157170766457219763170941964863149362573827810833643592250236630381057519175513675206708489019246888610898618504823479132139601394420849261260139494859490376100577837405457054455081323940775283485275550837206353403100316613712441937822303913736868852820533275431383495148157513933477076708808378615418465687088578467543842033900890688909602424204024526796759323681604521134935093611559878553829588329148590698413870551882277957486495299092925503543347056340726055884349850178887094193262524270219649201332682635907922598587499778118530007816325333943924778489533522615473116634695359342227599956762130649042191975621487413812340927524007005055038947793880270659975103422385766141920783502478177703685111229600299790867094631157115020156284886274251324809751994800990957961856763574624982497932339381991240484199993047656557052650734859732188007762180472906795620236972291844740596854489001002020671282122220835762545741098819576105647411684333077169516147083014997660087852264042271789536572311436015138949754591986848717881008689540005680403922859233067741455817705897597178054689234007151462902906589428185165592367383386541810249806830846588166241245812178707626885182641379643651977738024154030116888994118777964099329344730971234288862086490085106137033225977577194656524587611627034716416426757754045526671643014006209969936745995430458171552755229754911019275173523764983818647296701849343485115215758801535382125786920170199266144117111699461542359135581802247811553533918707067609777206316771271846818117/2338224387510 Time: CPU 2.45 s, Wall: 2.51 s }}}

Or a list mod $p$.

{{{id=59| time bernoulli_mod_p(next_prime(10^5)) /// WARNING: Output truncated! full_output.txt [1, 83336, 23334, 97622, 23334, 37880, 53005, 83337, 35092, 81887, 77352, 85180, 66428, 8808, 53509, 47251, 72809, 38343, 31605, 26844, 27279, 553, 9783, 8336, 67117, 5237, 87725, 1602, 68521, 74983, 31210, 38680, 37700, 59791, 25790, 25960, 47165, 6587, 29457, 61675, 75450, 57290, 62561, 86552, 80539, 72603, 43193, 27052, 42362, 4816, 96631, 81218, 83920, 44052, 86682, 92345, 25874, 90743, 43289, 14156, 94090, 64130, 88568, 43649, 98152, 53610, 1156, 4211, 60053, 60531, 66417, 74673, 15298, 96930, 76496, 93044, 69154, 45099, 8120, 8396, 94226, 7461, 91339, 62542, 41967, 88759, 10784, 46688, 19899, 90103, 83345, 31614, 98156, 2945, 90395, 25450, 28697, 87450, 22035, 76440, 87345, 97964, 1733, 87741, 55759, 48890, 78770, 62324, 66838, 27992, 93802, 9582, 98956, 34136, 77664, 10750, 4445, 59387, 60171, 84582, 61566, 62227, 15197, 11635, 70578, 39616, 744, 86683, 56151, 18546, 77977, 71345, 51202, 83668, 2132, 94664, 87929, 45229, 57149, 98375, 2255, 62127, 65372, 69910, 60051, 81049, 70400, 89136, 65319, 62678, 22125, 13072, 78938, 63847, 18457, 1994, 58076, 92556, 53519, 12958, 17637, 96703, 83249, 97179, 43874, 53380, 55802, 34593, 9323, 46913, 23018, 38077, 65273, 74778, 84536, 41138, 35293, 84588, 95054, 59789, 37763, 29898, 21424, 41792, 12664, 86629, 93424, 30067, 84701, 83729, 56916, 81541, 16897, 36374, 97114, 91880, 17555, 37345, 42652, 81345, 66246, 30111, 96180, 85356, 92124, 64784, 67251, 12653, 37668, 22631, 78454, 98330, 20906, 5421, 88627, 5774, 68515, 94476, 40623, 43766, 61017, 8565, 55489, 90680, 21048, 97031, 39094, 20672, 20824, 33732, 26627, 47540, 32246, 6432, 33354, 44008, 2703, 27067, 58342, 18845, 61066, 9214, 90189, 79477, 11945, 45982, 43643, 96763, 73176, 82060, 56535, 74318, 76354, 9463, 7737, 50992, 69211, 34649, 96462, 11129, 89534, 35685, 811, 31056, 30353, 74274, 1747, 96170, 70060, 82699, 27872, 16063, 31166, 86806, 9872, 43439, 98375, 21141, 12141, 29754, 63624, 43175, 22833, 11313, 68506, 65649, 70367, 76329, 39916, 32659, 26758, 90650, 41992, 92789, 41135, 53228, 58717, 25043, 25582, 51667, 89093, 65056, 66905, 75624, 66062, 94280, 29461, 4414, 65694, 97699, 47694, 32213, 45599, 24357, 82107, 89502, 2202, 44582, 18393, 94981, 53021, 5107, 9469, 98528, 83822, 18194, 7165, 69095, 50740, 22910, 43065, 12339, 80748, 5512, 28310, 7101, 22175, 46694, 59101, 76316, 26876, 42350, 56665, 13442, 68598, 94307, 70902, 95809, 58443, 3303, 17300, 51806, 33214, 32722, 98390, 25227, 31852, 17284, 8813, 23427, 25268, 72829, 6031, 33254, 50789, 35492, 60834, 5788, 4576, 85971, 29353, 98234, 93239, 91630, 14225, 32989, 26142, 69077, 72170, 7876, 44222, 93063, 71265, 59967, 89894, 95802, 77733, 82275, 97417, 59555, 6728, 40658, 9493, 23309, 79141, 57383, 86212, 59820, 87166, 10820, 54540, 48930, 8163, 94696, 34785, 35008, 59937, 82935, 57187, 85813, 27823, 60702, 65723, 54728, 92827, 2696, 90910, 43457, 30425, 97074, 80144, 41997, 58179, 54407, 70048, 67598, 9890, 85403, 82928, 50727, 13700, 87660, 5878, 18180, 10403, 79749, 36372, 35887, 60100, 97069, 38063, 49053, 29838, 62552, 96972, 31540, 11351, 38911, 23504, 75894, 52824, 90089, 91656, 99648, 73214, 71595, 34335, 94453, 82826, 16405, 40330, 57659, 28319, 57508, 70489, 3518, 22882, 19043, 85441, 12369, 24971, 69557, 31513, 99786, 61338, 55617, 22182, 27951, 10288, 22121, 75322, 74530, 55985, 17268, 98485, 45225, 33408, 43868, 36514, 152, 86902, 2940, 11136, 92794, 62572, 29862, 15249, 45653, 69341, 76595, 21745, 10630, 55689, 59504, 25225, 42497, 95770, 581, 80929, 42584, 89195, 27673, 30952, 1643, 86467, 95614, 42531, 47517, 30946, 6520, 48099, 83078, 20277, 530, 87968, 11730, 5394, 82597, 86079, 76056, 24753, 79307, 6117, 60797, 88235, 59861, 67074, 55379, 5584, 21945, 74072, 47380, 72357, 96334, 97889, 49697, 70307, 31256, 57940, 74186, 57195, 73374, 95625, 98137, 18583, 31398, 9159, 58163, 44967, 65986, 89207, 4645, 30876, 87269, 98942, 76237, 90081, 84992, 41781, 24758, 40023, 27983, 68009, 91244, 93447, 30375, 39421, 66789, 37030, 32049, 94146, 33292, 13726, 39967, 90244, 6686, 20099, 91593, 55885, 56702, 17803, 37707, 70726, 41749, 50547, 19801, 24952, 36239, 50476, 75547, 15914, 11905, 25952, 71950, 54896, 49187, 15823, 83743, 64691, 56586, 30687, 722, 52327, 42172, 5394, 65107, 13100, 92447, 82829, 24880, 59569, 60082, 36221, 38638, 64743, 34225, 86681, 44425, 30556, 27013, 5820, 94492, 45318, 74484, 86308, 2041, 24210, 88015, 17063, 15795, 89542, 16402, 78632, 44428, 61080, 86146, 86061, 50766, 93604, 34977, 18471, 58790, 70862, 93019, 74432, 1277, 48691, 67641, 50013, 44751, 59164, 79329, 38693, 66031, 1184, 23613, 44072, 12398, 3312, 19989, 89263, 76937, 87955, 89023, 95549, 5446, 23190, 66861, 31663, 50774, 53532, 66482, 39669, 69306, 98219, 18089, 93269, 15630, 5454, 83063, 60163, 58604, 2636, 14957, 26845, 41250, 19235, 5216, 9134, 52497, 9905, 89996, 87460, 80532, 8559, 787, 2524, 3564, 65881, 11043, 17250, 28146, 97822, 78924, 54310, 14529, 50667, 84226, 45970, 33111, 57796, 99215, 60083, 52585, 87704, 71144, 47186, 84368, 89334, 24316, 59257, 27680, 58261, 92811, 47166, 59133, 68120, 60797, 86500, 36825, 30658, 58786, 27136, 61703, 19393, 70913, 40220, 88818, 1704, 23776, 38239, 64084, 26136, 2724, 38347, 48918, 82814, 75769, 25280, 37255, 35735, 14813, 82091, 3964, 86817, 98977, 1962, 61884, 67566, 11508, 93870, 28255, 40640, 10840, 18589, 86249, 65608, 1005, 42847, 73058, 84119, 81053, 21216, 49182, 35488, 87147, 15377, 47078, 55230, 41160, 61063, 47147, 32929, 55, 50197, 27109, 78514, 49768, 39087, 34310, 22041, 61303, 65154, 45088, 6761, 6204, 87537, 94779, 70753, 93769, 17281, 30150, 92075, 18591, 53892, 52296, 65957, 83913, 31610, 10031, 19886, 6832, 29676, 6556, 4121, 53032, 74499, 48642, 57767, 62593, 76945, 73345, 66056, 89491, 96563, 94082, 79098, 39548, 71508, 84144, 35019, 39336, 54693, 3363, 13291, 45895, 7671, 55857, 60990, 71400, 91088, 62699, 80036, 56743, 54317, 49954, 12565, 31148, 74414, 30471, 12314, 6277, 50111, 83881, 39669, 78622, 14263, 84108, 64368, 36360, 57399, 15676, 59367, 43305, 73196, 7534, 92014, 76763, 46921, 78643, 17144, 68113, 19844, 47737, 71842, 9432, 725, 67970, 13214, 22038, 87248, 79203, 648, 68079, 56472, 58750, 19620, 31383, 71274, 53979, 36023, 22609, 55007, 44116, 80924, 74822, 35935, 99416, 40433, 64585, 78006, 26866, 82697, 54413, 227, 70898, 8796, 44083, 23743, 9690, 8482, 70099, 86266, 85623, 46516, 11508, 45438, 37655, 72580, 2929, 17679, 12433, 68288, 6229, 53658, 786, 12388, 34159, 58737, 92548, 36299, 56319, 58008, 46016, 13692, 89506, 817, 31674, 79034, 26989, 1207, 88812, 84834, 34467, 44270, 57380, 99299, 58245, 28384, 35888, 25962, 22268, 85329, 10973, 54028, 53280, 97986, 79749, 41560, 19608, 54987, 89461, 27801, 48293, 2345, 66754, 21492, 34300, 61271, 68932, 14396, 87302, 66435, 25375, 36418, 21883, 38646, 48327, 70320, 32846, 24867, 19710, 19843, 86771, 40485, 34598, 66648, 64605, 5721, 2481, 37241, 73254, 24260, 9014, 46495, 28596, 60641, 36266, 60063, 26490, 72871, 82876, 2923, 89860, 26384, 27423, 43854, 92729, 19788, 65597, 26764, 12352, 97042, 62785, 1245, 48694, 95536, 36156, 41392, 30929, 83974, 42760, 45167, 10153, 93932, 63791, 38789, 22841, 45032, 48721, 6447, 97547, 30561, 86853, 9021, 59873, 19886, 90028, 39528, 29109, 15398, 23362, 21424, 65311, 66169, 15249, 24288, 91349, 99301, 54932, 54919, 2222, 65146, 50361, 74415, 10418, 70052, 66570, 8456, 76048, 85409, 38607, 22612, 89141, 55375, 77267, 50062, 52177, 80923, 67943, 2031, 15849, 48652, 98790, 63525, 15613, 48683, 73358, 68978, 18274, 14820, 83866, 7493, 53629, 92875, 87027, 36094, 8303, 47625, 68630, 11242, 7096, 29164, 97826, 44694, 68041, 26877, 39945, 93127, 40394, 50847, 76893, 71426, 59429, 78260, 5070, 91596, 77933, 97562, 93575, 50976, 37025, 67491, 96520, 1152, 18636, 62241, 6117, 37956, 63153, 50439, 44029, 97786, 60220, 79230, 38018, 86110, 96666, 71224, 89439, 91310, 25701, 14223, 83865, 23210, 50036, 50510, 47117, 76529, 57427, 68311, 97772, 75016, 76806, 95199, 60696, 43463, 68781, 98127, 52414, 10712, 88550, 92638, 48612, 86833, 83124, 6327, 50113, 39406, 78339, 65147, 95960, 38320, 84260, 88922, 2748, 72089, 34829, 33819, 11383, 59023, 27694, 45075, 62656, 39509, 13838, 80741, 44405, 7578, 82287, 36750, 92254, 6105, 96882, 37579, 42062, 23574, 68798, 56968, 95900, 58130, 16293, 63639, 10129, 30677, 89932, 17468, 59624, 84019, 42210, 94291, 75665, 36892, 16433, 8617, 27338, 23527, 99841, 7828, 47292, 40919, 25688, 84539, 41762, 67492, 58408, 13869, 39570, 53070, 3135, 72264, 34810, 11811, 74987, 31466, 58601, 25035, 54628, 67108, 29407, 20646, 90124, 28740, 25939, 42087, 96494, 22365, 41929, 48898, 54836, 76834, 78535, 48032, 51903, 67601, 2265, 9274, 93183, 77126, 64170, 57886, 41171, 98667, 85037, 20893, 12575, 62034, 87767, 27910, 34147, 54677, 99513, 51145, 61841, 78309, 53647, 753, 69169, 29993, 11668, 3585, 20636, 7641, 68880, 34388, 5014, 73703, 82084, 35964, 59036, 70028, 26586, 408, 63687, 68485, 66120, 29268, 6748, 19002, 1252, 22678, 26616, 14803, 17666, 34564, 24934, 40985, 92675, 24477, 85963, 91388, 26620, 7782, 28827, 69047, 55969, 26364, 57815, 87732, 51811, 60604, 15090, 99209, 43875, 14786, 86509, 61356, 10591, 86462, 80674, 86195, 57425, 6135, 17993, 186, 60800, 74403, 24475, 46213, 74266, 92570, 81693, 38244, 16320, 60976, 89655, 53444, 22916, 53983, 55190, 81458, 6240, 29181, 8512, 88571, 25402, 92756, 81016, 83246, 39099, 24629, 30789, 46805, 63341, 44568, 45479, 83705, 29666, 93564, 40617, 41258, 3335, 6735, 69948, 24145, 94121, 52995, 23970, 44553, 17173, 67651, 25162, 27936, 57056, 25057, 59598, 71273, 44336, 48985, 20455, 24958, 56814, 77188, 52998, 349, 73705, 34766, 32594, 40621, 122, 17584, 75711, 81038, 83705, 99061, 13218, 97533, 20322, 47320, 47742, 35562, 44870, 23497, 62089, 70206, 68958, 40496, 5066, 88580, 75461, 61716, 25203, 49300, 92095, 7948, 38466, 85074, 61966, 27027, 87335, 84957, 49771, 53652, 67527, 34984, 59106, 3352, 11025, 52246, 36188, 94077, 20291, 3991, 79550, 57833, 12665, 43466, 17681, 62468, 32528, 26700, 33626, 65021, 9090, 29621, 16501, 98940, 37903, 39832, 51665, 84415, 87933, 99833, 18034, 19076, 42280, 52057, 3956, 98607, 47299, 91746, 40933, 64526, 73915, 18846, 98306, 62031, 76551, 82245, 81773, 78456, 6815, 29272, 90456, 22060, 72988, 10811, 79886, 94981, 52022, 31565, 89078, 31247, 32535, 99283, 62707, 28733, 89801, 29569, 38911, 21235, 89464, 66812, 18300, 68658, 45857, 65296, 28627, 13166, 28990, 33172, 59360, 95892, 8088, 73190, 69417, 77427, 11428, 80363, 54633, 87220, 55695, 9727, 51162, 15222, 76192, 95005, 70767, 25769, 6504, 885, 74637, 32593, 69190, 82514, 57586, 12206, 58182, 2970, 72349, 37182, 34664, 82023, 47292, 32373, 547, 2884, 78168, 82609, 57413, 89096, 58321, 46967, 81251, 20460, 12165, 88228, 33950, 47722, 54558, 66801, 94504, 66255, 10976, 96319, 81821, 94679, 45741, 37003, 38620, 21170, 21416, 7048, 31861, 25273, 15977, 9997, 44717, 6604, 2990, 59443, 9771, 8364, 54979, 265, 19050, 11636, 37226, 60939, 93991, 78304, 23037, 66118, 26496, 83747, 85728, 60764, 7504, 54278, 89412, 1986, 99409, 73142, 9087, 37788, 66801, 5096, 58922, 54156, 35794, 31258, 81030, 91313, 99905, 15256, 10533, 8703, 71581, 20854, 30061, 55141, 13833, 40859, 33652, 3467, 11137, 81490, 39978, 73578, 40962, 68074, 53828, 67782, 31306, 9584, 41351, 53353, 14242, 38803, 24494, 78216, 29453, 87759, 48931, 48232, 67783, 95178, 73901, 79863, 40136, 37532, 50752, 70772, 22783, 87348, 17331, 7732, 85888, 60536, 60046, 75196, 27747, 69861, 291, 84725, 79912, 53249, 55206, 82849, 46898, 51638, 27216, 87013, 842, 95226, 5814, 9714, 10598, 23706, 95531, 56162, 10630, 86392, 58551, 35731, 39136, 51814, 31182, 74726, 7288, 45831, 38456, 24605, 85690, 80501, 86706, 73955, 23835, 58567, 70745, 74323, 7963, 62983, 67440, 83950, 20743, 81815, 15735, 14307, 56333, 72642, 52827, 64908, 68255, 59044, 35530, 42151, 57228, 22284, 25221, 92331, 63217, 43519, 32255, 39669, 48229, 19757, 48388, 59313, 35522, 12351, 99291, 11341, 21825, 74348, 13628, 83860, 9966, 47494, 34036, 89187, 2428, 39933, 59695, 96228, 62660, 43342, 88145, 15826, 53774, 69906, 16252, 7115, 28187, 42330, 71651, 37946, 88707, 37475, 11294, 3483, 25992, 93902, 46636, 4865, 87022, 44054, 85360, 29426, 32040, 62156, 30064, 63740, 36985, 98278, 83968, 75140, 41855, 44135, 42510, 56992, 81499, 36818, 7203, 98775, 81463, 39155, 62541, 6530, 98342, 20677, 14690, 87450, 46270, 94494, 97788, 69423, 49707, 22398, 31808, 11400, 26879, 16864, 45080, 93066, 43715, 44827, 62000, 39253, 61977, 49216, 20083, 68830, 34286, 42195, 67837, 62761, 3320, 73952, 62754, 47563, 13629, 65820, 46179, 37277, 50208, 38881, 21757, 49271, 32830, 24022, 65990, 67834, 86383, 64153, 99574, 47278, 71309, 54726, 84018, 25219, 35901, 85777, 34966, 68154, 28546, 19862, 96579, 43181, 34976, 36719, 20390, 60248, 9094, 16817, 4406, 55607, 6725, 29945, 42191, 53964, 768, 66671, 85704, 49804, 67868, 81788, 60276, 77165, 7987, 79038, 63944, 32611, 57268, 21879, 78560, 9661, 71344, 16259, 48671, 86248, 23798, 85680, 2971, 56460, 90714, 55521, 9243, 71261, 12520, 27746, 972, 42110, 89184, 14675, 87555, 90741, 18668, 7799, 62842, 19393, 35228, 14633, 42478, 4206, 14781, 71723, 81490, 70735, 95195, 97941, 26044, 44288, 59146, 42618, 62988, 40117, 7328, 89786, 39449, 83785, 52131, 10302, 65997, 45077, 86039, 21567, 68409, 71608, 18747, 99261, 60986, 41400, 17634, 60973, 4793, 2554, 96885, 57572, 56206, 11206, 29107, 57178, 60995, 42825, 76461, 84831, 59400, 2904, 26100, 26581, 82660, 5177, 60130, 46606, 94772, 78316, 27935, 97270, 4146, 61630, 48892, 8978, 64374, 40088, 96928, 89767, 78345, 33534, 75776, 25645, 60345, 29407, 40646, 88618, 9286, 5215, 42045, 25881, 28000, 72975, 92416, 39348, 83021, 15506, 84377, 46256, 25459, 43764, 29975, 69314, 45597, 23533, 79844, 24539, 25344, 24538, 95166, 69580, 90810, 9212, 57900, 60764, 81861, 97029, 43879, 94143, 93687, 25365, 18042, 74750, 72531, 3619, 18060, 44806, 46428, 48560, 91859, 94233, 63656, 10567, 88474, 45894, 52626, 17049, 24698, 7655, 52540, 57195, 17014, 24681, 91851, 79813, 1331, 13298, 13185, 79994, 78151, 91357, 18091, 75767, 44913, 53182, 9564, 99651, 35359, 34276, 49551, 69742, 60596, 824, 58146, 79582, 20793, 63780, 79981, 1962, 99006, 47243, 70485, 64664, 68520, 68319, 75394, 82522, 66590, 86447, 36197, 10396, 55859, 68173, 11551, 37056, 62547, 29298, 12099, 65430, 48282, 98591, 64725, 97531, 86757, 44676, 75267, 91113, 41202, 12673, 79312, 78932, 72351, 63821, 70001, 87751, 90713, 62427, 91859, 93518, 44464, 47735, 1640, 69272, 58114, 60432, 34698, 74107, 81546, 17039, 53930, 19733, 63640, 98556, 95860, 88231, 67628, 29571, 60997, 67444, 46652, 7565, 5602, 96278, 10809, 31722, 3636, 85345, 45042, 46990, 18891, 39312, 60755, 88375, 76834, 98436, 6009, 73177, 10608, 6317, 81567, 69203, 43423, 3901, 54018, 39596, 9370, 15361, 46877, 5906, 22395, 82033, 50622, 15219, 14191, 7802, 68380, 197, 22056, 91792, 75267, 70125, 17966, 8940, 8951, 58512, 72685, 38797, 88698, 99573, 59389, 50242, 55296, 78626, 52833, 82592, 39080, 89621, 39089, 48668, 10905, 50933, 83434, 57856, 12039, 99771, 9611, 80423, 74799, 51958, 73910, 54565, 32826, 41599, 57241, 45185, 10274, 49979, 66902, 27844, 41695, 32421, 38774, 18937, 8554, 49796, 77710, 31194, 36940, 49913, 82424, 29920, 89974, 59883, 40165, 34793, 62293, 45673, 97813, 18025, 55818, 89654, 8060, 36699, 41692, 36840, 53155, 47327, 11777, 61157, 94201, 47964, 34352, 96083, 10800, 56864, 31850, 93065, 51398, 31379, 22325, 54032, 84104, 70814, 50638, 17943, 50959, 79307, 73948, 40707, 84765, 23911, 66106, 54143, 73424, 76927, 65994, 14838, 73398, 52893, 35792, 16529, 81700, 22092, 17101, 25089, 51380, 98999, 55097, 86584, 1475, 27884, 74982, 72376, 67199, 50237, 52401, 68017, 87401, 35316, 72407, 75903, 21911, 23612, 96677, 95683, 56102, 38448, 23723, 27760, 45748, 36247, 12384, 26225, 42404, 7540, 15099, 26105, 66279, 82444, 59744, 71685, 29435, 878, 92678, 75115, 96474, 14186, 23589, 82587, 64175, 4118, 39704, 55941, 83437, 65112, 40454, 99344, 39333, 62037, 42024, 90797, 18752, 54926, 49198, 32735, 77046, 30589 ... 8157, 15982, 24693, 51746, 42236, 80433, 95464, 41958, 67824, 93232, 31823, 34742, 86926, 26645, 47243, 51845, 97039, 53202, 54287, 88091, 91004, 53138, 98159, 30959, 75763, 98210, 47813, 87766, 47320, 95506, 37778, 66571, 41790, 4530, 13223, 51297, 89606, 76726, 63372, 35242, 80629, 58783, 65774, 2037, 91991, 66933, 70958, 87329, 46057, 56870, 20743, 55453, 53626, 33784, 33954, 41537, 5823, 16973, 26551, 1817, 33082, 23984, 36020, 2762, 68022, 87681, 19008, 93666, 32280, 90262, 55199, 61238, 82108, 61475, 15133, 23133, 12398, 81445, 58767, 84116, 86677, 65930, 41050, 87790, 31095, 19785, 17439, 28351, 4926, 60515, 9722, 56335, 85294, 5692, 80500, 55506, 20985, 82777, 54757, 7923, 18712, 47325, 36943, 93311, 19833, 46145, 28667, 62267, 6800, 65962, 1627, 41644, 32204, 73506, 92363, 66914, 24928, 2360, 87014, 99152, 56017, 97623, 24690, 93489, 89533, 70683, 5034, 90872, 19553, 23311, 31404, 52157, 43517, 45501, 86122, 61505, 59190, 14158, 88727, 37261, 22250, 16806, 64148, 93943, 28769, 41765, 13860, 23499, 64910, 78167, 14421, 55226, 21356, 11466, 34045, 29078, 74477, 78537, 29768, 69028, 97948, 86768, 94092, 50879, 83189, 84623, 32825, 1975, 91292, 53468, 3461, 69644, 59112, 37858, 56031, 63931, 61317, 27330, 99046, 11000, 62105, 18684, 92729, 89560, 27671, 75366, 14140, 59401, 6390, 37799, 66519, 38580, 74347, 3148, 36141, 2159, 73636, 88777, 94570, 71670, 79291, 82607, 68160, 85798, 16084, 20372, 71106, 61354, 43111, 3360, 1441, 99916, 44895, 81058, 41607, 44086, 81519, 7360, 56493, 8709, 71266, 20836, 70275, 38005, 24419, 5614, 21973, 99655, 85277, 14764, 89323, 69363, 63207, 50821, 70904, 68479, 45040, 47585, 2676, 34971, 78688, 90266, 9782, 14983, 33877, 24527, 25270, 94271, 38341, 22686, 76142, 84220, 13904, 34805, 65949, 31884, 12313, 57364, 45429, 11215, 97628, 83695, 80258, 40205, 12991, 94464, 42926, 44168, 89114, 6067, 57863, 49263, 98699, 39574, 63490, 12287, 55723, 11848, 68082, 56212, 73934, 72657, 35906, 867, 9953, 90874, 6140, 89037, 39724, 76953, 45787, 85675, 32320, 68780, 81867, 31729, 72132, 66989, 45921, 9873, 86360, 20110, 8220, 32210, 55023, 92474, 40355, 53588, 18031, 45096, 64670, 27379, 38830, 86300, 41037, 63261, 19728, 47709, 58717, 76901, 36544, 51222, 65999, 40349, 18255, 46, 71085, 11453, 19959, 36447, 91230, 49154, 23449, 98820, 4523, 90851, 70309, 62108, 7045, 86351, 11861, 61633, 76192, 59800, 25192, 37020, 68129, 26884, 10564, 53067, 56133, 37124, 16470, 37477, 73607, 48232, 92659, 40960, 4779, 51312, 16274, 35401, 52079, 1665, 80891, 42005, 94162, 86369, 49316, 63709, 77183, 25300, 49220, 68925, 83338, 9792, 85308, 52542, 82948, 98751, 20376, 47801, 94328, 32212, 58469, 49775, 83766, 59542, 83732, 30136, 13986, 78588, 93908, 9941, 71691, 51468, 30615, 27469, 1378, 30888, 77071, 66573, 56322, 20143, 35168, 93797, 69597, 85129, 21096, 31241, 34299, 92852, 54290, 37086, 73759, 86282, 38281, 86158, 95543, 72541, 52698, 2462, 93580, 85429, 16508, 74380, 97762, 72044, 68235, 64297, 21790, 95550, 91316, 46434, 16717, 62716, 8273, 11304, 67598, 2093, 84956, 13748, 38730, 19945, 72803, 69612, 69913, 35253, 21416, 70022, 82305, 5108, 80616, 27603, 58578, 34857, 14586, 12476, 81880, 28549, 78887, 8723, 18454, 90955, 27670, 23927, 54484, 26199, 23341, 9576, 85502, 71884, 32776, 96068, 9717, 1108, 72773, 72290, 5647, 75745, 87460, 49381, 50682, 38861, 26904, 27841, 8316, 42297, 31473, 95297, 83852, 98570, 67914, 43280, 89754, 59989, 76101, 78407, 64283, 90619, 28602, 93666, 90088, 87464, 24170, 12574, 42068, 36119, 48987, 93951, 33893, 46765, 59263, 34933, 75142, 12877, 96113, 15511, 95073, 79251, 63135, 45467, 51909, 51178, 8356, 93217, 81815, 59824, 13619, 70816, 38498, 14235, 76413, 52397, 67061, 46419, 48992, 28040, 56244, 13098, 51296, 13542, 17130, 45126, 33331, 27098, 44692, 84919, 28192, 7408, 97120, 5169, 71375, 15314, 3888, 84854, 56886, 24538, 47506, 70493, 11604, 48678, 23718, 11223, 39887, 89849, 76024, 29504, 79711, 64334, 98605, 96026, 17066, 7570, 19761, 61123, 73291, 65848, 79785, 46203, 91881, 13617, 16691, 27404, 65758, 19396, 97356, 80331, 32640, 44274, 65723, 88866, 18622, 30821, 34607, 20729, 1791, 23624, 76970, 945, 67, 59253, 89712, 87795, 6599, 66329, 43380, 22635, 25867, 68412, 8449, 77879, 99749, 99502, 23713, 61233, 27657, 84507, 26305, 20685, 7214, 72176, 32644, 72905, 25812, 55301, 50130, 86574, 4932, 7818, 58775, 62231, 73991, 38430, 29294, 69695, 90267, 66217, 76542, 96519, 32146, 45470, 36296, 42268, 11921, 56010, 23950, 94801, 35540, 85368, 45210, 8428, 55981, 98170, 70244, 6818, 38979, 61993, 35334, 41530, 52321, 46116, 25312, 79807, 87513, 95235, 59824, 8942, 6913, 86269, 57578, 71258, 73196, 28823, 10984, 1991, 28631, 24186, 61587, 14951, 79861, 95764, 88700, 34681, 85104, 15780, 82032, 27531, 2385, 97406, 21189, 87929, 35243, 97565, 13560, 67655, 91213, 99574, 12625, 21587, 45827, 8917, 68399, 5629, 46237, 33008, 38401, 52421, 47157, 64028, 98208, 93453, 75235, 91350, 98335, 72377, 86480, 78783, 12151, 65320, 20315, 8724, 37194, 3211, 58603, 83248, 68291, 40505, 72141, 37007, 36748, 52755, 40616, 21023, 90050, 71244, 46361, 1873, 2426, 95447, 37511, 57914, 90897, 62751, 96612, 69047, 18254, 85942, 3099, 25063, 89226, 21657, 36474, 66571, 29174, 71529, 24769, 89633, 71411, 92631, 97441, 77504, 61896, 99593, 80001, 24596, 52530, 91463, 1957, 39812, 1534, 17399, 23382, 92027, 10977, 73509, 2784, 83495, 99320, 35249, 2126, 76002, 32258, 47038, 86443, 20381, 42612, 87198, 83406, 50376, 5203, 10016, 40095, 83415, 96079, 46550, 88231, 68932, 71009, 76140, 16312, 77761, 62217, 80016, 93431, 13851, 17358, 89434, 90789, 74312, 40585, 19089, 90385, 71762, 14613, 15454, 29594, 20661, 34850, 68795, 82152, 42166, 82231, 41205, 35776, 88658, 48379, 79945, 95240, 86009, 32008, 15946, 64226, 24896, 83111, 89819, 91822, 88141, 70977, 56207, 8436, 83012, 32824, 54254, 80365, 79506, 76303, 83250, 66141, 39068, 56209, 18218, 19077, 73492, 3114, 67420, 88499, 1878, 53654, 80303, 97428, 1430, 30416, 91817, 69891, 11763, 77918, 54168, 58320, 20072, 89610, 92604, 65862, 26847, 52672, 93358, 54732, 12527, 72884, 44695, 68807, 74790, 89749, 84471, 99407, 99291, 28129, 7317, 99909, 55506, 23846, 55180, 5098, 44741, 5606, 76181, 1498, 85481, 12925, 5363, 43535, 60731, 15308, 65292, 19634, 5252, 96328, 43811, 7683, 12213, 5688, 32620, 21245, 46244, 47180, 88238, 92612, 3627, 25663, 98290, 76814, 67050, 91705, 16001, 4705, 1113, 22157, 53070, 66468, 22062, 99641, 28927, 60574, 24034, 99307, 57202, 75633, 59684, 57, 14281, 66440, 78804, 5179, 89046, 11203, 17707, 57598, 94919, 40874, 94853, 81976, 77914, 34975, 76579, 22054, 80417, 99120, 72033, 7828, 68912, 16702, 63519, 47519, 18757, 21969, 93102, 40995, 53475, 37776, 1640, 21691, 50363, 63140, 28141, 97183, 77177, 73523, 52227, 97820, 37942, 99602, 77754, 24790, 58061, 54020, 31559, 58561, 46476, 45651, 1381, 62658, 71831, 53816, 20791, 4095, 62042, 82025, 18268, 74043, 18875, 1162, 52168, 74731, 65337, 49107, 39489, 39316, 36408, 10726, 22255, 25997, 98951, 62486, 66178, 8149, 57620, 11389, 30974, 16914, 77336, 39887, 56087, 55860, 31490, 86351, 60500, 90528, 53822, 62835, 217, 56751, 95122, 63217, 70744, 30201, 38372, 4536, 93358, 10234, 46584, 66561, 18159, 39443, 76037, 22253, 61387, 79178, 67209, 18143, 17325, 72211, 5841, 83857, 57010, 56198, 93287, 57705, 70049, 62387, 81372, 29124, 39758, 95735, 36979, 77355, 20795, 55578, 34795, 24423, 53906, 71869, 39950, 39676, 9324, 29764, 11797, 86011, 41992, 11689, 46512, 81274, 57452, 30605, 94937, 2888, 16218, 61877, 96886, 8758, 92023, 26727, 93139, 20006, 80498, 31290, 7669, 71955, 5302, 20515, 65700, 56646, 30883, 20657, 83200, 57300, 79682, 38199, 94243, 90195, 88687, 72842, 64368, 7229, 19280, 81644, 4792, 43241, 70922, 46579, 8244, 39606, 96254, 33862, 26523, 96251, 88061, 13918, 96211, 18567, 33231, 85768, 36050, 56159, 70113, 17403, 88859, 43210, 69667, 44949, 43868, 43636, 24447, 44484, 4565, 48184, 11892, 10445, 38335, 46029, 49288, 99670, 98902, 63630, 76624, 41408, 69055, 9371, 35987, 74796, 47429, 40658, 28511, 8264, 21279, 16224, 65028, 9169, 41963, 4658, 84773, 75385, 60184, 30562, 71640, 231, 90229, 3097, 47011, 62551, 69138, 35501, 98630, 20213, 37641, 86108, 20374, 96961, 46379, 44459, 56710, 28962, 28190, 15608, 34723, 75562, 66509, 55457, 35267, 91569, 39288, 56537, 58363, 22164, 50100, 63731, 99758, 40111, 82485, 57402, 68481, 29405, 59758, 47312, 94365, 34249, 72747, 33558, 69859, 48326, 48531, 5402, 71738, 31070, 24330, 12312, 21240, 51559, 74739, 53898, 19798, 77576, 243, 3726, 54650, 67568, 74432, 84362, 94322, 89404, 94145, 11863, 69125, 78326, 7223, 62879, 58356, 90215, 29311, 23549, 57641, 1509, 41778, 6543, 26948, 70760, 57069, 72637, 1549, 7690, 68892, 38862, 31824, 61112, 12350, 67502, 85170, 30085, 39815, 89416, 78830, 8639, 5036, 82502, 14754, 59900, 22056, 27136, 14075, 64050, 8506, 29963, 4128, 45384, 15950, 18974, 19297, 38951, 83469, 2803, 65341, 14316, 14731, 45592, 32182, 17131, 80351, 70124, 23560, 87643, 67247, 30173, 99250, 82433, 84212, 78618, 47368, 74482, 45135, 76111, 40056, 58737, 44120, 54877, 9157, 67026, 79631, 26417, 34478, 4121, 10490, 52028, 63236, 93141, 97371, 91546, 59914, 56385, 33097, 32588, 3634, 91900, 10462, 79317, 83031, 39751, 34769, 25859, 15092, 34926, 63002, 2573, 42959, 6873, 13354, 80666, 19845, 49836, 81403, 96205, 52964, 6908, 1711, 29491, 31073, 20226, 35785, 65224, 60712, 38062, 95003, 73538, 67684, 63531, 62083, 65676, 79528, 88806, 28787, 94896, 21116, 99497, 26342, 91369, 82316, 11200, 68938, 8688, 61791, 99912, 54649, 37559, 2622, 31367, 77261, 89357, 37691, 15128, 28262, 51267, 93660, 66669, 72914, 41354, 27665, 4488, 77646, 32823, 57765, 26380, 92270, 82590, 64768, 64443, 88342, 7191, 69978, 31451, 28164, 2638, 82706, 59597, 13946, 19836, 88767, 3555, 95359, 9621, 56361, 1345, 58759, 67879, 66150, 98497, 85891, 59509, 71276, 73981, 1448, 96873, 78621, 56532, 23421, 65581, 629, 95455, 29931, 53787, 96326, 74918, 21344, 48986, 69555, 62153, 85027, 90473, 90909, 35637, 64466, 17086, 1949, 28910, 40, 19746, 79281, 72949, 68376, 64976, 49006, 97919, 23322, 41142, 13838, 3263, 12928, 8096, 129, 49136, 16450, 95733, 83351, 71698, 36444, 132, 91519, 95871, 18921, 11946, 28867, 17266, 1414, 56572, 4770, 56238, 88803, 18387, 66382, 72803, 69742, 51065, 91240, 97130, 84343, 11776, 71844, 47166, 13979, 75569, 44947, 95210, 50837, 4645, 58829, 45493, 14905, 76390, 45385, 1543, 87531, 54229, 72509, 362, 56414, 87842, 26917, 42683, 70831, 51654, 98489, 58443, 75669, 1228, 78014, 19090, 95239, 52210, 96776, 12926, 5559, 62173, 67987, 66013, 47148, 69150, 16189, 26704, 96427, 32835, 29010, 5639, 4594, 6200, 82875, 753, 51278, 82423, 57205, 47174, 3629, 70931, 17854, 8108, 36028, 24779, 79050, 52938, 90531, 67527, 94899, 30190, 18240, 95630, 4822, 10780, 67703, 62311, 78077, 10359, 12183, 32833, 37368, 9969, 15736, 17146, 62653, 97975, 27420, 19098, 12431, 54356, 93722, 60349, 92983, 34651, 16688, 23015, 9540, 66010, 54845, 67852, 12830, 69662, 54288, 44009, 46368, 782, 43406, 5064, 38749, 24833, 28729, 24131, 82139, 60368, 19753, 3597, 37718, 75658, 26511, 70188, 11181, 14902, 96084, 81201, 52269, 96951, 87329, 44420, 55889, 87984, 36693, 69659, 53019, 11114, 67249, 35369, 15929, 86328, 74309, 68402, 55732, 33015, 37965, 41139, 39363, 61102, 1415, 878, 17199, 4477, 29534, 74435, 33400, 86305, 2354, 7468, 63913, 27207, 44482, 455, 17139, 83161, 58223, 36801, 72528, 19790, 6323, 69285, 47752, 83262, 44957, 88076, 13268, 91143, 94244, 71460, 23915, 4048, 37143, 36656, 37196, 76726, 24657, 3035, 58260, 89615, 40767, 89973, 77277, 85057, 92931, 39264, 85108, 91659, 38769, 89233, 16110, 95666, 73309, 38570, 41055, 67124, 85797, 200, 50873, 45024, 74320, 90182, 39173, 82662, 71877, 66752, 93152, 27990, 62221, 93282, 56001, 35893, 45214, 90146, 17064, 73035, 62226, 56544, 46443, 36702, 28321, 46847, 14840, 21402, 47117, 30808, 64972, 90081, 5663, 97545, 20775, 3869, 16465, 27635, 26179, 87303, 42240, 53498, 26372, 60798, 96600, 14142, 88503, 68073, 46739, 69927, 65011, 83432, 56974, 16272, 57832, 22343, 44824, 40641, 74283, 68101, 11018, 33523, 69136, 76241, 6533, 18999, 77787, 4294, 69289, 71545, 94687, 77537, 17420, 56198, 25598, 22222, 57276, 85748, 68276, 31361, 71787, 73161, 97974, 57311, 53227, 50698, 75311, 285, 78677, 42568, 95657, 3381, 67731, 39306, 37878, 2491, 40033, 69841, 4696, 87402, 37382, 68762, 58507, 75521, 64281, 13808, 76823, 76000, 31699, 18701, 74129, 57648, 79447, 82753, 21273, 4572, 15851, 63127, 32568, 60352, 6133, 89007, 57363, 47031, 52889, 37260, 27018, 26517, 5498, 15324, 38525, 8534, 35813, 32860, 51711, 17184, 69493, 22316, 5848, 25146, 42231, 22941, 15344, 6559, 48461, 50188, 14316, 67528, 88945, 43493, 76771, 53291, 54371, 19363, 34455, 13, 80760, 59784, 18968, 47780, 88829, 13297, 99414, 4928, 27762, 12237, 26905, 55898, 56413, 42835, 24054, 88403, 43170, 64786, 86958, 62281, 1600, 66673, 63671, 32362, 23828, 82682, 77622, 83651, 59198, 95810, 57640, 16707, 37128, 3354, 32827, 26065, 12598, 35384, 54872, 59421, 41018, 74957, 40360, 9273, 35663, 11510, 65234, 22247, 9351, 72042, 44784, 67416, 25730, 65312, 30582, 59298, 74545, 5360, 87978, 13438, 83148, 16017, 91600, 57518, 49529, 14714, 67682, 93167, 52381, 75631, 75581, 63136, 91556, 85460, 58621, 81577, 83287, 42874, 75979, 55463, 25355, 64983, 65630, 47958, 79533, 79150, 44067, 87733, 35363, 81220, 52190, 41052, 34567, 66535, 76133, 47240, 31162, 59508, 72239, 66639, 91567, 83290, 52313, 72958, 31269, 49475, 61723, 52137, 32377, 98625, 14175, 68489, 89186, 91645, 58189, 24038, 35475, 71351, 66503, 14609, 5659, 36657, 46618, 38786, 92360, 81066, 19360, 62376, 55486, 83798, 85932, 55552, 33465, 30331, 84034, 29337, 47402, 72454, 75160, 64039, 76352, 30204, 84829, 65072, 74053, 87623, 39047, 84767, 42988, 80074, 48454, 86792, 2134, 91183, 54221, 11237, 23368, 77914, 90715, 23010, 92746, 87561, 6206, 13936, 13887, 47514, 35783, 38104, 7461, 10340, 23644, 77707, 49186, 40884, 89136, 44426, 99846, 79859, 17304, 49013, 33453, 41731, 4451, 30121, 76481, 80956, 39067, 92761, 92713, 82166, 26376, 60416, 70331, 97591, 28785, 54768, 15240, 40408, 53771, 59990, 16490, 6572, 77862, 34943, 61564, 47034, 51737, 23705, 89323, 34278, 79767, 2741, 68472, 54946, 76869, 39723, 56898, 56539, 27238, 92097, 90492, 70224, 92673, 30389, 59115, 31364, 62643, 35256, 31819, 28032, 99973, 75518, 5279, 76173, 47534, 18065, 36318, 66533, 69948, 83407, 96302, 90904, 81516, 24864, 86782, 61211, 8988, 82845, 44512, 54368, 75112, 5131, 14719, 9884, 30891, 58409, 88770, 30017, 4747, 54897, 14207, 1536, 91168, 43898, 76425, 52513, 68567, 2864, 59022, 97422, 40593, 67358, 8350, 35246, 88081, 12378, 87604, 25922, 3772, 4679, 53310, 24026, 15413, 14262, 39239, 65303, 4999, 23830, 50226, 75489, 21931, 95177, 63966, 85080, 50782, 89608, 7541, 26500, 1857, 10042, 59268, 35011, 16819, 27630, 74683, 17422, 73958, 35666, 29231, 57345, 28028, 7971, 12873, 93757, 45279, 74724, 94470, 41723, 7296, 8311, 58545, 14078, 45650, 37907, 42395, 28287, 48687, 71957, 59740, 78728, 73563, 64526, 93846, 51308, 64264, 78736, 92362, 59726, 22578, 87912, 38360, 48739, 26254, 55323, 18943, 8424, 90041, 74012, 44450, 39464, 75874, 33045, 21779, 73861, 30643, 29428, 94417, 92279, 53164, 72963, 12929, 75931, 29584, 32087, 80972, 34831, 72673, 46876, 77758, 74177, 23361, 44882, 22188, 98638, 22496, 96368, 8707, 37602, 94248, 91604, 8988, 85118, 79745, 5651, 47841, 90088, 79891, 27894, 62428, 9616, 34351, 60905, 37567, 83286, 49463, 91180, 57093, 70564, 94113, 7450, 8197, 11450, 43162, 66751, 8717, 73334, 72384, 34513, 57492, 96423, 93559, 28262, 98810, 12319, 71785, 4999, 4214, 67805, 58323, 82999, 68464, 34766, 52667, 88771, 23311, 88336, 85518, 66419, 50595, 67402, 9297, 61501, 19928, 35658, 39925, 40307, 19345, 19120, 4231, 44616, 25130, 78431, 98420, 10133, 13610, 36874, 10360, 86160, 79004, 84582, 18625, 2321, 62079, 15503, 70581, 81476, 67653, 23629, 53718, 27190, 79919, 20913, 91522, 13380, 3547, 32780, 31602, 56655, 28657, 44089, 83990, 85034, 30304] Time: CPU 0.23 s, Wall: 0.26 s }}}

Basically, you can get alot Bernoulli numbers quickly!  

Now, let's work over more interesting rings and fields than $\mathbb{Z}$ and $\mathbb{Q}$.  

Sage, of course, can do modular arithmetic.

{{{id=60| (8+7).mod(3) /// 0 }}} {{{id=63| (8+9).mod(5) /// 2 }}} {{{id=65| N.inverse_mod(p) /// 5629424454395772101788469153479761645017276747431494780318820405324076416609134694013237984486401657072165169748256318429784401972667689726083156871252938265564654625339031629578136048895615438226126990397373476060328301461872397304797593698919995236580267932443522281611983901299683956561141634993232389031471052595052093200761981414371450944891442451140687800344598310657705081700559932201028217663 }}} {{{id=66| legendre_symbol(N,p) /// -1 }}} {{{id=67| legendre_symbol(19,23) /// -1 }}} {{{id=73| CRT(1,2,5,7) /// 16 }}}

Even better, we could work with finite fields.

{{{id=68| F = GF(59) /// }}} {{{id=70| F.gen(), F.multiplicative_generator() /// (1, 2) }}}

You can coerce integers to these finite fields, and also lift back.

{{{id=71| n = F(24); n /// 24 }}} {{{id=74| n.base_ring() /// Finite Field of size 59 }}}

Automatic coersion . . .

{{{id=78| (n+2).base_ring() /// Finite Field of size 59 }}}

Lift to create a new element in the same equivalency class as $n$ over the integers.

{{{id=75| n.lift().base_ring() /// Integer Ring }}} {{{id=76| n.base_ring() /// Finite Field of size 59 }}} {{{id=77| 1/n /// 32 }}} {{{id=81| G = Zmod(23^4); G /// Ring of integers modulo 279841 }}} {{{id=82| m = G(23); 1/m /// Traceback (most recent call last): File "", line 1, in File "_sage_input_98.py", line 10, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("bSA9IEcoMjMpOyAxL20="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in File "/private/var/folders/l5/l55HHC6uExG+F0kEqsPAgU+++TM/-Tmp-/tmpcp77kD/___code___.py", line 3, in exec compile(u'm = G(_sage_const_23 ); _sage_const_1 /m' + '\n', '', 'single') File "", line 1, in File "element.pyx", line 1799, in sage.structure.element.RingElement.__div__ (sage/structure/element.c:13260) File "coerce.pyx", line 745, in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:6663) File "element.pyx", line 1797, in sage.structure.element.RingElement.__div__ (sage/structure/element.c:13239) File "integer_mod.pyx", line 3056, in sage.rings.finite_rings.integer_mod.IntegerMod_int64._div_ (sage/rings/finite_rings/integer_mod.c:25274) File "integer_mod.pyx", line 3371, in sage.rings.finite_rings.integer_mod.mod_inverse_int64 (sage/rings/finite_rings/integer_mod.c:27056) ZeroDivisionError: Inverse does not exist. }}} {{{id=83| H = IntegerModRing(2^80); H /// Ring of integers modulo 1208925819614629174706176 }}} {{{id=89| H.is_field() /// False }}} {{{id=90| HF = GF(2^80,'a'); HF /// Finite Field in a of size 2^80 }}} {{{id=88| J = Zmod(24); J /// Ring of integers modulo 24 }}}

Now let's look at p-Adic fields.

{{{id=85| K = Qp(23); K /// 23-adic Field with capped relative precision 20 }}} {{{id=86| a = K(101/23); a /// 9*23^-1 + 4 + O(23^19) }}} {{{id=91| a.valuation() /// -1 }}} {{{id=92| b = K(1/3); b /// 8 + 15*23 + 7*23^2 + 15*23^3 + 7*23^4 + 15*23^5 + 7*23^6 + 15*23^7 + 7*23^8 + 15*23^9 + 7*23^10 + 15*23^11 + 7*23^12 + 15*23^13 + 7*23^14 + 15*23^15 + 7*23^16 + 15*23^17 + 7*23^18 + 15*23^19 + O(23^20) }}} {{{id=93| b.valuation() /// 0 }}} {{{id=98| K.integer_ring() /// 23-adic Ring with capped relative precision 20 }}} {{{id=114| K.uniformiser() /// 23 + O(23^21) }}}

And finally, Number Fields.

{{{id=97| x = var('x') L. = NumberField(x^4+2*x^2+x-1) /// }}} {{{id=94| L.gen() /// c }}} {{{id=95| (c^2-3*c+4)*(c^5+2*c) /// 2*c^3 - 21*c^2 + 5*c + 5 }}} {{{id=99| OL = L.ring_of_integers(); OL /// Maximal Order in Number Field in c with defining polynomial x^4 + 2*x^2 + x - 1 }}} {{{id=100| OL.basis() /// [1, c, c^2, c^3] }}} {{{id=101| J = L.ideal(c^2+c-1) /// }}} {{{id=102| J.factor() /// Fractional ideal (c^2 + 1) }}} {{{id=111| J.is_prime() /// True }}} {{{id=112| k = J.residue_field() /// }}} {{{id=113| k.characteristic() /// 5 }}} {{{id=117| L.uniformizer(J) /// c^2 + 1 }}} {{{id=103| L.ideal(23).factor() /// (Fractional ideal (2*c^3 + 3*c^2 - 3*c + 9)) * (Fractional ideal (c^2 + c + 2)) }}} {{{id=104| L.disc() /// -1371 }}} {{{id=105| L.class_group() /// Class group of order 1 of Number Field in c with defining polynomial x^4 + 2*x^2 + x - 1 }}} {{{id=106| L.class_number() /// 1 }}} {{{id=107| L.embeddings(CC) /// [ Ring morphism: From: Number Field in c with defining polynomial x^4 + 2*x^2 + x - 1 To: Complex Field with 53 bits of precision Defn: c |--> -0.825109883204088, Ring morphism: From: Number Field in c with defining polynomial x^4 + 2*x^2 + x - 1 To: Complex Field with 53 bits of precision Defn: c |--> 0.171647147024427 - 1.57668609232740*I, Ring morphism: From: Number Field in c with defining polynomial x^4 + 2*x^2 + x - 1 To: Complex Field with 53 bits of precision Defn: c |--> 0.171647147024427 + 1.57668609232740*I, Ring morphism: From: Number Field in c with defining polynomial x^4 + 2*x^2 + x - 1 To: Complex Field with 53 bits of precision Defn: c |--> 0.481815589155235 ] }}} {{{id=108| e1,e2,e3,e4 = L.embeddings(CC) /// }}} {{{id=109| e2(c) /// 0.171647147024427 - 1.57668609232740*I }}} {{{id=110| L.units() /// [c, c + 1] }}} {{{id=116| /// }}}