number theoretic functions.sagews

prime_range(10,50)

[11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

gcd(97,100)

1

3*47

141

gcd(197,1000)

1

lcm(97,100)

9700

n = 74037563479561712828046796097429573142593188889231289084936232638972765034028266276891996419625117843995894330502127585370118968098286733173273108930900552505116877063299072396380786710086096962537934650563796359

is_prime(n)

False

p = 2^32582657 - 1

p

1245750260153694554008555015747995031227959851511518428436704756625911152359973973805597596066168459391004198868821113087062042849043048563427193924179676463175953389304422007303179021122683590423098732339390892542105984535224309250632987877260849806827055390890640148456203736011933757802399692661758862749761713589606175375030205627843573215470110440062840356190925033901041163320632970866214924362806816094332901830866523181930912894357059008074501640718536357422308085105982976201444193484971676813199946491899089200558098056097990890695525705693921992982291986901618961860147146814875880764159726311046884555030164699793310214082901825956031372575205936524356319163502414310991184199974228169114458008530530968421087086058856532916655287889014470920783281096828273974246259763310616848312556267921055936818563240486394055300918869210038338942512582376528519785641456934778963323217987073260833245769052615086689389921758899142341598880060204545120812748260225207220628317215719700569145202631764530953143756962644181591286416438753010916954884342935245191518221528363899262892735338016119453245902568024473143297945523059011061033271825854722693075139829328710516400903957917583106254815102208779340868283523732573480854975122589990996308421441689511337922150110782175331158931860953962431964300765845906848176835743518340564468411948601490999557073054496933618274743291328715625694463270625866642869390244224374934777812676790882649092530581536370451328108805988843942850972178684265809907589021341047392159866697564984177351988538103523710931176915957908673779106126245292770333009681907976037660392068365869390838795467364994413478743347763691220190513047743408240777432260732817594774745482746153423341058959527718761343079307889039372602901639533081889692875150392472481076379175685445217026616171667284138448091970708709860620383265730907788678240541679112528271788389435957920483857743367130988228725845072698563861654131080866744299419908718088646427824181927318808813740430825607899263077472775491617781000888335358452738237821473335514061146932142735536501578108832568718984618448602598084439949113637747694648666412914529762283777595483100270839403469500412405257604377369794943718285598064128895948785710225118840951750663500374093324512322743602840336491758823553711892932199639863072362272659233076531592384283308230291868045610982828762913694005069747097517320394352751759557790499437266948768437099577263435055092201814340513794390755488716691503626091189623059618027883608216907164260516647089176116332043636562138391479898701155737780873548017339036535935576760834663025517519599972855485839619775141390758497320281075486500600240600862586142659811294710428565380514834921766684433965722488903913322011577921566193539068863229502365665262704511805242462372764779516028333052911664914349197468818383101983698516268861823140094266654609923492190105430959837539232708389875806302889492805153533546933243436829305203698485170012214381341404105146797690099160964754586630896523942331088867238745459525107284866629592444201362953878744142962473968830895548399019312185714979317712105397182141878935381281046386803233528980200984957178296575521951343689029359576594718327273534270211693475326160255139867973653628925421980068645330049348522019053537791858339003171419250720188472334189123644703107320757853511940442315671355145941141397750361238665209173172208270484699028665869363609715420264978083612325385473579759387229808013199099513308543439054759445874976882627500984928621598560317301378217895779911516585934030893375231659467707624651691892293427943480369657059809380528524381801051711765437664405761700583383462627638896537501864930458991270359475364269594155226999700093398555796227880941276345042399467519656981147170925008367655587339047205258931814525656852901195086632700966143406860611902267136240372774769492969013958165010742190268523593535813386215146623482459722345155998303742815258343763992797700050532548715069890513551288406478690246489536747253091769118661998344249588567993658427650834071829795355366975887597104823285737730113402789688623256554400517777038160050070836248653548794745975798006585830055781428880246461116969023917507187743128194975762179842533968119577291275380051014401012100832069507860159989976763121764445351540482362442145286957125302363634610894238615547857621508272388045333139984660000646523477945229403160854155926524977246935064199578820563814416219606932367328639788932143414076984046214592076155376020838336990348748346045472998353079111743612194947690444704279220894670118281556682233097534297213766156762144153812226457319954005101506644964268298507680249320895880311295413595978725057977855749701073588254093841680032314489589307796436238442848178171251278387995489607373850878056256058012250098078681148563860905883924692833272087629472579838478676906207967272165453182529374265139100207732717967389958746702427390449242587605675732507080004935498108424073178875313483270169276750544405701245455729958478993906771164266693354393729977503924531962404759109578297332118363053858695583563872668868863888514514127892445125569493263839808639767948313335771275716009306330085084749355651498002994119021821716794501046305245744643635575920035289729094262165080699946473154913437865857217464552056868272155375686905184570186755891822841321571872192437974870513645046249358588648486653305287893287767359375875609045904672625050618125797109534536085943345189420482991756893405355566955527302871620645961867148611348678904572458671160958867983188971592724741020499306830566204999680314301449734231694437270959022731658742959040495476357464037222419137477918922535899346000091539722659834722022502643421842361375544243995223945596764635165987230349802996981319403829378979703504795125902185062002776063673789044749278899703906416185672767829974242291843251993342393976120182086957759524565773510238672878335235492995776274372624817529187170194254613625613969795019851352213516007044910141142485484073592641131587319740059891068680583133486725326574794644568832867245933278800432787676053448060054880894765467394751309656443506101162323311445184975727963033574433093465207923008594074746268540219954208235432944068294510047625890148092456659380398862344985886600397916796248146230030485715381112725247185322978714224691226085652176208453959593125177778436247244562688832859198237975896408564927881537852392072031043988309263493972909742505677019524960902505934720234771670788495287200240229039877585706607498236649623205702844604284599807622379435057091796352375573476993270157536570503498953484130981902982393103044377872164045661547061254577414045531825661371474551188235150206409740129227458386496268554133692164527297594788017694781616750011876099857068141298553248776917139068886764252545105008147193311736930895305525439965809029093815729682626400322295894980603607258007015640566411958061707644148355956754981121603217432311604812639439168412943239923506053987852870987117034893563310158592994674776004033943534812578742396250828807578274951255382606135312246031495974045934190048691598080746739137426293805358491914610744817329919112017499313108771357863774401864340588424628265752779809606120393491903370601259190188586907643024557296991617636179866979088470226311889494242047868021512635075110839885077677750915022919193641020911782092451720368098658187413852878024653984893809006524860075069911948040903091565573743152929410232331522918616289161600677359064343166255507379706850813316718505940290904887114687910999316632811314657332312749320644617862875351019889626602877009368552748569253019643938381959729388597636760318987236109288258606090090748835907224584745469719119407504215009300674877932441397121650283316346754798059655533297720660148367372259261631091264065575333225825259272822662844052284732204282953169789651004700797982981809677106808645376568426192734170437314121524680734885625634328077981161705776030914320885219298859324146615051738017852434234814855513646930875349305696638406394169123176972527057655407675589597370396163588570159614935163647667360841508645045841119981102375180723432507972865522004343577377732514745025618025665130668951917788061149262721021547106202304222043496414256552836685361711874217934240039127520466597055706706276496833770917124861021881509147713402646200874866567111509021577939243664248246305825306597399093431921766371857036249817312870336150323483574825577411401848369093647225027521204687951451420811176465144810263369112013038795874847474950084289024121023644570015006302250099964761293961624053401993480248646388580870482369469320937366075234111013497438857654417744497665470198406892944004046499124879520759582231586255500324564140173611940304377878896992670660789183002507492435417070139326268383672148543417250827046486670918739935655749676302733079336621861580776015129016330506467545598589094172180890402857700326060572543272608352332644686154798310226553516902724436956579926796186431848377745595374231113136630830149082075629145006598919832343989160342664590473627472442129919088911992287766897938879215814987415124727585171478608380985382682683148920673953992603353261155422565025566783474043905975101164495883073846215560138601006521705647915075872023413497827436238377184372757608087043145360866635400325657353927337879717838256316175547815948241110857962680953502078376487732770666749552237395125653198795381244366013868536249636866435094800910923886692152013743278519228607050960251011466996749495497917256460927637382554673557032176542434099392067569000981800432988035744998158639993840206537579912965350533384979820124494527210771717069323161544648680183678876164499324858081111376509861308320780115971214913850615877825861281574666603689932674884897999324358767816218074934565724500150546982649351301279915379415113594494157047077128646740337544068641618739312243425269189571881549074155586218437818967744396372352737630895147405723718432218336916523285025747028306380457799664647990341794172497408706028678264277202917549909447653169596178467742789557858446560985582840821978634917492463178758444961915251695508192966239278356101931542287512518187089079259281839722585976857570368259471643200425937710738616550568684146674329193664352047855746864367583683595507119631893418668546077596972188888979325324619110476589548758432975620276424672261480186300106590966929716848507531173341369216206158134608097803500418406924564733388475718099011860938465205368879581890570251892498774175095876726938367138053054786594399854301740054834254900727384771363803396548685359792019876259194599498520797569224290572928146037633223343635216975829744766950454896469244117143673345365960546486246075683178568907714392030501124308435865685606091802973219535758085043933571834299940453512381318797711739152868777742656811941579478873074988058139768270100011726854812906423302751350452448211258789074755490585754944858691550307001919812032144001913732045029084999771684047695463024141437228571868864787749934388815027018032629158153844837197750635082845594392147713303709324139312817313953694293258223918033311651810823384850182580627840831467636265777846358599952467163173698842495073439792795746903886432340153027975419528234772915745141827780010604322745312991813754208216898996989542559104396792650458000767797678861543177241874361234306836709367080265427590309013870769434520158255447681072704040103647029416096036862022530403658258659925805015544002262150464289791720742643083577011678595713916451875265280909145442596047082119184589681343204530818480757867007956437490138766137335986310919722656239201639783722942664283462023482362004240365811150098852011158161685292453278257654616241799606015945379202820603717107704575450733499076307756201627091561751364447192474054363468500248020554806259313419586524596072813323412053974539175651164514349269547169230721248117313573815761632240050718510248076816220290206286595512119339815169002054725782382332489182719159844427475255547161724855614686513842916078487825908319448025279221582476732390056921707541415572897486281415767617098606558557704086018219736687177367028979031347516599821204961112608473802450364297955525467404930172595916685017062541111136636610575384912764249803544716990036396534249726189607642667902031400618599399717733236062493416831903261371883293439872477446929294011747711220642054937607618804281175986377548510020018981065427393430665846211242974260767076939241376769415141619725971061820007569756158313793377984646674814534780970394687932400410159258139557374289472825612663157884164363464325632797408158197520308533732946057612559769422182498423041426067353392008841055276962123013081387920201780742714109293266289318302721585600811071694743368493548009255911051585458040179802100273269150655639923613795089360282120299427071234706281456712810992624887622806852326388483354461648440522133983095706558829826340659104939937600674904754562014133701328661363010275325501382455437151327412514556698874985765590936261533533465858766314908904707396961548640999687475255316820625538923086555308293841710362887609501125788136155397893441978021064417504480447784062132881578617158065198244019511939284208360634875519416210685946233680337934232076402602288415733016284278900241657984828156238702273989648441107920680417695126447303213281984003071684686275490286287295876782408154063187998814758551730266741794103415144802273971635881959557250976398144687494041041422343209177515187153307443039203441312484475720551183279417048729821470616768002350243763063337566166072781044822798771952027271604290831526162752799401893163255389798213062333688674047104630224563719360926986630350154556998850558729368659467718434137685973956072687969755377246697828258712975696837401136135421084090893418749543116516544635283836004601101217859199625643401651741838619325592498739313526453728212748493333401277817890236322411075954325703570718925906368239006711029977024299226655635285234078501498055954665948008159181403749992465753053143324789396857065471565719395222919180146133409673423359807009948131050926882125216998818285348159251211124423340860876504496662833071134841103933982154807962347414668000227824290900270998508605668488116462599089885093019592948542892373132022809728236263998271211840783320670034121647994155425881295674684113354452687219249245829810539997189444232112959093399503711761381916847431463203274941194546474570586786462699259871923824597139539172889409930421287049872012535846460020941574005646721607111237221463406226841048760657024796066613329339153474893259059888544964522017331742755503556497296516845370579778728935404976026557300389416169181290120552623386052341990546637580595204866723960875527045787711562175520937373559086402703706160977925516889989999674443579773136024291872445947229149208488328431616383049697865281062193494810837863553201100465907474465679726299311654564159992577523716355721644614732633119584093834761638634600745476616364938020286746846717375406075013155966885873973901657840056770671102837305229846694502610635067353445876038527460399867277389645178716217492562792830356262474049863143421374015221211989212833407117729041269369531364928198790186032380122719234432241665450882542482009973773679807274166492923340825896508917000594290366265689586714170211074090465899649801563083381580982361605267974050359008068969684890725849748002894300301365487643602906703788598113402804095541262395334189461156940319218946656067781482129322233624940604039833346626693128548466034935696312872027130565047938478046767288616872515393124209086257802232483982237506450097274387137635029835150779482456302425570313327100884028808873526709188388032934828821327043236623906041091312620996288922944029919788014547662459236929181217861118004382724575212041454120325569940193012752302527342240257002235026045621296304141308722611596473760549734829866812834854078225161756344957748430889223187761553826920053622454184833083459751149365131339464909932410531211100895908509097471854686194931862641818466685385770326217806627823908911480944297533493932147852633283973161336770926847850484888849990670449249067546414137530475133900663309576138648926400091764928699919879638358378929051211386282064099182453076409081693900846426571662877739091930926844099292201750873133537243746431791135859367693064285994907459234571706043625309340316250172130641040894927447177045698079643641455047657502638500097839643684157120049901684729315724901088858181845651163208942499665368347113982685815457795205264838602315415800819641351397842874863130674088306814682214779440210534467554461345673845572250597899356474408491668263912306612473393164541935111994658677623762921738009598771835485302706600283395421697338177146004464895637741285044969940608106365766436282283432245502332319926744623286350669710687965194799926240398049851370923517923606203086108856735852608759418718668273312940006244516272154122247859688902363917728927084926471319838305839921458451237148120818087829329548795390578889366407872577831982363894324288028999272331076725021059024147850033547710821171194096496614781110581225882672625633517423343972267534309164744081008000924206488196581405459871258311203902246213591424825764717305829320227486804203127836547599134528860156560594828979337225389979476956693032881336451127800583274169633494059453035228192118215060722149004323549278143716006562855526411973525149266812680994157806499433780805841338137051955135823351847821323755938846738510371041593398351466533137152549792702259229010155772297877719122757001020636246982811553347702724066573201037899405063544435543949423303719342325337549245044739291336799562023046141836775871959599794108051254806012107966199465731257075988736666591136106950056466645911957900955509950270222463306076020678936566951183550909523893865102214085454893908894874686751778357972931827577515070482821454979258418575693214590508343764701132542843174385957582782505066712742653493594566573229362565872868375926095825799268839261729561240287968489891945625054714248020970513294929628983002800679359445389951277263200838879182651783436867305565503920542443355291374418651443478664926241182531042957644187495965483779723598802422692299439167797397390737711942625502320208174264700874950949236357967866535396181305041459552433827219801753269524508496248544807294141776588620545646199189804682832016940501226897363893613126647336995391289653593676613231753232784819411631036198688036036014789158669552098553827434047301514578535139828056593788445377386814647901432399044992550907756508611100111097821599925608132884839997538209280597737493909015272159037277089032262517766064686002980224740899230404357271202338853875684031938344080657115117479327227166256369717524308780868889779372545761687733960995943908701455038282758097857614820276091223788738705464068333174030707022305288674837694863792222653072428713778666706012346916684441506367485672239009987890879852615965328309536924735335600308439404895805981501381457334443566339328617800520525129890901473536269713934167596131914772308959148162259236552044955967115878926093193898257629244662833250122941097217686025101424060438441340479990799647073706859161148692204605125845185256911584228888906517031423927009770645095129556254226953113907125839115747899891962120307819499689139717447588569404417691447292741416658674163202881629927449973005704858754248117160934824759458972088123157694589020911657967741525650985893009610698913630113440055993754842162976796965200761610884122877489173455547872394311125713030146062167511329952608819478964786510267369946534566732843356817975141745229245489662342222937189336187801473900602908460507857454797458665810903812909357195337909774575692579416225706570140392814207412351748858648640802264989269298195939219606749012551969386096767220221840291656282672828371602090977794674814554156256223874180881011347955653068297010685817182517700116212143139920656168511500919327498808663268588553247951530824019531310946574208568386032179932168924061587810895976059225841382237584965544792438753410155660679818005326108737111424153469395716408366605718426641252841457156158731017383304014459581190479138443601608613298619191341521289762306855913710180883560818587137366833530366378918959502447556305010415375432698427721854896632107294215694412616379053455368176184473681839335386210615985090186268121231683473495210291819776884041536911167011356967190512786857013319284321652322375095555511068374731600501308443317350522746661069967488833965454443315170759506833629506651988551225133250545795379288254229211411974041229393961074440230523763678990244584327526847869532038836855722562449327980268427213593564031611293444984521229916996451949287964280819136144672314502426137725844493746810552313324250675112500170069686264711149418373286207867365442138027690892274997405358216121564357720266653414159463858659790011949094476975414000371102547146619723390412436388014507896319368887250791570498790796093895995609766179120471399020345391589438773483293375571041986552978756837774434115779088132984592554745088714171139872564705959739236453224341144909559083845069480436919964907731089472964043193267067366691118635237346651693968196605140114903090337017792080155576887038205453308367879160398028810754262031380878046733427475816980719532223021527996901288425381110274778705110297962522010320660485299654516618280836908499415568922097021666266158141394405133836385041688194440251944051384381623792435594245359427873303914316561675785394379164810371647294527347554269212449310776898262785656112853088633225278622017230332056456077641150711658867315387766288713948770620910025205918983217503584071987775287566188673844123543637762263193795596920425260080044356095949127677307251961838118995084710849787768018791260252845381518827926318333387158760254677435746198415531939463788351791968995627124435295252787871325921689508307901911386056659471168279615250918890645203204963484929799336306875376496249955951103398734081206107276628420215474379708747773426642084928331079553035339084589266707982824592498337994537255170592988697017277483774248656792449731932890347886392443422049814769789176197079439861811225516719581887990721989346442233660817954874267124484742871360960633651741094906975203293344039703422098574857785803965384705282242068856979889099700012307558480137373295699580643908680930842469527126055149117979888806834369983418255163027027184422495412545777185961818942280741624142274660538646662486720609519745048412329168136406296544761965856919516132003241910098859045521046605773279315856808590845225558104780376855967814306830901850962882083740303013116383339945982507787112390084222995016911715314640742706411580248589224048398258651876474865862852645800964645787190384049976325392439568480970453931214278985244577434678505438208070586523163556708289137732604083824942590156195335724687847585233384694526734421981814826776989193764403973352933700698991163990557949181444600988539413165660260313257643230126906507392363756106599489618886946708906488487302151137084131170088464708797137677641945784527050624581691280271791067308694451803261456250921779466925108519364766229359114736254343219531671014412910902627936809939974940225303531610916028239300922302877015574500311659300219007245538293212958647352339943532163265138439264282048216360492814727135077002935309131444110479071503653442483946804951817888753552239840774588877620313139077331490045955749694050579574564111673965095387414797161411201751839411523279192301792363275331027686918121364070925018550875197537162279620857961455362432030802777581310141729405249574853130191733006824617912010569587367439633566392320004386657858238503740708050878844975375612201582187964789741713541827224916996085360129886605200756679886781628293866314716149909474868630345791019851852901737868718396934437666366073104126928509825755329589313049638103046568415840179846116307536644966145263069115215004250745779112250920115997971610635996005372492820326414650913314433132088662150245395593652772614805555020421554669619294156071543843886710379586416259450449437037405863813525009506972512022333370636479277159089036680070797091838558649124539071556429808516626224696857988172753187797682112023315017221919673275807397016055666889226402143064511893487093111154811718796348305298671169012666818191794785277768310143602200551119113104846083631141426872297599232055840091588577297306730531092897740840749057121409860696198142744273813554375359279989918818441741594049225173302667476512754729307878792369083889674920362563703774162405868518079990873190005193962413010396851846953699855718215283968617933247990760117257951003003799140284207414566992879540895874572897719380953970597507509022748515631690494359512333647282804759799427208420625789525547811574491308309218876880898261998507800913291766937681339897976124436709007835503722290709823198806468120234002418294574798105667294677025084070414341901914330229790938126252905414258748325103987953898495314797739538588858992411770756559670099106121463452882384381040954309045453610696134464994410202395891307938615979869590622367887084029620873209669151182863102791021884205566010486990809740224038408451050835156120938741277532473544616969209593852009507058280990681949226215608009418004761212740020405863080129411681869703121769722162392854542251345286832583757936510310522928252041226547448226107823324648781981648954416278587265008382795183302634792143523999263233912747292610260251325714257995932911416649082821541706555481935929003452981427772117032367387377872094755054595795845200657537835055970583075509173433143390618968918261685955028700894833926565899575706061015925825913434893131327450349391699938304717644610239231820755684380454382645206862877290215576859076905585338487482278953199065108675785957004981903252935657630674225280299925316287206309012211101369043347233872618829376722924287805158392359102931392366661695930089715266517437622078017987990885245845054992185420852633742520853105966763751823776087427576388047196327925043448616136232634570949929397249510459957654532730407569913005200840544620378832781024874980921929662129034261428415389771289190651353746771584622176338993027030049037803772831382534057631127086338110162395034457584421173086154081826120933383551091863824051337072448624723425721803653452469727157609128808718042193882828158396628683987357257440164353175147806706927714754546025073833351402384130925754780921540834893653423924096259408001619098375625947662709629584443167315228201854565963407391025187213655896722959376982037500481088355194831985962162562660459354822483787931243734245479400573172797594266487611734149619917970809983796810673096530269987685643201992471350767884210386482530065450083360743523630569548132550995281591409105916105754721226379133080632282174583167502187138632905231045861104632106246852838520980317845652587932104833061882822883929991934454616863190721165117145435078186973116133250980253428750832763820432658953224654555538445684455474827290894147910534107234778668449399666876200835000560317886344786604499134418945077193551374676540715788487487479655184301056730001078973280902969048751482774400250262302893200989659135782831512333952876418074370286047282409354659403946288808172535075472955253350617798672038755519763339392585300652758561402632796387491866107391568300537778135520531965985270561467926583875504568351009911939594183493883201793529493397138968385866327511762511934493709541680811440992009206770660015539388282967309105279536664928132603223201021325392721119879984845927263236472542338349930915797421835331960349373035900485399014665893435744452731932029412498504044454286713753211521026547070813027735994277937006470418565858668893777964462394505988483148547493020511689126574852693442390008286717573764770703339254908615303885962100641951018180588359891634137129371051042969576728791721682477197608874384086711697487268840741189361640169964350954588768126656702511654083387200422793220605825568662032196464632342174304816566029941903057967829023044848924305590270365079406229077809546244041673297274858194645166456903798587560017843595025588568479290734361979710552403988521258807065095074220035843758297953133081465237520821205095453150821532275204397899976521401651753750498765220861794757017109640345360807709000034868821419950978798949244483208109817977223032820615088441078793659926097380489502890197652239780904665616990310169309917827885177620915524692942081849557469622613729272530731296334259100849830352849261263501861579381117342260399198079648967233737756651227225978142428146891560458994906895413505937846180542053204063156330949405894202510944872030351108533409284897380829443566812800942494333933391930360595104746316968324959447818871578737459079090316397234703758769700981428575275589798020786443699548619539030903949532985397310418699130566335938334314517873023191853213381103884490459364150577647925745380120133232646774898280066960230816750764913554877217980325739216928093712047730080849798239349092503964569309481778621066866476042817665701238583256693610325277293019784707315595751262617704999512038997703629002151569616539820866989304048698662601724902766802392514762828611309462790485241893453643607318980768591252054383883068470445932084348999632241668792315214507825805670758416539044499103787476742499310401518915933715446907205476602410889408203137872080265212851861011283815653049817011264630234358010345345880440833007460732451566207929199808719561129442069654547122360043366080249458503973953104793000919819145945068766421216294671385279750499066627627150084461052042161910295857234246110067090770436705266065772032704494219277877349555072210278712055314139290480413226267382778773819472428337853311195522023056633995955228675121264709479527653989925882691206231957843614534258252460872112344526626252509758239152803073783707530131935695402792151938105792856242096858814926729500537455296271364813817683614718125276098913580126623894388309705093431156058561642639590722515542505040767778570204346016145971177533580872705467814017902513382422045744507176020278425103683238434503232943074969290211762665880137553481610584433260253592572184035325522369018903288779876012251930715648677933469189158835790736490417994215202900875331034045077508134012333051377054935993037225984022606952963179508130064966911839554184390387974733433986654362566992798827731297877687343837502011587548720571845796846115886698574914913248208208746386683667928695965927018150492013145952316197271500941181643588790304165033785533765803736803784918485771286777490575396058958180321792465959442453718682981526887560520752780757598464429154809409768835157955827157591124630060365435902021855281479652147494517065279589739775700761716909402463101725039997906798698270027397556527292733851566920640621727341673895806298429039533495910813737297651555460918734209661378912196315491202228459244724681922969141779352843729783836898271885520943972354511411444336131008408692132185794237602696003315688011546662989050628741381600885822521036661005651399922389620736058455389367371718548017997180137809497308990499665913425490503022214732514905325561703919562205771360346356009560228827403554871517831667893238109438317859405109888296608530054076208688703266815942017330990669635042023033656975476629034350924476705150369647591621025003546026217241775240786395069559341004157942230679562163509628662961791040512864384281522525871563977444637826585230270014163872689425836792043667349527695525593225921436405317276332514846074725925122927527239542342695951904139148959436467416384043807316380481195943568633504616880568493551175558226515330887689889712354250217538859132243375602152244018284611157879985181586796106257902473392363248331980335347144699858658108702421315270231611791112349354832603187511267997828682160902927474493388737700493879478283311019478199406890247322476814674563695506848160940155233139753913120757500267645790345277812019998257187453548978730152344519863236602300636214729150220378207921349504150886461667524174704033247411659227109863159283751261411890651513147686494567727069721190034615652362361722425606875357990912463862773615137764601952576805339122764045795658680204626999094934642544454884296745625199945131762502542992382166834274382650492522914091573344029730318425661341185604309606228916118722421107735953537687827127521225773905199374966690050139204771356176440504309662842529887596868960201932842733065301320446765633455871849832524121392297421524107308318321262527064095398795052540739575530365029328124131826909911653423869400470686502879496319697312545604900505246744195445352040455052380385068657377056179955506659047305407819309372759777150365599326950169546334341407443623734242797673861815637302742881792950669061389279555246228156751351746342692037222444910125761540353516878009496504555678349915645145406460260045094665896878643500119763808959741030313123441956606028522496018179280098116200047415744783458562470159990172258079604566037432269632105316302178135853937638325687807345315821030949906561567408690427222652860301793743378042415213572675708014621642161006892721113087346894236948709370302611079563051724500301781653200371085717899521696144241160698316013371217639717560178630670259651457023513505156004282937775532894769181327603840271007837380777185767151292316853567198476504665076874932313153876502353913891399482278047345930391252583473781150290886701417230541758627987156337395166019530016190103861629850224654904380823784066003689898502826965561426223590219559928351722402511125056093570708443764175445465645640251629549789198961602199113952430171323925602026182135124587864745593925198710968772234036559062505476665244815523601842791365189827385011959250428630815029093363682362842586034003566956103742194209640221526824505456431905054113107036911847006802280674134997482097023170282775230008344716112416776354930573278003667152985075999318116709676048357287422543864861967936197953390680649936443149547908293486171424370172785301904947345164477043075105349365852315691628693701376456164493428799034442638350295411522041948935558825604948721032600580928001207893213725746376801903006248737364677153070131610942900891201580527289039101393468943025724651069901627696863784305505281747242137426336142557935122613008060124830330377051362634293521025587762305301911323808860758282940787676234067424053296952044800778624706138177831219692196816235189286340549533305470532741508755920973125364751698330747799457657360240473458235632860293264452467311182108336303209308365973710323027696415799623517897742652450615031938024267133935527400102653279868923651384875859689908190455593961380811342304823250413351682798189681398052758865965455864345293856300689392239971564343147318684499856763052167682976688493825151724419769125856391771062896429286166701816329367708740943918764734457102640317955408848489707045623007473891565633501816037249162341578459719788387549774539075832409822752998026210586448778910825706110462724480966143241967625179876098430849958272138779492862624304519000681657011265506693166095990648937006044305058552409062272615893129227499513487355532539301003234050288351404154294249703011364124559591956147631791091720400294359091745527653684646403328756471037126810555729558587949255574780182314477535219204744831138181940630063778315408248432672214010632036367783844740653314048636125253192275443864007625474684539733304209709559982475343330053637079707419001516274602767216422627606762286910892640065741461917164879328689246419970225252817819537355370925902797493926287279723901605359843520378349626863647240300271066096073805238697670095850408770110049231856844870796407888702441590414438115449248703283790189555049298276620069174537917686058995539186783074779297728303984009194754387597205186492223388979328651989013259029705632821830058742648623286170665927583805094921637482491078510982454015348536752246736658505199031988137869972361445082292365532070704567007940367312319751226545457846740046466339999241486775515339403085756238570304768495650737656957500037213766017368003875833614402060154920516006544614341857040499860022007098098785023500496194783191679617848962106517925624839656047696095133108133503146978541961407870678360313164101253068414699409269578793985933406944650970627911239198824179771439662827870703309805790576865716455805076935024516989715685188344672105125630227712070241059291700187941063094654012814890124468155638201547775289946130605356641168474855636745883932742309196176567550230179296355272083132036799397557447328170210627299912243242764490038281795816044579488008460631024941262532707369952669848286738902908829922013498869280300032048761780228487467969415612543860879891618509743358108960168902405090605813435784448708966434826409784128315196258197944316888921501570620350341352501654665980095700753697534097751412992415215474246685990519654368870922591182490116552391962208671820918465353386008133228808722187295382854641659940779854158082485338720092867007948627504310631316775531284754996370700979234992471920191462438535671839057721843626407703353992202688839841807725167923627348780604613880672535935192540910950890074473434639774002494971149096746574515419391784572593431835617581308808375427576663093244133222743516824727677267555786494721108829890547602789255302981887764279945170162096395199573370513470641370613609881687805855580083720797731141139479927396045203776848695591398555875619099836154425617396353143931693668639801425969132091835269248385206565823560005950482749188291246605441299588517677334083356666079244241237868133101723821746051794338628946675762326783163879540026515898629138834997034292236821879958433832705999105698554959193853292231370581931075395899992571013379639920663080268625787439977358700026836270350244264719033187428997035901974132868278319377143722358340289161011796340434708799980921377959152892233753310934512844015320048066433507911586372760240115300638711964735983928757168925797765797215933368697877379698338466798403902246598848411805305741192723846881056297495962606280316549594738967382518073779060971725594570639549025083632770101389772433518614483751963376500742124565691971821208878535256292726133245686237785697343794672732788702018828967449228434229114950442704237045686204304930845227039882645824031128717478457868282347963074211392402490743310646802074557569685068063001071923870920666663421964613324040962260793208609221997395817523169627136037581582729486377482282557668725541583976605453571972786514083319998631616290269591370498250259591329628045632931592517833905485732012166644960791465009499908729063872707284477232961671141660201327800474659257685351059779325904566341141420997886169354402397876173008355482298197598422016440305215934008636432465704635715179399835436290371114803174935001060150441898151901451706645789998357444687203697007224969547504751735213352948673613904143507448998068745085961672560953923526311315459645969529651829964157756976305251527287540431058522797002334237039550421927680814942400739391074329567415321483729517615494056002167288462315009178236250716460920924565514208048019250280547881024072339354824581497138614196421159722820405417382456394085518105664505246022864603283172694180012614554117267264050079994480678566045114345176017402728938378200674819408707249823605806390346982050534171401077651136384364016009531668514413130028671694633825848452797084670002015841783833896785360643513222672069421365814905107320201634620261588767624377729148020925145219534617768451964896689219253281455888334329078965618650404868373680043094362700104861518989311226736935015905906609393331769067208878663543285998355828839432133572498892277042519121452637199583071552767178559129523891853048215140077145764146562320726892187237247885766195292829801297930893090696491058114503162899438138331327314422229590019344749669880333961207591301057244169976275282238000409136123846277359957845881414653544136776965399109513211956559503914210446613817690565107943834940392233891089073473293215004751466276384348082803404582158103373421744308488993112027515604720894389077014456747915052089561242174180081898507043782030912398719039245272093773740272119788388225384630722386081137308498957104360459363738479281899[...]

p.ndigits()

9808358

is_prime(p)

prime_pi(3000000)

216816

︠fd19ed86-1530-4c2e-8d46-db1d457d8cf7︠
Li?

File: /projects/sage/sage-6.9/local/lib/python2.7/site-packages/sage/functions/exp_integral.py
Signature : Li(self, coerce=True, hold=False, dont_call_method_on_arg=False, *args)
Docstring :
The offset logarithmic integral, or Eulerian logarithmic integral,
operatorname{Li}(x) is defined by

   operatorname{Li}(x) = int_2^x frac{dt}{ln(t)} =
   operatorname{li}(x)-operatorname{li}(2)

for x >= 2.

The offset logarithmic integral should also not be confused with
the polylogarithm (also denoted by operatorname{Li}(x) ), which is
implemented as "sage.functions.log.Function_polylog".

operatorname{Li}(x) is identical to operatorname{li}(x) except
that the lower limit of integration is 2 rather than 0 to avoid the
singularity at x = 1 of

   frac{1}{ln(t)}

See "Function_log_integral" for details of operatorname{li}(x).
Thus operatorname{Li}(x) can also be represented by

   operatorname{Li}(x) = operatorname{li}(x)-operatorname{li}(2)

So we have:

   sage: li(4.5)-li(2.0)-Li(4.5)
   0.000000000000000

operatorname{Li}(x) is extended to complex arguments z by analytic
continuation (see [AS] 5.1.3):

   sage: Li(6.6+5.4*I)
   3.97032201503632 + 2.62311237593572*I

The function operatorname{Li} is an approximation for the number
of primes up to x. In fact, the famous Riemann Hypothesis is

   |pi(x) - operatorname{Li}(x)| <= sqrt{x} log(x).

For "small" x, operatorname{Li}(x) is always slightly bigger than
pi(x). However it is a theorem that there are very large values of
x (e.g., around 10^{316}), such that exists x: pi(x) >
operatorname{Li}(x).  See "A new bound for the smallest x with
pi(x) > operatorname{li}(x)", Bays and Hudson, Mathematics of
Computation, 69 (2000) 1285-1296.

Note: Definite integration returns a part symbolic and part
  numerical result.  This is because when Li(x) is evaluated it is
  passed as li(x)-li(2).

EXAMPLES:

Numerical evaluation for real and complex arguments is handled
using mpmath:

   sage: N(log_integral_offset(3))
   1.11842481454970
   sage: N(log_integral_offset(3), digits=30)
   1.11842481454969918803233347815
   sage: log_integral_offset(ComplexField(100)(3+I))
   1.2428254968641898308632562019 + 0.87232935488528370139883806779*I
   sage: log_integral_offset(2)
   0
   sage: for n in range(1,7):
   ....:  print '%-10s%-10s%-20s'%(10^n, prime_pi(10^n), N(Li(10^n)))
   10        4         5.12043572466980
   100       25        29.0809778039621
   1000      168       176.564494210035
   10000     1229      1245.09205211927
   100000    9592      9628.76383727068
   1000000   78498     78626.5039956821

Here is a test from the mpmath documentation. There are
1,925,320,391,606,803,968,923 prime numbers less than 1e23. The
value of "log_integral_offset(1e23)" is very close to this:

   sage: log_integral_offset(1e23)
   1.92532039161405e21

Symbolic derivatives are handled by Sage and integration by Maxima:

   sage: x = var('x')
   sage: f = log_integral_offset(x)
   sage: f.diff(x)
   1/log(x)
   sage: f.integrate(x)
   -x*log_integral(2) + x*log_integral(x) - Ei(2*log(x))
   sage: Li(x).integrate(x,2.0,4.5)
   -2.5*log_integral(2) + 5.799321147411334
   sage: N(f.integrate(x,2.0,3.0))   # abs tol 1e-15
   0.601621785860587

ALGORITHM:

Numerical evaluation is handled using mpmath, but symbolics are
handled by Sage and Maxima.

REFERENCES:

* http://en.wikipedia.org/wiki/Logarithmic_integral_function

* mpmath documentation: logarithmic-integral

P = plot(Li, 2,10000, color="purple")

P.show()

Q = plot(prime_pi, 2,10000, color="black")

Q.show()

show(P+Q)

sage: R = Integers(10)
sage: a = R(3)                 # create an element of Z/10Z
sage: a.multiplicative_order()

4

[a^i for i in range(15)]

[1, 3, 9, 7, 1, 3, 9, 7, 1, 3, 9, 7, 1, 3, 9]

euler_phi(2007)

1332

CRT(2,3, 3, 5)

8

CRT_list([2,3,2], [3,5,7])

23

#The xgcd(a,b) command computes the greatest common divisor g of a and b along with x, y such that ax + by = g.
xgcd(5,7)

(1, 3, -2)

sage: a = Mod(17, 61)
sage: a^(-1)

The Sage session not running; please retry later.

#computes 7^91 mod 100
Mod(7,100)^91

43

sage: n = 95468093486093450983409583409850934850938459083
sage: Mod(2,n)^(n-1)

34173444139265553870830266378598407069248687241

factor(n)

1610302526747 * 59285812386415488446397191791023889

is_prime(n)

False

number_of_divisors(4)

3

prime_divisors(12)

[2, 3]

quadratic_residues(5)

[0, 1, 4]

quadratic_residues(12)

[0, 1, 4, 9]

quadratic_residues(20)

[0, 1, 4, 5, 9, 16]

list(squarefree_divisors(12))

[1, 2, 3, 6]

list(squarefree_divisors(100))

[1, 2, 5, 10]

len(list(squarefree_divisors(1000000)))

4

sage: R = Integers(97)
sage: a = R(51)
sage: a^2006

12

R = Integers(10)
a = R(5)
2*a

0

R = Integers(10)

legendre_symbol(69,389)

1

legendre_symbol(3,389)

-1

legendre_symbol(389,3)

-1

legendre_symbol(23,389)

-1

legendre_symbol(2,41)

1

︠18328bf7-3d29-40c6-9020-d70d6aa587f4︠
︠9e75df76-0a31-4f2a-b9ed-0e5306eb940e︠
︠29ece7f0-6f80-4c5a-923f-c9dea7830a53s︠
)

Error in lines 0-1 Traceback (most recent call last): File "/projects/sage/sage-6.9/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "<string>", line 1 ) ^ SyntaxError: invalid syntax

quadratic_residues(41)

[0, 1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 21, 23, 25, 31, 32, 33, 36, 37, 39, 40]

for x in range(41):
    if x^2%41 == 2:
        print x

17 24

for x in range(17):
    if x^2%17 == 2:
        print x

6 11

for x in range(57):
    if x^2%73 == 2:
        print x

32 41