How many integer partitions of a googol (10^100) into at most 60 parts

2011-07-23T22:30:22Z

[Ed. Prof. Zeilberger has explained why he was asking this question. In joint work with Sills he had developed one approach to this problem, and he asked this question to see how this method compared to the current state of the art. Thus in order to be most useful, answers should explain a technique for computing the number of partitions of a given number and explain how quickly that technique works on large numbers.]

I am offering $100 (one hundred US dollars) for the EXACT number of integer-partitions of 10^100 (googol) into at most 60 parts. The answer has to come by 23:59:59 Sat. July 30, 2011, by Email to zeilberg at math dot rutgers dot edu . The first correct answer would get the prize. Please have

Subject: MathIsFun; Computational Challenge for p_60(10^100) ;

Of course, the answer should also be posted on mathoverflow, this way people would know that it has been answered.

P.S. A quick reminder, the number in question is the coefficient of q^(10^100) in the Maclaurin expansion of 1/((1-q)(1-q^2)(1-q^3) .....(1-q^60))

Answer by joro for How many integer partitions of a googol (10^100) into at most 60 parts

2011-07-24T15:37:08Z

Assuming the generating function is $\frac{1}{\prod\limits_{k=1}^{60}{(1-x^k)}}$ less than two hours of gp/pari computations gave the 5738 digit answer:

  p_60(10^100) =86656581294960581213175060679076908106704497466613021789269100257198717639235565191312316339492985931775559063255086528837813739104710297888706131590925777147446992989596305426558684312353832935177854304281051434707642789976633357008073006172513802039605620390971530655957695816047373679324636257282106902902642334621092094495020475520840128975825078563529533721223665030014973823745969613836273106408827327620882478583495948350012091274039702064403585282561588485459886814177864772537183125213711100412687405422437352195598054377411587222269453652608772595749758879318654363237967684143231492819869859849144643303192846597868095662984235221075244178993104547452731511881759746102529420779361469502083053597121420547771297370551721671548302500091286893415042409909386976998366647667730271589358498087377526580681061646805629741775292578165923941705511503682125111965696369869537104454897622661946756673714986529163822467578554047245492495510507170090948586721472176087890067187205068847873944550040070916438551321351396516213312259752977287529254685370643911843047105714953040605284080636692506692852386290861343553224074351341717615684759689286925891931418713944578600404523388228164949290655986905260347937245272959342219230306425929769819674715342009178833416712244795668148759773978550600441248548844394745844052334403899748841438534047816714279171794504022130682781281338860748886310942696518241739354639469191565831755281487651975490310571755217751161614063490987562368769323044232577035098658230233013237255973046519611557796486164097780600572765717192049207954645676522794492200060665810654697408765940922890681071570384648258924284066002369593013417037460844987760581310856784498330666017867379926932694902997867177534401534253516077108815999378705993544948398373531228390862058340486152600008916251487948597447302087222445574918132585218917475956102854139673493135870736987796597089097002154332556076681792911960393717282441400003891789494260210518618598398188973314601719313940864500046963578450894149843678435403526369044654570577736547494560409713817349951247573596666312987608479125353084495156167369686044416320507047788675965257815987123582326728091964213648779393844782376881912696986212395145284269498793326663270251644721155827704955889017550948057150607407340515621974551535912800395378923117298039858992279692113890732218616186715963928401879310471182014398714662911530318387903719384123094503523206696497344490492638446160520515345185475243301577733068288864511852204443105974689867573265717663992266843175679920468623776646192750361660066693548858340497070820836336832199589479748493873317664342726797884461623034017101485138334977039474244928106432671579231185307999275082811493423960476932458859071426598186180193873112974561741389243099450104083630784275091797080843197458051593402628198584022892884659157159673262136007475012211642068258586790111983004487115216316587714983184061600620955510042347951208525065607903584615122754411093720333997372104303686158116390169328647564729654602496822021852772627790051147655497081758653708323731069376329211820329894720964292204308512951279394392815381531228647996748926021980587998964261559656789935515903400714034275245390786720943646069317133415476977019995552930699089095507184260562010127210662513680400195596743618969063736866638772821443713466075147525295691845979077397586672472600601543352722962465248875034380223555307587552833073676295297462269930775994370058825449794499092333098572763536845613567842007659729575950101377792470604573148496958694358500851681021020417594633650488157803555292646903284496164708723320577897705653022386786879215494849887211690867003601123525598841552234310761205697727878524537734677467073785042424099919327513045482888697810675989587429823477178875557088606857135477182172185015519236919521892931144178066734476513787554644960056748117699500499619773294247239228662598512935502836101729578744392303964471746249068504824095375264500084786240673237030325688054879312901256140411126019876717562604656695370754259610380124733596290494150939078833029847277734279848103655035634005537012357440970178134041530010383962758911236744087548957247418495385838344050488193120198883656103937944047482394289200718538660178091001587195284171526798215466184392607070866663303013384407124487552431242699246058135314350852485524272063343281779127361940425132806724989541986633960769535303122467306918016412450564031174033910533590190086814981425286256620935490998866145273905397216624258819860307507105774061029397025943293906050905675435357400232306328073568576501790379120117667898974043944187447981387549878960713202932947775104921101559396576930010856892403392376903132049196798179726054506703688678257002906484375930174337243347713509605577865904845933780545352176065540746989843910448263598464743883743439272998551440273145595918471962680847257889187644711316597456792335590005247303224359521888113127081850435754309177603997607819802516595862380433682384768629515466542262017881243664146776012340346962436435902670624415630984638855161435213820664151078798248565386059057915029104772346437888653030556324179188240674032973292350468414546941023474634728292600948182617121556982271419859775728848796694902653386079448715972566638129584559954562361057167423402068307675741886341592218981106331969215861131581250781124740005504878113203950194519164264383901294959862497186017815081914576467308984426624348931287895061495731260738434212734724426778408532295618503758135224149897249857036284783900183976954684955435242114417114172532305756633722611320470393047211480479720666959127636504139868217145958399715530772463153560598077341901760982207337893156549165428179577945947050066009093850246495381004264287660200535241771035068278713633310388540

I am not sure this is correct at all, yet Doron seems happy.

EDIT: Here is how the number was computed. The generating function $\frac{1}{\prod\limits_{k=1}^{60}{(1-x^k)}}$ means the sequence satisfies linear recurrence with constant coefficients. These are known to be efficiently computable assuming arithmetic operations in the range of the result are tractable. A good computational resource for recurrences is the free book "Matters Computational" was: "Algorithms for Programmers" by Jörg Arndt. Basically the method is fast binary exponentiation of a matrix or in $\mathbb{Z}[x]/poly(x)$. The book has code parts of which I used. Got a linear recurrence of order 1830. My gp/pari code is here. A curiosity of the challenge is the result is so small - I wouldn't even try $fibonacci(10^{100})$.

To my knowledge the monetary bounty was donated to Wikipedia by Doron Zeilberger per agreement with the recipient.

EDIT2 A closed form possibly leading to faster approach (avoiding computing the recurrence) appears in the paper A GENERAL METHOD FOR DETERMINING A CLOSED FORMULA FOR THE NUMBER OF PARTITIONS OF THE INTEGER $n$ INTO $m$ POSITIVE INTEGERS FOR SMALL VALUES OF $m$, W. J. A. COLMAN

Answer by Peter for How many integer partitions of a googol (10^100) into at most 60 parts

2011-07-24T17:27:17Z

Can you do p_60(10^1000)? p_60(10^10000)? – Doron Zeilberger

8.6656581294960581213175060679076908106704497466613.. * 10^5737 Dollar 100 8.6656581294960581213175060679076908106704497466613.. * 10^58837 Dollar 1000 8.6656581294960581213175060679076908106704497466613.. * 10^589837 Dollar 10000

How many integer partitions of a googol (10^100) into at most 60 parts - MathOverflow

How many integer partitions of a googol (10^100) into at most 60 parts

Answer by joro for How many integer partitions of a googol (10^100) into at most 60 parts

Answer by Peter for How many integer partitions of a googol (10^100) into at most 60 parts