How many integer partitions of a googol (10^100) into at most 60 parts - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T19:59:50Z http://mathoverflow.net/feeds/question/71092 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/71092/how-many-integer-partitions-of-a-googol-10100-into-at-most-60-parts How many integer partitions of a googol (10^100) into at most 60 parts Doron Zeilberger 2011-07-23T22:30:22Z 2011-08-12T03:46:42Z <p>[<strong>Ed.</strong> Prof. Zeilberger has <a href="http://meta.mathoverflow.net/discussion/1091/3/how-many-integer-partitions-of-a-googol-10100-into-at-most-60-parts/#Item_27" rel="nofollow">explained</a> 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.]</p> <p>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</p> <p>Subject: MathIsFun; Computational Challenge for p_60(10^100) ;</p> <p>Of course, the answer should also be posted on mathoverflow, this way people would know that it has been answered.</p> <p>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))</p> http://mathoverflow.net/questions/71092/how-many-integer-partitions-of-a-googol-10100-into-at-most-60-parts/71132#71132 Answer by joro for How many integer partitions of a googol (10^100) into at most 60 parts joro 2011-07-24T15:37:08Z 2011-08-09T08:57:22Z <p>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> <pre><code> p_60(10^100) =86656581294960581213175060679076908106704497466613021789269100257198717639235565191312316339492985931775559063255086528837813739104710297888706131590925777147446992989596305426558684312353832935177854304281051434707642789976633357008073006172513802039605620390971530655957695816047373679324636257282106902902642334621092094495020475520840128975825078563529533721223665030014973823745969613836273106408827327620882478583495948350012091274039702064403585282561588485459886814177864772537183125213711100412687405422437352195598054377411587222269453652608772595749758879318654363237967684143231492819869859849144643303192846597868095662984235221075244178993104547452731511881759746102529420779361469502083053597121420547771297370551721671548302500091286893415042409909386976998366647667730271589358498087377526580681061646805629741775292578165923941705511503682125111965696369869537104454897622661946756673714986529163822467578554047245492495510507170090948586721472176087890067187205068847873944550040070916438551321351396516213312259752977287529254685370643911843047105714953040605284080636692506692852386290861343553224074351341717615684759689286925891931418713944578600404523388228164949290655986905260347937245272959342219230306425929769819674715342009178833416712244795668148759773978550600441248548844394745844052334403899748841438534047816714279171794504022130682781281338860748886310942696518241739354639469191565831755281487651975490310571755217751161614063490987562368769323044232577035098658230233013237255973046519611557796486164097780600572765717192049207954645676522794492200060665810654697408765940922890681071570384648258924284066002369593013417037460844987760581310856784498330666017867379926932694902997867177534401534253516077108815999378705993544948398373531228390862058340486152600008916251487948597447302087222445574918132585218917475956102854139673493135870736987796597089097002154332556076681792911960393717282441400003891789494260210518618598398188973314601719313940864500046963578450894149843678435403526369044654570577736547494560409713817349951247573596666312987608479125353084495156167369686044416320507047788675965257815987123582326728091964213648779393844782376881912696986212395145284269498793326663270251644721155827704955889017550948057150607407340515621974551535912800395378923117298039858992279692113890732218616186715963928401879310471182014398714662911530318387903719384123094503523206696497344490492638446160520515345185475243301577733068288864511852204443105974689867573265717663992266843175679920468623776646192750361660066693548858340497070820836336832199589479748493873317664342726797884461623034017101485138334977039474244928106432671579231185307999275082811493423960476932458859071426598186180193873112974561741389243099450104083630784275091797080843197458051593402628198584022892884659157159673262136007475012211642068258586790111983004487115216316587714983184061600620955510042347951208525065607903584615122754411093720333997372104303686158116390169328647564729654602496822021852772627790051147655497081758653708323731069376329211820329894720964292204308512951279394392815381531228647996748926021980587998964261559656789935515903400714034275245390786720943646069317133415476977019995552930699089095507184260562010127210662513680400195596743618969063736866638772821443713466075147525295691845979077397586672472600601543352722962465248875034380223555307587552833073676295297462269930775994370058825449794499092333098572763536845613567842007659729575950101377792470604573148496958694358500851681021020417594633650488157803555292646903284496164708723320577897705653022386786879215494849887211690867003601123525598841552234310761205697727878524537734677467073785042424099919327513045482888697810675989587429823477178875557088606857135477182172185015519236919521892931144178066734476513787554644960056748117699500499619773294247239228662598512935502836101729578744392303964471746249068504824095375264500084786240673237030325688054879312901256140411126019876717562604656695370754259610380124733596290494150939078833029847277734279848103655035634005537012357440970178134041530010383962758911236744087548957247418495385838344050488193120198883656103937944047482394289200718538660178091001587195284171526798215466184392607070866663303013384407124487552431242699246058135314350852485524272063343281779127361940425132806724989541986633960769535303122467306918016412450564031174033910533590190086814981425286256620935490998866145273905397216624258819860307507105774061029397025943293906050905675435357400232306328073568576501790379120117667898974043944187447981387549878960713202932947775104921101559396576930010856892403392376903132049196798179726054506703688678257002906484375930174337243347713509605577865904845933780545352176065540746989843910448263598464743883743439272998551440273145595918471962680847257889187644711316597456792335590005247303224359521888113127081850435754309177603997607819802516595862380433682384768629515466542262017881243664146776012340346962436435902670624415630984638855161435213820664151078798248565386059057915029104772346437888653030556324179188240674032973292350468414546941023474634728292600948182617121556982271419859775728848796694902653386079448715972566638129584559954562361057167423402068307675741886341592218981106331969215861131581250781124740005504878113203950194519164264383901294959862497186017815081914576467308984426624348931287895061495731260738434212734724426778408532295618503758135224149897249857036284783900183976954684955435242114417114172532305756633722611320470393047211480479720666959127636504139868217145958399715530772463153560598077341901760982207337893156549165428179577945947050066009093850246495381004264287660200535241771035068278713633310388540 </code></pre> <p>I am not sure this is correct at all, yet Doron seems happy.</p> <p><strong>EDIT</strong>: 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 <a href="http://www.jjj.de/fxt/fxtpage.html#fxtbook" rel="nofollow">"Matters Computational" was: "Algorithms for Programmers"</a> by Jörg Arndt. Basically the method is fast binary exponentiation of a matrix or in$\mathbb{Z}[x]/poly(x)$. The book has <a href="http://www.jjj.de/pari/" rel="nofollow">code</a> parts of which I used. Got a linear recurrence of order 1830. My gp/pari code is <a href="http://pastebin.com/rpCSgvZw" rel="nofollow">here</a>. A curiosity of the challenge is the result is so small - I wouldn't even try$fibonacci(10^{100})$.</p> <p>To my knowledge the monetary bounty was donated to Wikipedia by Doron Zeilberger per agreement with the recipient.</p> <p><strong>EDIT2</strong> A closed form possibly leading to faster approach (avoiding computing the recurrence) appears in the <a href="http://www.fq.math.ca/Scanned/21-4/colman.pdf" rel="nofollow">paper</a> 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</p> http://mathoverflow.net/questions/71092/how-many-integer-partitions-of-a-googol-10100-into-at-most-60-parts/71136#71136 Answer by Peter for How many integer partitions of a googol (10^100) into at most 60 parts Peter 2011-07-24T17:27:17Z 2011-07-24T17:35:08Z <p>Can you do p_60(10^1000)? p_60(10^10000)? – Doron Zeilberger</p> <p>8.6656581294960581213175060679076908106704497466613.. * 10^5737 Dollar 100 8.6656581294960581213175060679076908106704497466613.. * 10^58837 Dollar 1000 8.6656581294960581213175060679076908106704497466613.. * 10^589837 Dollar 10000</p>