defmodule Caustic.Utils do
  use Bitwise

  @moduledoc """
  A collection of useful methods.
  """
  
  @base58_table "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
  @base_prefixes %{2 => "0b", 16 => "0x"}
  @base58_version %{
    address: <<0x00>>, # base58 starts with 1
    address_p2sh: <<0x05>>, # base58 starts with 3
    address_testnet: <<0x6f>>, # base58 starts with m/n
    private_key_wif: <<0x80>>, # base58 starts with 5 for uncompressed and K/L for compressed
    private_key_bip38_encrypted: <<0x0142::size(16)>>, # base58 starts with 6P
    public_key_bit32_extended: <<0x0488b21e::size(32)>> # base58 starts with xpub
  }
  
  # https://oeis.org/A000043
  # https://en.wikipedia.org/wiki/Mersenne_prime
  # Primes p such that 2^p - 1 is prime.
  @mersenne_exponents [
    2,        3,        5,        7,        13,       17,       19,      31,      61,       89,
    107,      127,      521,      607,      1279,     2203,     2281,    3217,    4253,     4423,
    9689,     9941,     11213,    19937,    21701,    23209,    44497,   86243,   110503,   132049,
    216091,   756839,   859433,   1257787,  1398269,  2976221,  3021377, 6972593, 13466917, 20996011,
    24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609]
  
  # https://oeis.org/A000668
  # https://en.wikipedia.org/wiki/Mersenne_prime
  # Primes of the form 2^p - 1 where p is a prime.
  @mersenne_primes [
    3, 7, 31, 127, 8191, 131071, 524287, 2147483647,
    2305843009213693951, 618970019642690137449562111,
    162259276829213363391578010288127,
    170141183460469231731687303715884105727,
    6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151,
    531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127,
    10407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087,
    1475979915214180235084898622737381736312066145333169775147771216478570297878078949377407337049389289382748507531496480477281264838760259191814463365330269540496961201113430156902396093989090226259326935025281409614983499388222831448598601834318536230923772641390209490231836446899608210795482963763094236630945410832793769905399982457186322944729636418890623372171723742105636440368218459649632948538696905872650486914434637457507280441823676813517852099348660847172579408422316678097670224011990280170474894487426924742108823536808485072502240519452587542875349976558572670229633962575212637477897785501552646522609988869914013540483809865681250419497686697771007,
    446087557183758429571151706402101809886208632412859901111991219963404685792820473369112545269003989026153245931124316702395758705693679364790903497461147071065254193353938124978226307947312410798874869040070279328428810311754844108094878252494866760969586998128982645877596028979171536962503068429617331702184750324583009171832104916050157628886606372145501702225925125224076829605427173573964812995250569412480720738476855293681666712844831190877620606786663862190240118570736831901886479225810414714078935386562497968178729127629594924411960961386713946279899275006954917139758796061223803393537381034666494402951052059047968693255388647930440925104186817009640171764133172418132836351,
    259117086013202627776246767922441530941818887553125427303974923161874019266586362086201209516800483406550695241733194177441689509238807017410377709597512042313066624082916353517952311186154862265604547691127595848775610568757931191017711408826252153849035830401185072116424747461823031471398340229288074545677907941037288235820705892351068433882986888616658650280927692080339605869308790500409503709875902119018371991620994002568935113136548829739112656797303241986517250116412703509705427773477972349821676443446668383119322540099648994051790241624056519054483690809616061625743042361721863339415852426431208737266591962061753535748892894599629195183082621860853400937932839420261866586142503251450773096274235376822938649407127700846077124211823080804139298087057504713825264571448379371125032081826126566649084251699453951887789613650248405739378594599444335231188280123660406262468609212150349937584782292237144339628858485938215738821232393687046160677362909315071,
    190797007524439073807468042969529173669356994749940177394741882673528979787005053706368049835514900244303495954950709725762186311224148828811920216904542206960744666169364221195289538436845390250168663932838805192055137154390912666527533007309292687539092257043362517857366624699975402375462954490293259233303137330643531556539739921926201438606439020075174723029056838272505051571967594608350063404495977660656269020823960825567012344189908927956646011998057988548630107637380993519826582389781888135705408653045219655801758081251164080554609057468028203308718724654081055323215860189611391296030471108443146745671967766308925858547271507311563765171008318248647110097614890313562856541784154881743146033909602737947385055355960331855614540900081456378659068370317267696980001187750995491090350108417050917991562167972281070161305972518044872048331306383715094854938415738549894606070722584737978176686422134354526989443028353644037187375385397838259511833166416134323695660367676897722287918773420968982326089026150031515424165462111337527431154890666327374921446276833564519776797633875503548665093914556482031482248883127023777039667707976559857333357013727342079099064400455741830654320379350833236245819348824064783585692924881021978332974949906122664421376034687815350484991,
    285542542228279613901563566102164008326164238644702889199247456602284400390600653875954571505539843239754513915896150297878399377056071435169747221107988791198200988477531339214282772016059009904586686254989084815735422480409022344297588352526004383890632616124076317387416881148592486188361873904175783145696016919574390765598280188599035578448591077683677175520434074287726578006266759615970759521327828555662781678385691581844436444812511562428136742490459363212810180276096088111401003377570363545725120924073646921576797146199387619296560302680261790118132925012323046444438622308877924609373773012481681672424493674474488537770155783006880852648161513067144814790288366664062257274665275787127374649231096375001170901890786263324619578795731425693805073056119677580338084333381987500902968831935913095269821311141322393356490178488728982288156282600813831296143663845945431144043753821542871277745606447858564159213328443580206422714694913091762716447041689678070096773590429808909616750452927258000843500344831628297089902728649981994387647234574276263729694848304750917174186181130688518792748622612293341368928056634384466646326572476167275660839105650528975713899320211121495795311427946254553305387067821067601768750977866100460014602138408448021225053689054793742003095722096732954750721718115531871310231057902608580607,
    4782202788054612029528392986600059097414971724022365008513345109918378950942662970278927686112707894586824720981524256319306585052676834087480834429433264797425893247623688331021633208954847354805799943341309825989013743806187109581043148680813778321530496715601563282624414040398143207622036272190408590790537203475256105564071579263867875240985573356522656108542128577321057879052328865035355873615679363655889925711574420153832091752422843046918811427400662135559303516853703976812686385750376227787949580582081831261725701003498206512329872677233489510953469375683037038373999696771585788905639115522613405495707184524158219208223766442059014593330657009722153962376853423770486138578089775621301167811299166407361746606697808186757966914671246073712904200588408923186387737887675292886953797066980967406053530122853539036965490224784924649007954898678503314655546475504501686187354866964374552614120640782949622452027788962138602665933147687696322089504278791624651519312327831756553779377194524673395819281486668576384019590720179413349582970319393884388810494546040342087536563628332152073181614300721769371426238517540520845214665313301183551962591849558938499025348780376716477073930634436840084468255937443451690315999349137664638968972614199015304906547819056227171224947070739716300953775743441307920501863532234466545645695774331885044978250148663467372130392099894852145190998232878772486650513010816769902892518719250066947215706536216248696240569256865554296221552211560427778662545936998801070186162601476474293459830183651273363462732675883060701410359254829149774339297173680765610959599911309189788238350131635672661435969218239977196933874395403996623675580528211207136396370858056051160781770985452576988032333812939272752101944629527490313835551985197095928885236415301789218675141014541203096191270934369039522098280317668942061325572349643638403056487349290884223786292887472231219032385281034091824306618947740727265524284893304474861454942076799041739447165838281671410435831206790501914527326287370339974707206016882562827404270170322606727980343479326425730091839813077719322455394763960606588214326603156141490740557698055166263044447583756711516490181193442236859424151843795389335765432129944054855345155859273424561825146813714720606287781021240923708021492298349635179527270302962970156927686511635050080407282674252362644695710769768866137302789313609674382719017385508484663373476120843567983065059558072935110637544240807350667082987233779768874938983584523095638996120616318634391967112086464384649470963230072729200912586147267999762496709852769503535733924416202657720741248683592202828983311140833923302433917797976990311425843619350936754483811194408812763388084204451804912454383884180800945275626668057628954763384641305107753773247082495804533355717481965025070819730466422826105697510564289798951182192885976352229053898948737614642139910911535864505818992696826225754111,
    34608828249085121524296039576741331672262866890023854779048928344500622080983411446436437554415370753366448674763505018641470709332373970608376690404229265789647993709760358469552319045484910050304149809818540283507159683562232941968059762281334544739720849260904855192770626054911793590389060795981163838721432994278763633095377438194844866471124967685798888172212033000821469684464956146997194126921284336206463313859537577200462442029064681326087558257488470489384243989270236884978643063093004422939603370010546595386302009073043944482202559097406700597330570799507832963130938739885080198416258635194522913042562936679859587495721031173747796418895060701941717506001937152430032363631934265798516236047451209089864707430780362298307038193445486493756647991804258775574973833903315735082891029392359352758617185019942554834671861074548772439880729606244911940066680112823824095816458261761861746604034802056466823143718255492784779380991749580255263323326536457743894150848953969902818530057870876229329803338285735419228259022169602665532210834789602051686546011466737981306056247480055071718250333737502267307344178512950738594330684340802698228963986562732597175372087295649072830289749771358330867951508710859216743218522918811670637448496498549094430541277444079407989539857469452772132166580885754360477408842913327292948696897496141614919739845432835894324473601387609643750514699215032683744527071718684091832170948369396280061184593746143589068811190253101873595319156107319196071150598488070027088705842749605203063194191166922106176157609367241948160625989032127984748081075324382632093913796444665700601391278360323002267434295194325607280661260119378719405151497555187549252134264394645963853964913309697776533329401822158003182889278072368602128982710306618115118964131893657845400296860012420391376964670183983594954112484565597312460737798777092071706710824503707457220155015899591766244957768006802482976673920392995410164224776445671222149803657927708412925555542817045572430846389988129960519227313987291200902060882060733762075892299473666405897427035811786879875694315078654420055603469625309399653955932310466430039146465805452965014040019423897552675534768248624631951431493188170905972588780111850281190559073677771187432814088678674286302108275149258477101296451833651979717375170900505673645964696355331369819296000267389583289299126738345726980325998955997501176664201042888546085699446442834195232948787488410595750197438786353119204210855804692460582533832967771946911459901921324984968810021189968284941331573164056304725480868921823442538199590383852412786840833479611419970101792978355653650755329138298654246225346827207503606740745956958127383748717825918527473164970582095181312905519242710280573023145554793628499010509296055849712377978984921839997037415897674154830708629145484724536724572622450131479992681684310464449439022250504859250834761894788889552527898400988196200014868575640233136509145628127191354858275083907891469979019426224883789463551,
    2814112013697373133393152975842584191818662382013600787892419349345515176682276313810715094745633257074198789308535071537342445016418881801789390548709414391857257571565758706478418356747070674633497188053050875416821624325680555826071110691946607460873056965360830571590242774934226866183966309185433462514537484258655982386235046029227507801410907163348439547781093397260096909677091843944555754221115477343760206979650067087884993478012977277878532807432236554020931571802310429923167588432457036104110850960439769038450365514022349625383665751207169661697352732236111926846454751701734527011379148175107820821297628946795631098960767492250494834254073334414121627833939461539212528932010726136689293688815665491671395174710452663709175753603774156855766515313827613727281696692633529666363787286539769941609107777183593336002680124517633451490439598324823836457251219406391432635639225604556042396004307799361927379900586400420763092320813392262492942076312933268033818471555255820639308889948665570202403815856313578949779767046261845327956725767289205262311752014786247813331834015084475386760526612217340579721237414485803725355463022009536301008145867524704604618862039093555206195328240951895107040793284825095462530151872823997171764140663315804309008611942578380931064748991594407476328437785848825423921170614938294029483257162979299388940695877375448948081108345293394327808452729789834135140193912419661799488795210328238112742218700634541149743657287232843426369348804878993471962403393967857676150371600196650252168250117793178488012000505422821362550520509209724459895852366827477851619190503254853115029403132178989005195751194301340277282730390683651120587895060198753121882187788657024007291784186518589977788510306743945896108645258766415692825664174470616153305144852273884549635059255410606458427323864109506687636314447514269094932953219924212594695157655009158521173420923275882063327625408617963032962033572563553604056097832111547535908988433816919747615817161606620557307000377194730013431815560750159027842164901422544571224546936793234970894954668425436412347785376194310030139080568383420772628618722646109707506566928102800033961704343991962002059794565527774913883237756792720065543768640792177441559278272350823092843683534396679150229676101834243787820420087274028617212684576388733605769491224109866592577360666241467280158988605523486345880882227855505706309276349415034547677180618296352866263005509222254318459768194126727603047460344175581029298320171226355234439676816309919127574206334807719021875413891580871529049187829308412133400910419756313021540478436604178446757738998632083586207992234085162634375406771169707323213988284943779122171985953605897902291781768286548287878180415060635460047164104095483777201737468873324068550430695826210304316336385311384093490021332372463463373977427405896673827544203128574874581960335232005637229319592369288171375276702260450911735069504025016667755214932073643654199488477010363909372005757899989580775775126621113057905717449417222016070530243916116705990451304256206318289297738303095152430549772239514964821601838628861446301936017710546777503109263030994747397618576207373447725441427135362428360863669327157635983045447971816718801639869547525146305655571843717916875669140320724978568586718527586602439602335283513944980064327030278104224144971883680541689784796267391476087696392191,
    43154247973881626480552355163379198390539350432267115051652505414033306801376580911304513629318584665545269938257648835317902217334584413909528269154609168019007875343741396296801920114486480902661414318443276980300066728104984095451588176077132969843762134621790396391341285205627619600513106646376648615994236675486537480241964350295935168662363909047948347692313978301377820785712419054474332844529183172973242310888265081321626469451077707812282829444775022680488057820028764659399164766265200900561495800344054353690389862894061792872011120833614808447482913547328367277879565648307846909116945866230169702401260240187028746650033445774570315431292996025187780790119375902863171084149642473378986267503308961374905766340905289572290016038000571630875191373979555047468154333253474991046248132504516341796551470575481459200859472614836213875557116864445789750886277996487304308450484223420629266518556024339339190844368921018424844677042727664601852914925277280922697538426770257333928954401205465895610347658855386633902546289962132643282425748035786233580608154696546932563833327670769899439774888526687278527451002963059146963875715425735534475979734463100678367393327402149930968778296741391514599602374213629898720611431410402147238998090962818915890645693934483330994169632295877995848993366747014871763494805549996163051541225403465297007721146231355704081493098663065733677191172853987095748167816256084212823380168625334586431254034670806135273543270714478876861861983320777280644806691125713197262581763151313596429547763576367837019349835178462144294960757190918054625114143666384189433852576452289347652454631535740468786228945885654608562058042468987372436921445092315377698407168198376538237748614196207041548106379365123192817999006621766467167113471632715481795877005382694393400403061700457691135349187874888923429349340145170571716181125795888889277495426977149914549623916394014822985025331651511431278802009056808456506818877266609831636883884905621822262933986548645669080672191704740408891349835685662428063231198520436826329415290752972798343429446509992206368781367154091702655772727391329424277529349082600585884766523150957417077831910016168475685658673192860882070179760307269849987354836042371734660257694347235506301744118874141292438958141549100609752216882230887611431996472330842380137110927449483557815037586849644585749917772869926744218369621137675101083278543794081749094091043084096774144708436324279476892056200427227961638669149805489831121244676399931955371484012886360748706479568669048574782855217054740113945929622177502575565811067452201448981991968635965361551681273982740760138899638820318776303668762730157584640042798880691862640268612686180883874939573818125022279689930267446255773959542469831637863000171279227151406034129902181570659650532600775823677398182129087394449859182749999007223592423334567850671186568839186747704960016277540625331440619019129983789914712515365200336057993508601678807687568562377857095255541304902927192220184172502357124449911870210642694565061384919373474324503966267799038402386781686809962015879090586549423504699190743519551043722544515740967829084336025938225780730880273855261551972044075620326780624448803490998232161231687794715613405793249545509528052518010123087258778974115817048245588971438596754408081313438375502988726739523375296641615501406091607983229239827240614783252892479716519936989519187808681221191641747710902480633491091704827441228281186632445907145787138351234842261380074621914004818152386666043133344875067903582838283562688083236575482068479639546383819532174522502682372441363275765875609119783653298312066708217149316773564340379289724393986744139891855416612295739356668612658271234696438377122838998040199739078061443675415671078463404673702403777653478173367084844734702056866636158138003692253382209909466469591930161626097920508742175670306505139542860750806159835357541032147095084278461056701367739794932024202998707731017692582046210702212514120429322530431789616267047776115123597935404147084870985465426502772057300900333847905334250604119503030001704002887892941404603345869926367501355094942750552591581639980523190679610784993580896683299297681262442314008657033421868094551740506448829039207316711307695131892296593509018623094810557519560305240787163809219164433754514863301000915916985856242176563624771328981678548246297376249530251360363412768366456175077031977457534912806433176539995994343308118470147158712816149394421276614228262909950055746981053206610001560295784656616193252269412026831159508949671513845195883217147982748879261851417819979034417285598607727220866677680426090308754823803345446566305619241308374452754668143015487710877728011086004325892262259413968285283497045571062757701421761565262725153407407625405149931989494459106414660534305378576709862520049864880961144869258603473714363659194013962706366851389299692869491805172556818508298824954954815796063169517658741420159798754273428026723452481263569157307213153739781041627653715078598504154797287663122946711348158529418816432825044466692781137474494898385064375787507376496345148625306383391555145690087891955315994462944493235248817599907119135755933382121706191477185054936632211157222920331148502487563303118018805685073569841580518118710778653953571296014372940865270407021924383167290323231567912289419486240594039074452321678019381871219092155460768444573578559513613304242206151356457513937270939009707237827101245853837678338161023397586854894230696091540249987907453461311923963852950754758058205625956600817743007191746812655955021747670922460866747744520875607859062334750627098328593480067789456169602494392813763495657599847485773553990957557313200809040830036446492219409934096948730547494301216165686750735749555882340303989874672975455060957736921559195480815514035915707129930057027117286252843197413312307617886797506784260195436760305990340708481464607278955495487742140753570621217198252192978869786916734625618430175454903864111585429504569920905636741539030968041471,
    44867916611904333479495141036159177872720902372938861301036480447512785609158053637162018395920183108689149613973035533621134551674715287880007134345347194681025732056939825423723521750452980127215084299527266875706892007262798468825185681532142985720637290299313726344463257416449344509835102458816789016394945893696705168502436180232259551672603295389186364437045681350697590862198047118901225352609650331560624641680529360950276322519541199378781611887950368067065467094570602703933944508795918017973611326798274338403964825448745270434393258865935311826270281291301767537362073560471706796018086986188192305477308263143033689309402401116023184218739861793173381674293624039080146446533167893142403441626243986354829868152963856856097613981370008545290902178852760181267516916666189196652889272405457548015727583223936389690623948268629738406595342536881770621194098884299042222510205198907427651269590866489020849331593183544730378438673619905441075619665362094087700417583472204239335761771260615063239687136058218014855376128809648109025328444692060981149171853122623214490315199270347679840250650446624361158632712607371820441076129040576076156413981966443384174935945557589269550551384444249641738589326431062350244259749888495427561113138125373546749571089212977055534105306317668036525450115619994704703080975001831039096328170193148671686659220369588362291591980963840251182084839045643052580945876198697254235294718583716788165976228557375284260972377346244685323620326927812128869122804644917707943186384476057711810558228653120572801809938250702311789320142979213175068746598525343177694757992501015403459055756096150131796369342571712916973547166474698856592132612717244249685861542410597610354729550125380584497109056463991926448357223209008827764713220228439775757230755516658614028292960947522709456751199752268424383084190316769975828969408161512929731166188774631973942613003505328030528435929861943028814647224393409604332129915709479716480001751152901047730022099226496393622633345405009361146955156338963448113785646130979933903537929751619768669550563002423706161236691536299577305442116055910462682405728304933022695634876033547918117176704431651372729753611485207957283097607765933169252913861287726833830000755907168496373643201886627226059186824987046158950280121480310106220821760865120562920439756658081153617726352709131801387158672559847396101178548655217308890158788609324326427919178121708326042669857675282709609677929532780738060001705557411238564945972873592110131239116174462947424279402757853073650206058072089139080813381552120237889176959032725532187981806390188976611966923383780080589571180304127953763426872458894003176440733448130784320760858250357720163697308151884697269173048039142351116460009341135465682559795451407065757164712682892684340399927996841540378943787439234382545562253973300003977291497945580368468642313784723553952911754115108385290054865563784523161325911184338403975092561182541488447059744171236348865292897919507096247432485742758096709852132553243687088002636637356883647209281384466468348661473539477676114713952390574283871138643608927689646270265436227072361361556969326026972555137795806131512078396392381117163021488319719122953967241849650035686516897636532829829413559438271078909648012546818155830670649731025924561052079518365511691315910359549578098542021850858860195694976630351366074278129451101792937644085504395275589852388064138602439346909569031381270272833205694814223411334423565977453887542395353485301546284835327702006873689327611630437966491140077951840154972590243416512380587609900111470825767310676939441942826834427612997756892340669203408743659224466633723212596650417249730825215118303577011272768581293371366148392778532335573122542905472394542069919985611732624482347646980930805586007081976261003097963198812882873782621377463926668786498204922447802136607398552526766227205124310008056632919363553194966717056709446690809053625020657218419836547624618595375352039018705449062959037038925284556675116361168237279922207920794703117075921951295707710873733317931433110923531405719416365240907518118794096775462324423434250371711420947553571555908465792580645089870615111865933553809003552706994499748706917899889082891225016257753453229705906397483096836459677640750701051127649136815511445021677568414826304009394300853762240103073543616073297109679097852591173721376034038403903797326084264850909622924265141840684883798695123898530601713627917934581206083528373369371952855787986368194089909153037760311683730584329384267492189510884229753903906808988993523259437606901944039838823315225488711871355530334671879703287493612171018890720047791219983006575690550227543246901734749051876793980240930546447655515405860615566182339568500526080685358056916078877218441535928716267560418132595102517522928981353833074067246933111570873295331815501725771241383698605105802286768924861382741652271179538064625778814288737402101220075694269814240934893379113612806306410045157701609671517543787442511524203121293023260598375610136932287924468473569626893292863959506611559181514200293625478634965230187600993204860736747921056014359652196606989325320755082356901630669240688685505174445515739151017185696401582807173431580481627122423292641208991071222953038343766541925054971737959169869292375645057151727543470106206531135735154136115144300015873080448570355596137321380062748881332031472142823024949510022409370177712994235289702790490255826941441774321618772576455298250619988354955614763200793811728997204477597638052792510878225745663494703701392574625552528908681553926116252158243953964293657171414581341823547346468074289772645946104841180801333621512150598625594195401601933368973292090945435953301875202828322848138663871822530516790587144451339179411203328134884327892252621182901800244630979609876813374281202935998128401633959108387881070976339195584757402099414224321539543476019604874975720230127703172732861447718691961098975942332752633167063512960112700154075209382155551695503282689329429789346503176351007528609841743736084042408094015850910964618482805649640269394165006760210370817982850495571836159005709917919149733735278914364020463842602726375487527643414975692020200079346255666615166515258291939313433912222614621242014153365037286833662921186290423547789663783785467893012638041082143785487398866487992341179948504338667781255945413472465246231194881401316071628427281713042247869185631200192333698966933544361629391311041730956501694662754558875644345191269279600693551809271956450264294092857410828353511882751,
  ]
  
  @doc """
  Encodes an integer codepoint 0 <= `n` <= 63 to its MIME Base64 character.
  
  ## Examples
    
      iex> Caustic.Utils.base64_encode_char(0)
      "A"
      iex> Caustic.Utils.base64_encode_char(5)
      "F"
      iex> Caustic.Utils.base64_encode_char(26)
      "a"
      iex> Caustic.Utils.base64_encode_char(31)
      "f"
      iex> Caustic.Utils.base64_encode_char(52)
      "0"
      iex> Caustic.Utils.base64_encode_char(57)
      "5"
      iex> Caustic.Utils.base64_encode_char(62)
      "+"
      iex> Caustic.Utils.base64_encode_char(63)
      "/"
  """
  def base64_encode_char(n) when is_integer(n) and 0 <= n and n <= 25 do
    ascii = ?A + n
    << ascii >>
  end

  def base64_encode_char(n) when is_integer(n) and 26 <= n and n <= 51 do
    ascii = ?a + n - 26
    << ascii >>
  end

  def base64_encode_char(n) when is_integer(n) and 52 <= n and n <= 61 do
    ascii = ?0 + n - 52
    << ascii >>
  end

  def base64_encode_char(n) when n === 62, do: "+"
  def base64_encode_char(n) when n === 63, do: "/"

  @doc """
  Gets the character code of a MIME base64 digit.
  
  ## Examples
    
      iex> Caustic.Utils.base64_decode_char("A")
      0
      iex> Caustic.Utils.base64_decode_char("F")
      5
      iex> Caustic.Utils.base64_decode_char("a")
      26
      iex> Caustic.Utils.base64_decode_char("f")
      31
      iex> Caustic.Utils.base64_decode_char("0")
      52
      iex> Caustic.Utils.base64_decode_char("5")
      57
      iex> Caustic.Utils.base64_decode_char("+")
      62
      iex> Caustic.Utils.base64_decode_char("/")
      63
  """
  def base64_decode_char(<<char_code>>), do: _base64_decode_char(char_code)
  
  def _base64_decode_char(char_code) when is_integer(char_code) and ?A <= char_code and char_code <= ?Z do
    char_code - ?A
  end

  def _base64_decode_char(char_code) when is_integer(char_code) and ?a <= char_code and char_code <= ?z do
    26 + char_code - ?a
  end

  def _base64_decode_char(char_code) when is_integer(char_code) and ?0 <= char_code and char_code <= ?9 do
    52 + char_code - ?0
  end

  def _base64_decode_char(char_code) when char_code === ?+, do: 62
  def _base64_decode_char(char_code) when char_code === ?/, do: 63

  @doc """
  Encodes a string into its MIME Base64 representation.
  
  https://en.wikipedia.org/wiki/Base64 (see Variants summary table)
  
  ## Examples
  
      iex> Caustic.Utils.base64_encode("Man")
      "TWFu"
      iex> Caustic.Utils.base64_encode("Ma")
      "TWE="
      iex> Caustic.Utils.base64_encode("M")
      "TQ=="
      iex> Caustic.Utils.base64_encode("Man is distinguished, not only by his reason, but by this singular passion from other animals...")
      "TWFuIGlzIGRpc3Rpbmd1aXNoZWQsIG5vdCBvbmx5IGJ5IGhpcyByZWFzb24sIGJ1dCBieSB0aGlz\\r\\nIHNpbmd1bGFyIHBhc3Npb24gZnJvbSBvdGhlciBhbmltYWxzLi4u"
      iex> Caustic.Utils.base64_encode("Man is distinguished, not only by his reason, but by this singular passion from other animals...", new_line: false)
      "TWFuIGlzIGRpc3Rpbmd1aXNoZWQsIG5vdCBvbmx5IGJ5IGhpcyByZWFzb24sIGJ1dCBieSB0aGlzIHNpbmd1bGFyIHBhc3Npb24gZnJvbSBvdGhlciBhbmltYWxzLi4u"
  """
  def base64_encode(data, opts \\ []) when is_binary(data), do: _base64_encode(data, [], 0, Keyword.get(opts, :new_line, true))

  defp _base64_encode(<<>>, acc, _len, _new_line?), do: Enum.reverse(acc) |> Enum.join()

  # Got 3 bytes
  defp _base64_encode(<<c1 :: size(6), c2 :: size(6), c3 :: size(6), c4 :: size(6), rest :: binary>>, acc, len, new_line?) do
    {acc, len} = _base64_append_newline(acc, len, new_line?)
    acc = [base64_encode_char(c4), base64_encode_char(c3), base64_encode_char(c2), base64_encode_char(c1) | acc]
    _base64_encode(rest, acc, len + 4, new_line?)
  end

  # The last block is 2 bytes
  defp _base64_encode(<<c1 :: size(6), c2 :: size(6), c3 :: size(4)>>, acc, len, new_line?) do
    {acc, len} = _base64_append_newline(acc, len, new_line?)
    c3 = c3 <<< 2
    acc = ["=", base64_encode_char(c3), base64_encode_char(c2), base64_encode_char(c1) | acc]
    _base64_encode(<<>>, acc, len + 4, new_line?)
  end

  # The last block is 1 byte
  defp _base64_encode(<<c1 :: size(6), c2 :: size(2)>>, acc, len, new_line?) do
    {acc, len} = _base64_append_newline(acc, len, new_line?)
    c2 = c2 <<< 4
    acc = ["=", "=", base64_encode_char(c2), base64_encode_char(c1) | acc]
    _base64_encode(<<>>, acc, len + 4, new_line?)
  end

  defp _base64_append_newline(acc, 76, true), do: {["\n", "\r" | acc], 0}
  defp _base64_append_newline(acc, 76, false), do: {acc, 0}
  defp _base64_append_newline(acc, len, _new_line), do: {acc, len}

  @doc """
  Decodes a MIME Base64 encoded string.
  
  https://en.wikipedia.org/wiki/Base64 (see Variants summary table)
  
  ## Examples
  
      iex> Caustic.Utils.base64_decode("TWFu")
      "Man"
      iex> Caustic.Utils.base64_decode("TWE=")
      "Ma"
      iex> Caustic.Utils.base64_decode("TQ==")
      "M"
      iex> Caustic.Utils.base64_decode("TWFuIGlzIGRpc3Rpbmd1aXNoZWQsIG5vdCBvbmx5IGJ5IGhpcyByZWFzb24sIGJ1dCBieSB0aGlz\\r\\nIHNpbmd1bGFyIHBhc3Npb24gZnJvbSBvdGhlciBhbmltYWxzLi4u")
      "Man is distinguished, not only by his reason, but by this singular passion from other animals..."
  """
  def base64_decode(str) do
    str_clean = _base64_decode_ignore_invalid_chars(str, [])
    _base64_decode(str_clean, [])
  end
  
  defp _base64_decode(<<>>, acc), do: Enum.reverse(acc) |> :binary.list_to_bin()

  defp _base64_decode(<<a, b, ?=, ?=, rest :: binary>>, acc) do
    a = _base64_decode_char(a)
    b = _base64_decode_char(b)
    <<x, _y, _z>> = <<a :: size(6), b :: size(6), 0 :: size(6), 0 :: size(6)>>
    _base64_decode(rest, [x | acc])
  end

  defp _base64_decode(<<a, b, c, ?=, rest :: binary>>, acc) do
    a = _base64_decode_char(a)
    b = _base64_decode_char(b)
    c = _base64_decode_char(c)
    <<x, y, _z>> = <<a :: size(6), b :: size(6), c :: size(6), 0 :: size(6)>>
    _base64_decode(rest, [y, x| acc])
  end
  
  defp _base64_decode(<<a, b, c, d, rest :: binary>>, acc) do
    a = _base64_decode_char(a)
    b = _base64_decode_char(b)
    c = _base64_decode_char(c)
    d = _base64_decode_char(d)
    <<x, y, z>> = <<a :: size(6), b :: size(6), c :: size(6), d :: size(6)>>
    _base64_decode(rest, [z, y, x | acc])
  end
  
  defp _base64_decode_ignore_invalid_chars(<<>>, acc), do: Enum.reverse(acc) |> Enum.join()
  defp _base64_decode_ignore_invalid_chars(<<c, rest :: binary>>, acc) 
    when (?A <= c
      and c <= ?Z)
    or (?a <= c
      and c <= ?z)
    or (?0 <= c
      and c <= ?9)
    or c == ?+
    or c == ?/
    or c == ?=,
  do: _base64_decode_ignore_invalid_chars(rest, [<<c>> | acc])
  defp _base64_decode_ignore_invalid_chars(<<_c, rest :: binary>>, acc), do: _base64_decode_ignore_invalid_chars(rest, acc)
  
  @doc """
  Converts a bitstring (including binary) into array of 0s and 1s.
  For simple binary you can also use :binary.decode_unsigned
  
  ## Examples
  
      iex> Caustic.Utils.bitstring_to_array "Hey"
      [0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1]
      iex> Caustic.Utils.bitstring_to_array << 1 :: size(1), 0 :: size(1), 1 :: size(1) >>
      [1, 0, 1]
  """
  def bitstring_to_array(data) when is_bitstring(data), do: _bitstring_to_array(data, [])
  
  defp _bitstring_to_array(<<>>, acc), do: Enum.reverse(acc)
  
  defp _bitstring_to_array(<< n :: size(1), rest :: bitstring >>, acc) do
    _bitstring_to_array(rest, [n | acc])
  end
  
  @doc """
  Calculates integer exponentiation. Exponent can be negative.
  
  ## Examples
  
      iex> Caustic.Utils.pow(3, 9)
      19683
      iex> Caustic.Utils.pow(2, 8)
      256
      iex> Caustic.Utils.pow(2, 256)
      115792089237316195423570985008687907853269984665640564039457584007913129639936
      iex> Caustic.Utils.pow(2, -2)
      0.25
  """
  def pow(n, p) when is_integer(p) and p > 0, do: _pow(n, p, 1)
  def pow(0, 0), do: raise ArithmeticError, "Division by zero"
  def pow(_, 0), do: 1
  def pow(n, p), do: 1.0 / pow(n, -p)
  
  defp _pow(_n, 0, acc), do: acc
  defp _pow(n, p, acc) when rem(p, 2) == 0, do: _pow(n * n, div(p, 2), acc)
  defp _pow(n, p, acc), do: _pow(n, p - 1, n * acc)
  
  @doc """
  Lists the exponents of `n` when `n` is represented as binary.
  For example, `34` in binary is `100010` or `2^5 + 2^1`, so
  the function will return `[1, 5]`.
  
  ## Examples
  
      iex> Caustic.Utils.binary_exponents(0)
      []
    
      iex> Caustic.Utils.binary_exponents(2)
      [1]
    
      iex> Caustic.Utils.binary_exponents(32)
      [5]
    
      iex> Caustic.Utils.binary_exponents(33)
      [0, 5]
  """
  def binary_exponents(n) when is_integer(n) and n >= 0 do
    _binary_exponents n, []
  end
  
  defp _binary_exponents(0, acc), do: acc
  defp _binary_exponents(rem, acc) do
    {next, rem} = log2i(rem)
    _binary_exponents rem, [next | acc]
  end
  
  @doc """
  Interprets a bitstring (including binary) as an unsigned integer. You can use :binary.decode_unsigned/1
  if it's a normal binary.
  
  ## Examples
  
      iex> Caustic.Utils.bitstring_to_integer(<<255, 255>>)
      65535
  """
  def bitstring_to_integer(data) when is_bitstring(data) and data != "" do
    len = bit_size(data)
    <<n :: size(len)>> = data
    n
  end

  @doc """
  Encodes an integer into its base58 representation. If given a string, by default it will
  interpret the string as a hex.
  
  If given hex and it has leading zeros, then each byte of zeros will be encoded as 1.
  
  ## Examples
  
      iex> Caustic.Utils.base58_encode("801e99423a4ed27608a15a2616a2b0e9e52ced330ac530edcc32c8ffc6a526aeddc47e83ff")
      "5J3mBbAH58CpQ3Y5RNJpUKPE62SQ5tfcvU2JpbnkeyhfsYB1Jcn"
      iex> Caustic.Utils.base58_encode(<<57>>, convert_from_hex: false)
      "z"
      iex> Caustic.Utils.base58_encode(63716817338599314535577169638518475271320430400871647684951348108655027767484127754748927)
      "5J3mBbAH58CpQ3Y5RNJpUKPE62SQ5tfcvU2JpbnkeyhfsYB1Jcn"
      iex> Caustic.Utils.base58_encode("0x000001")
      "112"
  """
  def base58_encode(str, opts \\ [])
  def base58_encode(str, opts) when is_binary(str) do
    opts = opts ++ [convert_from_hex: true]
    {n, padding} = if opts[:convert_from_hex] do
      n = str |> to_integer(16)
      padding = str |> hex_remove_prefix() |> _hex_get_zero_padding()
      {n, padding}
    else
      n = str |> :binary.decode_unsigned()
      padding = _binary_get_zero_padding(str)
      {n, padding}
    end
    
    _base58_encode_with_padding(n, padding)
  end
  
  def base58_encode(n, _opts) when is_integer(n) and 0 <= n and n <= 57 do
    String.slice(@base58_table, n, 1)
  end
  
  def base58_encode(n, _opts) when is_integer(n) and n >= 0 do
    to_digits(n, 58) |> Enum.map_join(&base58_encode/1)
  end
  
  def _base58_encode_with_padding(n, padding) do
    prefix = String.duplicate("1", padding)
    prefix <> base58_encode(n)
  end

  def _hex_get_zero_padding(str, acc \\ 0)
  def _hex_get_zero_padding(<<?0, ?0, rest::binary>>, acc), do: _hex_get_zero_padding(rest, acc + 1)
  def _hex_get_zero_padding(str, acc) do
    if rem(String.length(str), 2) == 0, do: acc, else: 0
  end

  def _binary_get_zero_padding(data, acc \\ 0)
  def _binary_get_zero_padding(<<0x00, rest::binary>>, acc), do: _binary_get_zero_padding(rest, acc + 1)
  def _binary_get_zero_padding(_, acc), do: acc
  
  #def _hex_remove_prefix
  
  @doc """
  Same as base58_decode but outputs an integer instead of hex string.
  """
  def base58_to_integer(str) when is_binary(str), do: _base58_to_integer(str, 0)
  
  defp _base58_to_integer(<<>>, acc), do: acc
  defp _base58_to_integer(<<c, rest :: binary>>, acc) do
    c = << c >>
    value = string_index_of @base58_table, c
    _base58_to_integer(rest, acc * 58 + value)
  end
  
  @doc """
  Decode a base58-encoded string into its hexadecimal string representation.
  
  ## Examples
  
      iex> Caustic.Utils.base58_decode("5J3mBbAH58CpQ3Y5RNJpUKPE62SQ5tfcvU2JpbnkeyhfsYB1Jcn")
      "0x801e99423a4ed27608a15a2616a2b0e9e52ced330ac530edcc32c8ffc6a526aeddc47e83ff"
      iex> Caustic.Utils.base58_decode("5J3mBbAH58CpQ3Y5RNJpUKPE62SQ5tfcvU2JpbnkeyhfsYB1Jcn", prefix: false)
      "801e99423a4ed27608a15a2616a2b0e9e52ced330ac530edcc32c8ffc6a526aeddc47e83ff"
  """
  def base58_decode(str, opts \\ []), do: base58_to_integer(str) |> to_string(16, opts)
  
  @doc """
  Encodes a binary to its base58check representation.
  
  Possible values for version: `:address`, `:address_p2sh`, `:address_testnet`,
  `private_key_wif`, `private_key_bip38_encrypted`, `public_key_bit32_extended`
  
  Can also use custom binary version.
  
  ## Examples
  
      iex> Caustic.Utils.base58check_encode("0x1e99423a4ed27608a15a2616a2b0e9e52ced330ac530edcc32c8ffc6a526aedd", :private_key_wif)
      "5J3mBbAH58CpQ3Y5RNJpUKPE62SQ5tfcvU2JpbnkeyhfsYB1Jcn"
      iex> Caustic.Utils.base58check_encode(<<Caustic.Utils.to_integer("0x1e99423a4ed27608a15a2616a2b0e9e52ced330ac530edcc32c8ffc6a526aedd")::size(256)>>, :private_key_wif, convert_from_hex: false)
      "5J3mBbAH58CpQ3Y5RNJpUKPE62SQ5tfcvU2JpbnkeyhfsYB1Jcn"
      iex> Caustic.Utils.base58check_encode(<<Caustic.Utils.to_integer("0x1e99423a4ed27608a15a2616a2b0e9e52ced330ac530edcc32c8ffc6a526aedd")::size(256), 0x01>>, :private_key_wif, convert_from_hex: false)
      "KxFC1jmwwCoACiCAWZ3eXa96mBM6tb3TYzGmf6YwgdGWZgawvrtJ"
      iex> Caustic.Utils.base58check_encode(<<Caustic.Utils.to_integer("1E99423A4ED27608A15A2616A2B0E9E52CED330AC530EDCC32C8FFC6A526AEDD", 16)::size(256), 0x01>>, :private_key_wif, convert_from_hex: false)
      "KxFC1jmwwCoACiCAWZ3eXa96mBM6tb3TYzGmf6YwgdGWZgawvrtJ"
      iex> Caustic.Utils.base58check_encode("f5f2d624cfb5c3f66d06123d0829d1c9cebf770e", :address)
      "1PRTTaJesdNovgne6Ehcdu1fpEdX7913CK"
      iex> Caustic.Utils.base58check_encode("000000cb23faea20aa20f02a02955ffd1d785518", :address)
      "1111DVWAb9XQh88gakJRcK14e1i1onvAL" # private key is 5KjhZsxt61XSPunjrPm8XUEAH1YN6zXm6pqT5D1hZ9mLoEAqKTp
  """
  def base58check_encode(payload, version, opts \\ []) do
    opts = opts ++ [convert_from_hex: true]
    
    if opts[:convert_from_hex] do
      payload_i = to_integer(payload, 16)
      size = 4 * String.length(hex_remove_prefix(payload))
      payload_raw = <<payload_i::size(size)>>
      _base58check_encode(payload_raw, version)
    else
      _base58check_encode(payload, version)
    end
  end
  
  def _base58check_encode(payload, version) when is_atom(version), do: _base58check_encode(payload, Map.fetch!(@base58_version, version))
  
  def _base58check_encode(payload, version) when is_binary(payload) and is_binary(version) do
    payload_with_version = version <> payload
    checksum = base58_checksum(payload_with_version)
    final_payload = payload_with_version <> checksum
    final_payload |> base58_encode(convert_from_hex: false)
  end
  
  def base58_checksum(data) do
    <<checksum::size(32), _rest::binary>> = :crypto.hash(:sha256, :crypto.hash(:sha256, data))
    <<checksum::size(32)>>
  end
  
  def base58_version(data) do
    _base58_version(data, Map.keys(@base58_version))
  end
  
  defp _base58_version(data, []), do: {nil, data}
  defp _base58_version(data, [key | rest]) do
    prefix = @base58_version[key]
    prefix_length = byte_size(prefix)
    case data do
      <<^prefix::binary-size(prefix_length), payload::binary>>
        -> {key, payload}
      _
        -> _base58_version(data, rest)
    end
  end
  
  @doc """
  Returns checksum, payload, and version
  
  ## Examples
  
      iex> Caustic.Utils.base58check_decode "5J3mBbAH58CpQ3Y5RNJpUKPE62SQ5tfcvU2JpbnkeyhfsYB1Jcn"
      {:ok, <<196, 126, 131, 255>>, "1e99423a4ed27608a15a2616a2b0e9e52ced330ac530edcc32c8ffc6a526aedd", :private_key_wif}
      iex> Caustic.Utils.base58check_decode "1J7mdg5rbQyUHENYdx39WVWK7fsLpEoXZy"
      {:ok, <<55, 254, 252, 208>>, "bbc1e42a39d05a4cc61752d6963b7f69d09bb27b", :address}
  """
  def base58check_decode(str) do
    str_i = base58_to_integer(str)
    {exp, remainder} = log2i(str_i)
    bin_digit = exp + (if remainder == 0, do: 0, else: 1)
    bin_digit = bin_digit + rem(bin_digit, 8) # multiple of 1 byte
    data_bin_size = div(bin_digit - 32, 8)
    <<data_bin::binary-size(data_bin_size), checksum::binary>> = <<str_i::size(bin_digit)>>
    data_normalized = _base58check_data_normalize(data_bin)

    #<<data_int::size(data_bin_size), checksum::binary>> = <<str_i::size(bin_digit)>>
    #data_bin = <<data_int::size(data_bin_size)>>
    checksum_computed = base58_checksum(data_normalized)

    #IO.puts("Data is #{inspect(data_bin)}")
    #IO.puts("Checksum is #{inspect(checksum)}")
    
    if checksum_computed != checksum do
      {:error, "Checksum doesn't match. Computed #{inspect(checksum_computed)} vs actual #{inspect(checksum)}"}
    else
      {version, payload_bin} = base58_version(data_normalized)
      payload_hex = Base.encode16(payload_bin, case: :lower)
      #IO.puts("Version is #{inspect @base58_version[version]}")
      #IO.puts("Payload id #{inspect payload_bin}")
      
      # bx uses :binary.decode_unsigned(checksum, :little) to print checksum
      {:ok, checksum, payload_hex, version}
    end
  end
  
  # data of type :bitcoin_address has prefix 0x00 which is lost on encoding,
  # so we need to restore it.
  defp _base58check_data_normalize(data) do
    _base58check_data_normalize(data, Map.values(@base58_version))
  end

  defp _base58check_data_normalize(data, []) do
    # address size must be 20 bytes, so with version it is 21 bytes
    target_size = 21
    current_size = byte_size(data)
    diff = (target_size - current_size) * 8
    <<0x00::size(diff), data::binary>>
  end
                                            
  defp _base58check_data_normalize(data, [prefix | rest]) do
    len = byte_size(prefix)
    case data do
       <<^prefix::binary-size(len), _rest::binary>> -> data
       _ -> _base58check_data_normalize(data, rest)
    end
  end
  
  def log2i(n) when is_integer(n) and n >=1 do
    res = _log2i(n, 0)
    {res, rem(n, pow(2, res))}
  end
  defp _log2i(1, acc), do: acc
  defp _log2i(n, acc), do: _log2i(div(n, 2), acc + 1)
  
  @doc """
  Converts a Bitcoin 256-bit private key to the Wallet Import Format. Defaults to outputting compressed format.
  
  ## Examples
  
      iex> Caustic.Utils.bitcoin_private_key_to_wif("1e99423a4ed27608a15a2616a2b0e9e52ced330ac530edcc32c8ffc6a526aedd")
      "KxFC1jmwwCoACiCAWZ3eXa96mBM6tb3TYzGmf6YwgdGWZgawvrtJ"
      iex> Caustic.Utils.bitcoin_private_key_to_wif("1e99423a4ed27608a15a2616a2b0e9e52ced330ac530edcc32c8ffc6a526aedd", compressed: false)
      "5J3mBbAH58CpQ3Y5RNJpUKPE62SQ5tfcvU2JpbnkeyhfsYB1Jcn"
  """
  def bitcoin_private_key_to_wif(hex_str, opts \\ []) do
    opts = opts ++ [compressed: true]
    hex_str = if opts[:compressed], do: hex_str <> "01", else: hex_str
    base58check_encode(hex_str, :private_key_wif)
  end
  
  @doc """
  Finds the index of an ASCII character inside a string. Not unicode friendly!
  
  ## Examples
  
      iex> Caustic.Utils.string_index_of("Hello", "H")
      0
      iex> Caustic.Utils.string_index_of("Hello", "h")
      nil
      iex> Caustic.Utils.string_index_of("Hello", "l")
      2
  """
  def string_index_of(str, c), do: _string_index_of(str, c, 0)
  defp _string_index_of(<<>>, _c, _), do: nil
  defp _string_index_of(<<next, _rest :: binary>>, c, i) when << next >> == c, do: i
  defp _string_index_of(<<_next, rest :: binary>>, c, i), do: _string_index_of(rest, c, i + 1)

  @doc """
  Find the digits of a nonnegative integer `n` in a particular `base`.
  
  ## Examples
      iex> Caustic.Utils.to_digits(321, 10)
      [3, 2, 1]
      iex> Caustic.Utils.to_digits(5, 2)
      [1, 0, 1]
      iex> Caustic.Utils.to_digits(255, 16)
      [15, 15]
      iex> Caustic.Utils.to_digits(0, 8)
      [0]
  """
  def to_digits(n, base)
    when is_integer(n)
    and is_integer(base)
    and n >= 0
    and base >= 2 do
    _to_digits(n, base, [])
  end

  defp _to_digits(0, _base, []), do: [0]
  defp _to_digits(0, _base, acc), do: acc
  defp _to_digits(n, base, acc) do
    d = div(n, base)
    r = rem(n, base)
    _to_digits(d, base, [r | acc])
  end
  
#  @doc """
#  Convert a digit's integer representation to its string representation.
#  
#  ## Examples
#  
#    iex> Caustic.Utils.to_string(8, 10)
#    "8"
#    iex> Caustic.Utils.to_string(15, 16)
#    "f"
#  """
#  def to_string(n, base)
#    when is_integer(n)
#    and is_integer(base)
#    and n >= 0
#    and base >= 2
#    and n < base
#    and base <= 36
#    do
#    _to_string(n, base)
#  end
  
  @doc """
  Convert an integer into its string representation in any `base`.
  
  ## Examples
  
      iex> Caustic.Utils.to_string(255, 16)
      "0xff"
      iex> Caustic.Utils.to_string(255, 16, prefix: false)
      "ff"
      iex> Caustic.Utils.to_string(5, 2)
      "0b101"
  """
  def to_string(n, base, opts \\ []) do
    opts = opts ++ [prefix: true, padding: 0]
    str = to_digits(n, base) |> Enum.map_join(&_to_string(&1, base))

    str = String.pad_leading(str, opts[:padding], "0")
    
    prefix = if opts[:prefix], do: Map.get(@base_prefixes, base, ""), else: "" 
    prefix <> str
  end

  defp _to_string(n, _base) when n <= 9, do: to_string(n)
  defp _to_string(n, _base), do: <<?a + n - 10>>
  
  @doc """
  Parse a string which can be in any base to integer, autodetecting the base using the prefix.
  
  ## Examples
  
      iex> Caustic.Utils.to_integer("0xff")
      255
      iex> Caustic.Utils.to_integer("0b101")
      5
      iex> Caustic.Utils.to_integer("321")
      321
  """
  def to_integer(str) do
    base = get_base(String.downcase(str))
    to_integer(str, base)
  end

  @doc """
  Parse a string which can be in any base to integer, specifying the base.
  
  ## Examples
  
      iex> Caustic.Utils.to_integer("ff", 16)
      255
      iex> Caustic.Utils.to_integer("101", 2)
      5
      iex> Caustic.Utils.to_integer("755", 8)
      493
      iex> Caustic.Utils.to_integer("321", 10)
      321
  """
  def to_integer(str, base) do
    str = String.downcase(str)
    prefix = Map.get(@base_prefixes, base)
    if prefix == nil do
      _to_integer(str, base)
    else
      if String.starts_with?(str, prefix) do
        prefix_len = String.length(prefix)
        rest = String.slice(str, prefix_len..-1)
        _to_integer(rest, base)
      else
        _to_integer(str, base)
      end
    end
  end
  
  defp _to_integer(str, base) do
    _to_integer(str, base, 0)
  end
  
  defp _to_integer(<<>>, _base, acc), do: acc
  
  defp _to_integer(<<digit, rest :: binary>>, base, acc) do
    acc = acc * base + _digit_to_integer(digit, base)
    _to_integer(rest, base, acc)
  end
  
  defp _digit_to_integer(char_code, base) when ?0 <= char_code and char_code <= ?9 and char_code - ?0 < base, do: char_code - ?0
  defp _digit_to_integer(char_code, base) when ?a <= char_code and char_code <= ?z and 10 + char_code - ?a < base, do: 10 + char_code - ?a
  
  @doc """
  Guess the base of an integer string using its prefix. Defaults to 10, and doesn't check for validity of the digits.
  
  ## Examples
  
      iex> Caustic.Utils.get_base("0xabf")
      16
      iex> Caustic.Utils.get_base("0b101")
      2
      iex> Caustic.Utils.get_base("321")
      10
  """
  def get_base(str) do
    keys = Map.keys @base_prefixes
    _get_base(str, keys)
  end
  
  defp _get_base(str, [base | rest]) do
    prefix = @base_prefixes[base]
    if String.starts_with?(str, prefix),
      do: base,
      else: _get_base(str, rest)
  end
  
  defp _get_base(<<c, rest :: binary>>, []) when ?0 <= c and c <= ?9, do: _get_base(rest, [])
  defp _get_base("", []), do: 10
  
  @doc """
  Removes hexadecimal prefix from a string.
  
  ## Examples
  
      iex> Caustic.Utils.hex_remove_prefix("0xff")
      "ff"
      iex> Caustic.Utils.hex_remove_prefix("0XFF")
      "FF"
      iex> Caustic.Utils.hex_remove_prefix("ff")
      "ff"
  """
  def hex_remove_prefix(str) do
    if String.starts_with?(str, ["0x", "0X"]) do
      String.slice(str, 2..-1)
    else
      str
    end
  end

  @doc """
  Finds the least residue of a number modulo `m`.
  
  ## Examples
  
      iex> Caustic.Utils.mod(0, 3)
      0
      iex> Caustic.Utils.mod(-27, 13)
      12
      iex> Caustic.Utils.mod(-3, 3)
      0
  """
  def mod(x, m) when x >= 0, do: rem(x, m)
  def mod(x, m) when x < 0, do: rem(rem(x, m) + m, m)

  @doc """
  Fast exponentiation modulo m. Calculates x^y mod m.
  
  With x = 5, y = 12345, m = 17, and repeated 1000 times,
  it is faster by naive method by a factor of 150 on
  a particular benchmark machine.

  https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-exponentiation
  https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation
  
  ## Examples
  
      iex> Caustic.Utils.pow_mod(5, 0, 19)
      1
      iex> Caustic.Utils.pow_mod(5, 1, 19)
      5
      iex> Caustic.Utils.pow_mod(5, 117, 19)
      1
      iex> Caustic.Utils.pow_mod(7, 256, 13)
      9
      iex> Caustic.Utils.pow_mod(2, 90, 13)
      12
      iex> Caustic.Utils.pow_mod(50, -1, 71)
      27
      iex> Caustic.Utils.pow_mod(7, -3, 13)
      8
  """
  def pow_mod(x, -1, m), do: mod_inverse(x, m)
  def pow_mod(x, y, m) when y < -1 do
    inverse = pow_mod(x, -1, m)
    pow_mod(inverse, -y, m)
  end
  def pow_mod(x, y, m) do
    digits = to_digits(y, 2)
    
    digits
    |> Enum.reverse()
    |> Enum.reduce({1, mod(x, m)}, fn n, {acc, factor} ->
      acc = if n == 0, do: acc, else: acc * factor
      factor = factor * factor |> mod(m)
      {acc, factor}
    end)
    |> elem(0)
    |> mod(m)
  end
  
  @doc """
  Find the greatest common divisor of two integers.
  
  Proof: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm
  
  ## Examples

      iex> Caustic.Utils.gcd(1, 0)
      1

      iex> Caustic.Utils.gcd(-1, 0)
      1
  
      iex> Caustic.Utils.gcd(270, 192)
      6

      iex> Caustic.Utils.gcd(-270, 192)
      6

      iex> Caustic.Utils.gcd(270, -192)
      6

      iex> Caustic.Utils.gcd(-270, -192)
      6
  """
  def gcd(a, b) when a < 0, do: gcd(-a, b)
  def gcd(a, b) when b < 0, do: gcd(a, -b)
  def gcd(a, b) when a != 0 or b != 0, do: _gcd(a, b)
  def _gcd(0, b), do: b
  def _gcd(a, 0), do: a
  def _gcd(a, b) do
    #q = div(a, b)
    r = mod(a, b)
    _gcd(b, r)
  end

  @doc """
  Find the greatest common divisor `d` of two integers `a` and `b`, while also finding
  the coefficients `x` and `y` such that `ax + by = d`.

  ## Examples
      iex> Caustic.Utils.gcd_with_coefficients(3, 0)
      {3, 1, 0}

      iex> Caustic.Utils.gcd_with_coefficients(6, 3)
      {3, 0, 1}

      iex> Caustic.Utils.gcd_with_coefficients(270, 192)
      {6, 5, -7}

      iex> Caustic.Utils.gcd_with_coefficients(-270, 192)
      {6, -5, -7}

      iex> Caustic.Utils.gcd_with_coefficients(270, -192)
      {6, 5, 7}

      iex> Caustic.Utils.gcd_with_coefficients(-270, -192)
      {6, -5, 7}

      iex> Caustic.Utils.gcd_with_coefficients(314, 159)
      {1, -40, 79}
  """
  def gcd_with_coefficients(a, b) when a < 0 do
    {d, x, y} = gcd_with_coefficients(-a, b)
    {d, -x, y}
  end

  def gcd_with_coefficients(a, b) when b < 0 do
    {d, x, y} = gcd_with_coefficients(a, -b)
    {d, x, -y}
  end

  def gcd_with_coefficients(a, b) when a < b do
    {d, x, y} = gcd_with_coefficients(b, a)
    {d, y, x}
  end

  def gcd_with_coefficients(a, b) when a != 0, do: _gcd_with_coefficients(a, b, 1, 0, 0, 1)

  def _gcd_with_coefficients(a, 0, x, y, _, _), do: {a, x, y}

  def _gcd_with_coefficients(a, b, x_prev_prev, y_prev_prev, x_prev, y_prev) do
    q = div(a, b)
    r = mod(a, b)
    x = x_prev_prev - q * x_prev
    y = y_prev_prev - q * y_prev
    _gcd_with_coefficients(b, r, x_prev, y_prev, x, y)
  end

  @doc """
  Find the modular inverse (modular multiplicative inverse).
  
  Using Euclidean Algorithm: https://www.math.utah.edu/~fguevara/ACCESS2013/Euclid.pdf
  
  ## Examples
  
      iex> Caustic.Utils.mod_inverse(1, 101)
      1
      iex> Caustic.Utils.mod_inverse(2, 3)
      2
      iex> Caustic.Utils.mod_inverse(50, 71)
      27
      iex> Caustic.Utils.mod_inverse(25, 50)
      nil
      iex> Caustic.Utils.mod_inverse(8, 11)
      7
      iex> Caustic.Utils.mod_inverse(345, 76408)
      48281
      iex> Caustic.Utils.mod_inverse(71, 50)
      31
    
      # Bitcoin elliptic curve
      iex> Caustic.Utils.mod_inverse(345, 115792089237316195423570985008687907853269984665640564039457584007908834671663)
      53029420578249156164997726467746925915410601672960026429664632676085785153979
  """
  def mod_inverse(a, m) when a >= m or a < 0, do: mod_inverse(mod(a, m), m)
  def mod_inverse(a, m) do
    result = _mod_inverse(m, a)
    if result == nil, do: nil, else: mod(result, m) # normalize to 0 < inverse < m
  end

  # instead of using sentinel values q_prev = nil and q_prev_prev = nil
  # the equation works perfectly if we use initial values of q_prev = 1 and q_prev_prev = 0
  defp _mod_inverse(m, a, q_prev \\ 1, q_prev_prev \\ 0)
  
  # not coprimes, doesn't have inverse mod m
  defp _mod_inverse(_m, 0, _, _), do: nil
  
  defp _mod_inverse(_m, 1, q_prev, _), do: q_prev
  
  defp _mod_inverse(m, a, q_prev, q_prev_prev) do
    q = div(m, a)
    r = mod(m, a)

    #IO.puts("[#{m}] = [#{a}] . #{q} + #{r}")
    
    _mod_inverse(a, r, q_prev_prev - q * q_prev, q_prev)
  end

  # 1 is a unit
  def prime?(n) when n <= 1, do: false
  def prime?(n), do: _prime?(n, 2)

  # if a number n is composite, then it is divisible by a prime
  # less than or equal to sqrt(n)
  # TODO: Optimize using the first n primes
  defp _prime?(n, factor) when factor * factor > n, do: true
  defp _prime?(n, factor) when rem(n, factor) == 0, do: false
  defp _prime?(n, factor), do: _prime?(n, factor + 1)

  # 1 is a unit
  @doc """
  Checks whether an integer `n > 1` is a composite number. 1 is a unit,
  neither a prime nor composite. Will return false on `n <= 1`.

  ## Examples

      iex> Caustic.Utils.composite?(4)
      true
      iex> Caustic.Utils.composite?(2)
      false
      iex> Caustic.Utils.composite?(3)
      false
      iex> Caustic.Utils.composite?(1)
      false
  """
  def composite?(n) when n <= 1, do: false
  def composite?(n), do: not prime?(n)

  @doc """
  Find the prime factors of an integer.
  
  ## Examples

      iex> Caustic.Utils.factorize(72)
      [2, 2, 2, 3, 3]
      iex> Caustic.Utils.factorize(480)
      [2, 2, 2, 2, 2, 3, 5]
      iex> Caustic.Utils.factorize(357171293798123)
      [7, 181, 1459, 193216691]
      iex> Caustic.Utils.factorize(100000001)
      [17, 5882353]
      iex> Caustic.Utils.factorize(9223372036854775807) # largest 64-bit integer
      [7, 7, 73, 127, 337, 92737, 649657]
      iex> Caustic.Utils.factorize(18446744073709551615) # largest 64-bit unsigned integer
      [3, 5, 17, 257, 641, 65537, 6700417]
      iex> Caustic.Utils.factorize(18446744073709551615 * 3571 * 5901331)
      [3, 5, 17, 257, 641, 3571, 65537, 5901331, 6700417]
      iex> Caustic.Utils.factorize(1)
      []
  """
  def factorize(n) when n <= 1, do: []
  def factorize(n), do: _factorize(n, [])

  defp _factorize(1, factors), do: factors |> Enum.reverse()
  defp _factorize(n, factors) do
    p = smallest_prime_divisor(n)
    _factorize(div(n, p), [p | factors])
  end
  
  def factorize_grouped(n) do
    factorize(n)
    |> Enum.reduce([], fn
      n, [{n, count} | rest] ->
        [{n, count + 1} | rest]
      n, acc ->
        [{n, 1} | acc]
    end)
    |> Enum.reverse()
  end

#  defp _factorize(n, factors) do
#    sqrt = floor(:math.sqrt(n))
#    divisors = 2..sqrt |> Enum.filter(& rem(n, &1) == 0)
#    smallest_prime_divisor = divisors |> Enum.filter(&prime?/1) |> List.first()
#    smallest_prime_divisor = if smallest_prime_divisor === nil, do: n, else: smallest_prime_divisor
#    factors = [smallest_prime_divisor | factors]
#    _factorize(div(n, smallest_prime_divisor), factors)
#  end

  @doc """
  ## Examples
  
      iex> Caustic.Utils.smallest_prime_divisor(2)
      2
      iex> Caustic.Utils.smallest_prime_divisor(4)
      2
      iex> Caustic.Utils.smallest_prime_divisor(144)
      2
      iex> Caustic.Utils.smallest_prime_divisor(5)
      5
      iex> Caustic.Utils.smallest_prime_divisor(35)
      5
  """
  def smallest_prime_divisor(n) when n <= 1, do: nil
  def smallest_prime_divisor(n) when rem(n, 2) == 0, do: 2
  def smallest_prime_divisor(n), do: _smallest_prime_divisor(n, 3)

  defp _smallest_prime_divisor(n, factor) when factor * factor > n, do: n
  defp _smallest_prime_divisor(n, factor) when rem(n, factor) == 0, do: factor
  defp _smallest_prime_divisor(n, factor), do: _smallest_prime_divisor(n, factor + 2)
#
#    if prime?(factor), do: factor, else: _smallest_prime_divisor(n, factor + 1)
#  end

  @doc """
  Checks whether an integer is a prime using Sieve of Eratosthenes algorithm.
  Don't use on very large numbers.
  """
  def prime_sieve?(n) when n <= 1, do: false
  def prime_sieve?(n) do
    sieve = List.duplicate(true, n + 1) |> List.to_tuple() # assume all are primes
    _prime_sieve?(n, 2, sieve)
  end

  defp _prime_sieve?(n, factor, _sieve) when factor * factor > n, do: true
  defp _prime_sieve?(n, factor, sieve) do
    is_prime = elem(sieve, factor)
    if is_prime do
      {sieve, n_is_composite} = _sieve_sweep(sieve, factor * 2, factor)
      if n_is_composite, do: false, else: _prime_sieve?(n, factor + 1, sieve)
    else
      _prime_sieve?(n, factor + 1, sieve)
    end
  end

  defp _sieve_sweep(sieve, next, _factor) when next == tuple_size(sieve) - 1, do: {sieve, true}
  defp _sieve_sweep(sieve, next, _factor) when next >= tuple_size(sieve), do: {sieve, false}
  defp _sieve_sweep(sieve, next, factor) do
    sieve = put_elem(sieve, next, false)
    _sieve_sweep(sieve, next + factor, factor)
  end

  # {time, res} = :timer.tc(Utils, :prime_sieve_up_to, [10_000_000])
  # {time, :ok} = :timer.tc Utils, :write_to_file, [Enum.to_list(1..10_000_000), "/tmp/elixir_test_out_2.txt", 10] # 2 minutes
  @doc """
  Find all primes `p ≤ n` using Sieve of Eratosthenes method.
  
  ## Examples
      iex> Caustic.Utils.prime_sieve_up_to(10)
      [2, 3, 5, 7]

      iex> Caustic.Utils.prime_sieve_up_to(30)
      [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

      iex> Caustic.Utils.prime_sieve_up_to(100)
      [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
  """
  def prime_sieve_up_to(n) when n >= 2 do
#    easy_primes = [ 2,  3,  5,  7, 11,
#                   13, 17, 19, 23, 29]
    easy_primes = primes_first_500()
    first_sieves = 2..n |> Enum.filter(&_potentially_prime?(&1, easy_primes))
    check_limit = trunc(:math.sqrt(n))

    {left, right} = list_split first_sieves, Enum.count(easy_primes)
    left = left |> Enum.filter(& &1 <= n)
    if Enum.count(right) == 0 do
      left
    else
      _prime_sieve_up_to(check_limit, Enum.reverse(left), right)
    end
  end
  
  @doc """
  Determines whether an integer is a perfect number.
  A number n is perfect iff σ(n) - n = n
  
  ## Examples
  
      iex> Caustic.Utils.perfect?(6)
      true
      iex> Caustic.Utils.perfect?(5)
      false
  """
  def perfect?(n) when is_number(n) and n > 0 do
    proper_divisors_sum(n) == n
  end
  
  @doc """
  The other number of an amicable pair, if any.
  
  ## Examples
  
      iex> Caustic.Utils.amicable_pair(220)
      284
      iex> Caustic.Utils.amicable_pair(2)
      nil
  """
  def amicable_pair(n) do
    sum = proper_divisors_sum(n)
    if sum != n and proper_divisors_sum(sum) == n do
      sum
    else
      nil
    end
  end
  
  @doc """
  Euler's totient function `φ(n)`.
  The number of positive integers less than or equal to `m`
  and relatively prime to `m`.
  
  ## Examples
  
      iex> Caustic.Utils.totient(5)
      4
    
      iex> Caustic.Utils.totient(6)
      2
    
      iex> Caustic.Utils.totient(9)
      6
    
      iex> Caustic.Utils.totient(1)
      1
    
      iex> Caustic.Utils.totient(4200)
      960
  """
  def totient(m) do
    factorize_grouped(m)
    |> Enum.reduce(1, fn {p, e}, acc -> acc * _totient_prime(p, e) end)
  end
  
  def _totient_prime(p, e), do: pow(p, e - 1) * (p - 1)
  
  @doc """
  Positive integers less than or equal to `m` and relatively prime to `m`.
  
  ## Examples
  
      iex> Caustic.Utils.totient_members(1)
      [1]
    
      iex> Caustic.Utils.totient_members(6)
      [1, 5]
    
      iex> Caustic.Utils.totient_members(9)
      [1, 2, 4, 5, 7, 8]
    
      iex> Caustic.Utils.totient_members(10)
      [1, 3, 7, 9]
  """
  def totient_members(m) when is_integer(m) and m > 0 do
    1..m |> Enum.filter(&gcd(m, &1) === 1)
  end 

  @doc """
  Splits a list into its first `n` elements and the rest.

  ## Examples

      iex> Caustic.Utils.list_split([1, 2, 3, 4, 5], 2)
      {[1, 2], [3, 4, 5]}

      iex> Caustic.Utils.list_split([1, 2, 3], 5)
      {[1, 2, 3], []}
  """
  def list_split(objs, n) when n >= 0, do: _list_split([], objs, n)

  defp _list_split(left, right, 0), do: {Enum.reverse(left), right}
  defp _list_split(left, [], _), do: _list_split(left, [], 0)
  defp _list_split(left, [o | rest], n), do: _list_split([o | left], rest, n - 1)

  defp _prime_sieve_up_to(check_limit, left, right = [p | _]) when p > check_limit do
    Enum.reverse(left) ++ right
  end
  defp _prime_sieve_up_to(check_limit, left, [p | rest]) do
    rest = rest |> Enum.filter(& rem(&1, p) != 0)
    _prime_sieve_up_to(check_limit, [p | left], rest)
  end

  defp _potentially_prime?(_n, []), do: true
  defp _potentially_prime?(n, [d | rest]) do
    if d < n and rem(n, d) == 0 do
      false
    else
      _potentially_prime?(n, rest)
    end
  end

  def write_to_file(list, path, item_per_line) do
    {:ok, file} = File.open path, [:write] # or :append
    :ok = _write_to_file file, list, item_per_line, 0
    File.close file
  end

  defp _write_to_file(_file, [], _, _), do: :ok
  defp _write_to_file(file, [item | rest], item_per_line, i) do
    IO.binwrite file, "#{item}"

    if rem(i, item_per_line) === item_per_line - 1 do
      IO.binwrite file, "\n"
    else
      IO.binwrite file, " "
    end

    _write_to_file file, rest, item_per_line, i + 1
  end
  
  @doc """
  https://oeis.org/A000043
  https://en.wikipedia.org/wiki/Mersenne_prime
  The first n Mersenne exponents, primes p such that 2^p - 1 is prime.
  
  ## Examples
  
      iex> Caustic.Utils.mersenne_exponents_first(5)
      [2, 3, 5, 7, 13]
  """
  def mersenne_exponents_first(n) when is_integer(n) and n >= 1 and n <= length(@mersenne_exponents) do
    @mersenne_exponents
    |> Enum.take(n)
  end
  
  @doc """
  https://oeis.org/A000668
  https://en.wikipedia.org/wiki/Mersenne_prime
  The i-th Mersenne prime, starting at index 0.
  Primes of the form 2^p - 1 where p is a prime.
  
  ## Examples
  
      iex> Caustic.Utils.mersenne_prime(0)
      3
  """
  def mersenne_prime(i) when is_integer(i) and i >= 0 and i < length(@mersenne_primes) do
      @mersenne_primes |> Enum.at(i)
  end
  
  def mersenne_prime(i) when is_integer(i) and i >= 0 and i < length(@mersenne_exponents) do
    p = @mersenne_exponents |> Enum.at(i)
    pow(2, p) - 1
  end

  def primes_first_500() do
    [
      2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
      31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
      73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
      127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
      179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
      233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
      283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
      353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
      419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
      467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
      547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
      607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
      661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
      739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
      811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
      877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
      947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013,
      1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069,
      1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
      1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,
      1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291,
      1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373,
      1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
      1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,
      1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583,
      1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657,
      1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
      1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,
      1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889,
      1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987,
      1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
      2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129,
      2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213,
      2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287,
      2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
      2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,
      2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531,
      2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617,
      2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
      2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741,
      2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819,
      2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903,
      2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
      3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079,
      3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181,
      3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257,
      3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
      3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413,
      3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511,
      3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571
    ]
  end

  @doc """
  Calculate the document hash, used for ECDSA.
  """
  def hash256(str), do: :crypto.hash(:sha256, :crypto.hash(:sha256, str))

  @doc """
  Calculate the md5 hash.
  """
  def md5(str), do: :crypto.hash(:md5, str)

  @doc """
  If an integer can be written as the sum of the squares of two positive integers,
  return those two integers {a, b} where a <= b.

  ## Examples

      iex> Caustic.Utils.to_sum_of_two_squares(17)
      {1, 4}
      iex> Caustic.Utils.to_sum_of_two_squares(1)
      nil
  """
  def to_sum_of_two_squares(i) when is_integer(i) and i > 0 do
    sqrt = trunc(:math.sqrt(i))
    _to_sum_of_two_squares(i, 1, 1, sqrt)
  end

  def _to_sum_of_two_squares(i, a, b, _) when a * a + b * b == i, do: {a, b}
  def _to_sum_of_two_squares(i, a, b, sqrt) when b + 1 <= sqrt, do: _to_sum_of_two_squares(i, a, b + 1, sqrt)
  def _to_sum_of_two_squares(i, a, _b, sqrt) when a + 1 <= sqrt, do: _to_sum_of_two_squares(i, a + 1, a + 1, sqrt)
  def _to_sum_of_two_squares(_, _, _, _), do: nil

  @doc """
  Checks whether `a` divides `b`.
  See https://math.stackexchange.com/questions/666103/why-would-some-elementary-number-theory-notes-exclude-00 and
  https://math.stackexchange.com/questions/2174535/does-zero-divide-zero

  ## Examples

      iex> Caustic.Utils.divides(2, 8)
      true
      iex> Caustic.Utils.divides(2, 3)
      false
      iex> Caustic.Utils.divides(2, 0)
      true
      iex> Caustic.Utils.divides(0, 0)
      true
  """
  def divides(a, 0) when is_integer(a), do: true
  def divides(0, b) when is_integer(b), do: false
  def divides(a, b) when is_integer(a) and is_integer(b), do: rem(b, a) == 0
  
  @doc """
  Solves the linear congruence ax = b (mod m).
  
  ## Examples
  
      iex> Caustic.Utils.linear_congruence_solve(1, 3, 4)
      [3]
      iex> Caustic.Utils.linear_congruence_solve(2, 1, 4)
      []
      iex> Caustic.Utils.linear_congruence_solve(2, 6, 4)
      [1, 3]
      iex> Caustic.Utils.linear_congruence_solve(0, 0, 3)
      [0, 1, 2]
      iex> Caustic.Utils.linear_congruence_solve(0, 1, 3)
      []
      iex> Caustic.Utils.linear_congruence_solve(0, 2, 3)
      []
      iex> Caustic.Utils.linear_congruence_solve(0, 3, 3)
      [0, 1, 2]
    
  """
  def linear_congruence_solve(a, b, m) when is_integer(a) and is_integer(m) and m > 0 do
    b = mod(b, m)
    d = gcd(a, m)
    if divides(d, b) do
      _linear_congruence_solve a, b, m, m
    else
      []
    end
  end

  defp _linear_congruence_solve(1, b, m, m_orig) do
    _linear_congruence_solutions [b], m, m_orig
  end
  
  defp _linear_congruence_solve(0, 0, _, m_orig) do
    _linear_congruence_solutions [0], 1, m_orig
  end
  
  defp _linear_congruence_solve(a, b, m, m_orig) do
    d = gcd(a, b)
    if d == 1 do
      _linear_congruence_solve a, b + m, m, m_orig
    else
      m = gcd(d, m)
      _linear_congruence_solve div(a, d), div(b, d), m, m_orig
    end
  end
  
  defp _linear_congruence_solutions(ns = [n | _], m, m_orig) when n + m >= m_orig do
    Enum.reverse(ns)
  end
  
  defp _linear_congruence_solutions(ns = [n | _], m, m_orig) do
    _linear_congruence_solutions [n + m | ns], m, m_orig
  end
  
  def multiplication_table_mod_print(m) do
    table = multiplication_table_mod m
    
    row_labels = 0..(m - 1) |> Enum.to_list()
    col_labels = row_labels
    
    print_table(table, row_labels, col_labels)
  end
  
  def multiplication_table_mod(m) when is_integer(m) and m > 0 do
    0..(m - 1)
    |> Enum.map(fn n ->
      0..(m - 1)
      |> Enum.map(& mod(n * &1, m))
    end)
  end
  
  def exponentiation_table_mod(m) when is_integer(m) and m > 0 do
    residues = 0..(m - 1)
    exponentiation_table_mod(m, residues, residues)
  end

  # technically with m=1, any number is congruent to 0
  # but rather than displaying 1^1=0 (mod 1) it's cleaner to display 1^1=1 (mod 1)
  def exponentiation_table_mod(1, [1], [1]), do: [[1]]

  def exponentiation_table_mod(m, rows, cols) when is_integer(m) and m > 0 do
    rows
    |> Enum.map(fn n ->
      cols
      |> Enum.map(fn
        e when n == 0 and e == 0 -> "?"
        e -> pow_mod(n, e, m)
      end)
    end)
  end

  def exponentiation_table_mod_print(m, opts \\ [relatively_prime_only: false]) do
    rows = if opts[:relatively_prime_only] do
      max = if m == 1, do: 1, else: m - 1
      1..max |> Enum.filter(& gcd(&1, m) == 1) |> Enum.to_list()
    else
      0..(m - 1) |> Enum.to_list()
    end

    cols = if opts[:relatively_prime_only] do
      1..totient(m) |> Enum.to_list()
    else
      max = if m == 1, do: 1, else: m - 1
      0..max |> Enum.to_list()
    end
    
    table = exponentiation_table_mod m, rows, cols
    table = if opts[:relatively_prime_only] do
      _mark_primitive_root table
    else
      table
    end

    print_table table, rows, cols ++ ["√"]
  end
  
  defp _mark_primitive_root table do
    table
    |> Enum.map(fn row ->
      one_count = row
      |> Enum.filter(& &1 == 1)
      |> Enum.count()
      is_root = one_count == 1
      row ++ [(if is_root, do: "*", else: " ")]
    end)
  end
  
  def print_fn(n, f) do
    f_n = n |> Enum.map(& f.(&1))
    n = if is_list(n), do: n, else: Enum.to_list(n)
    print_table([f_n], ["f(n)"], n)
  end

  def print_fn(n, f, g) do
    f_n = n |> Enum.map(& f.(&1))
    g_n = n |> Enum.map(& g.(&1))
    n = if is_list(n), do: n, else: Enum.to_list(n)
    print_table([f_n, g_n], ["f(n)", "g(n)"], n)
  end
  
  def print_table(table, row_labels, col_labels) do
    table_with_row_label = Enum.zip(row_labels, table)
    |> Enum.map(fn {row_label, row} -> [row_label | row] end)
    
    col_labels = ["" | col_labels]
    table_with_label = [col_labels | table_with_row_label]
    
    col_widths = List.zip(table_with_label)
    |> Enum.map(fn row ->
      row
      |> Tuple.to_list()
      |> Enum.map(&String.length(to_string(&1)))
      |> Enum.max()
    end)
    
    table_str = table_with_label
    |> Enum.map(fn row ->
      Enum.zip(row, col_widths)
      |> Enum.map(fn {col, width} -> String.pad_leading(to_string(col), width) end)
      |> Enum.join(" | ")
    end)
    |> Enum.join("\n")
    
    IO.puts(table_str)
  end
  
  @doc """
  Gets all the positive divisors of a number.
  
  ## Examples
  
      iex> Caustic.Utils.positive_divisors(1)
      [1]
      iex> Caustic.Utils.positive_divisors(3)
      [1, 3]
      iex> Caustic.Utils.positive_divisors(6)
      [1, 2, 3, 6]
      iex> Caustic.Utils.positive_divisors(-4)
      [1, 2, 4]
  """
  def positive_divisors(n) when is_number(n) and n > 0 do
    {factors, exponents} = Enum.unzip factorize_grouped n

    result = exponents
    |> Enum.map(&Enum.to_list(0..&1))
    |> select()
    |> Enum.map(fn e ->
      Enum.zip(factors, e)
      |> Enum.map(fn {a, e} -> pow(a, e) end)
      |> Enum.reduce(1, &*/2)
    end)
    |> Enum.sort()
    
    if result == [], do: [1], else: result
  end
  
  def positive_divisors(n) when is_number(n) and n < 0, do: positive_divisors(-n)
  
  @doc """
  ## Examples
  
      iex> Caustic.Utils.select([[:a, :b], [1, 2, 3]])
      [[:a, 1], [:a, 2], [:a, 3], [:b, 1], [:b, 2], [:b, 3]]
    
      iex> Caustic.Utils.select([[["hello"], ["bye"]], ["world"]])
      [[["hello"], "world"], [["bye"], "world"]]
  """
  def select([]), do: []
  def select([first | rest]) do
    _select rest, Enum.map(first, & [&1])
  end
  
  defp _select([], result), do: Enum.map(result, & Enum.reverse(&1))
  defp _select([next | rest], []), do: _select(rest, [next])
  defp _select([next | rest], result) do
    result = result
    |> Enum.flat_map(& Enum.map(next, fn n -> [n | &1] end))
    _select(rest, result)
  end
  
  @doc """
  Counts how many positive divisors an integer has. `d(n)`.
  
  ## Examples
  
      iex> Caustic.Utils.positive_divisors_count(1)
      1
      iex> Caustic.Utils.positive_divisors_count(3)
      2
      iex> Caustic.Utils.positive_divisors_count(6)
      4
  """
  def positive_divisors_count(n) do
    factorize_grouped(n)
    |> Enum.reduce(1, fn {_, e}, acc -> acc * (e + 1) end)
  end

  @doc """
  Sums the positive divisors of an integer. `σ(n)`.
  
  ## Examples
  
      iex> Caustic.Utils.positive_divisors_sum(1)
      1
      iex> Caustic.Utils.positive_divisors_sum(3)
      4
      iex> Caustic.Utils.positive_divisors_sum(6)
      12
  """
  def positive_divisors_sum(n) when n > 0 do
    factorize_grouped(n)
    |> Enum.reduce(1, fn {p, e}, acc -> acc * div((pow(p, e + 1) - 1), (p - 1)) end)
  end
  def positive_divisors_sum(0), do: :infinity
  def positive_divisors_sum(n) when n < 0 do
    positive_divisors_sum(-n)
  end
  
  def proper_divisors_sum(n) when n > 0 do
    positive_divisors_sum(n) - n
  end
  def proper_divisors_sum(0), do: :infinity
  
  @doc """
  The smallest number `t` such that `a^t = 1 (mod m)`.
  """
  def order_multiplicative(n, m) do
    if gcd(n, m) != 1, do: nil, else: _order_multiplicative(n, m)
  end
  
  defp _order_multiplicative(n, m) do
    totient(m)
    |> positive_divisors()
    |> Enum.reduce(nil, fn
      candidate, nil -> if pow_mod(n, candidate, m) == 1, do: candidate, else: nil
      _, result -> result
    end)
  end
  
  @doc """
  Finds the primitive roots of a positive integer `m`.
  `a` is a primitive root of an integer `m` if `a` is a least residue
  and has order (`mod m`) of `t = φ(n)`.
  This means that `t` is the smallest number such that `a^t = 1 (mod m)`.
  """
  def primitive_roots(m) do
    1..m
    |> Enum.filter(&primitive_root?(&1, m))
  end
  
  def primitive_root?(n, m) when is_integer(m) and m > 0 do
    _primitive_root?(n, m)
  end
  
  # must be least residue
  def _primitive_root?(n, m) when n < 0 or n >= m, do: false
  
  def _primitive_root?(n, m), do: order_multiplicative(n, m) == totient(m)

  @doc """
  Finds all subsets of a set (represented by a keyword list).

  ## Examples

      iex> Caustic.Utils.subsets([:a])
      [[], [:a]]
      iex> Caustic.Utils.subsets([:a, :b, :c])
      [[], [:a], [:b], [:c], [:a, :b], [:a, :c], [:b, :c], [:a, :b, :c]]
  """
  def subsets(s) do
    (0..length(s))
    |> Enum.flat_map(& subsets(s, &1))
  end

  @doc """
  Finds all subsets with cardinality `n` of a set (represented by a keyword list).

  ## Examples

      iex> members = ["nakai", "kusanagi", "mori", "kimura", "katori", "inagaki"]
      iex> Caustic.Utils.subsets(members, 3)
      [
        ["nakai", "kusanagi", "mori"],
        ["nakai", "kusanagi", "kimura"],
        ["nakai", "kusanagi", "katori"],
        ["nakai", "kusanagi", "inagaki"],
        ["nakai", "mori", "kimura"],
        ["nakai", "mori", "katori"],
        ["nakai", "mori", "inagaki"],
        ["nakai", "kimura", "katori"],
        ["nakai", "kimura", "inagaki"],
        ["nakai", "katori", "inagaki"],
        ["kusanagi", "mori", "kimura"],
        ["kusanagi", "mori", "katori"],
        ["kusanagi", "mori", "inagaki"],
        ["kusanagi", "kimura", "katori"],
        ["kusanagi", "kimura", "inagaki"],
        ["kusanagi", "katori", "inagaki"],
        ["mori", "kimura", "katori"],
        ["mori", "kimura", "inagaki"],
        ["mori", "katori", "inagaki"],
        ["kimura", "katori", "inagaki"]
      ]
  """
  def subsets(s, n) when n >= 0 do
    _subsets([], [{[], s, n}])
  end

  def _subsets(result, []), do: Enum.reverse(result)

  def _subsets(result, [{_chosen, candidates, n} | pattern_rest]) when n > length(candidates) do
    _subsets(result, pattern_rest)
  end

  def _subsets(result, [{chosen, candidates, n} | pattern_rest]) when n == length(candidates) do
    _subsets([Enum.reverse(chosen) ++ candidates | result], pattern_rest)
  end

  def _subsets(result, [{chosen, _candidates, n} | pattern_rest]) when n == 0 do
    _subsets([Enum.reverse(chosen) | result], pattern_rest)
  end

  def _subsets(result, [{chosen, [candidate | candidates_rest], n} | pattern_rest]) do
    pattern_1 = {[candidate | chosen], candidates_rest, n - 1}
    pattern_2 = {chosen, candidates_rest, n}
    _subsets(result, [pattern_1, pattern_2] ++ pattern_rest)
  end
  
  def factorial(0), do: 1
  def factorial(n), do: n * factorial(n - 1)

  def pmap(collection, func) do
    collection
    |> Enum.map(&(Task.async(fn -> func.(&1) end)))
    |> Enum.map(&Task.await/1)
  end
end