Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

[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))

share|improve this question
17  
This qualifies as "Math Is Fun", but I'm wondering if MathOverflow is really the right place. Doron, I assume that you know the answer, since otherwise how will you check that someone's answer is correct. MathOverflow is designed for people to ask questions to which they do not know the answer, in order to enlist the aid of the MO community. And posting an answer on MO is, to my mind, not a very useful thing. What might be useful would be to post an explanation of how one does the calculation. Anyway, I'm not voting to close, but I question the posting of "challenges" of this sort on MO. –  Joe Silverman Jul 23 '11 at 23:17
8  
First of all, welcome to MO. Second of all, I am voting to close your question (interesting as it may be)--because apparently you already know the answer. –  Steve Huntsman Jul 23 '11 at 23:17
11  
Actually, I'm voting against closing. –  André Henriques Jul 23 '11 at 23:30
15  
27  
Doron, now that the problem was solved and the solution was confirmed, what was your point/motivation to start with? –  Gil Kalai Jul 24 '11 at 19:18
show 22 more comments

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
2  
The further values are also correct, but it is not clear whether Peter had all the digits, or did it with floating point. Joro did a great job, but still it took his computer two hours. Shalosh can do it in two seconds once it found the quasi-polynomial expression for p_60(n), and it found it in 400 seconds. So Shalosh does first symbol-crunching then number-crunching. -Doron Z. –  Doron Zeilberger Jul 28 '11 at 0:39
1  
I failed to compute p_60(10^1000) in 12 hours. –  joro Jul 28 '11 at 18:47
    
Doron, after the symbol cranching stage once the quasi-polynomial expression was found, how quickly can shalosh compute p_60(10,000) –  Gil Kalai Jul 28 '11 at 20:46
4  
Shalom Gil, Good question. I bet you meant p_60(10^(10000)) NOT p_60(10000). Using the Maple package PARTITIONS, soon to be posted in a joint work with Andrew Sills, typing restart: read PARTITIONS: t0:=time():qmn(60,10^10000): time()-t0; gave 3.121 seconds. If you want to actually see the 589838-digit integer, ending in 71918678375357 it took 3.932 seconds. -Doron Z. –  Doron Zeilberger Aug 7 '11 at 19:51
2  
A link to the Sills-Zeilberger paper, which appeared recently on the arXiv: arxiv.org/abs/1108.4391 –  Abhinav Kumar Aug 23 '11 at 15:11
add comment

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

share|improve this answer
9  
@Doron, please try math.stackexchange.com ;-) –  joro Jul 24 '11 at 17:32
10  
I was hoping to see some explanation since I thought this kind of computation is not tractable. This answer is right but doesn't offer any insight :(. –  Chao Xu Jul 24 '11 at 18:16
9  
Since joro is not sure at all if the answer is correct, and since it is still a mystery if Doron knew the answer to start with, and since the correctness of the answer may be irrelevant to Doron's initial point/motivation (which are also mysterious). It would be nice if the answer can be independently confirmed. –  Gil Kalai Jul 24 '11 at 21:10
2  
@Gil @Chao explained how the result was computed and gave full source code. –  joro Jul 27 '11 at 15:24
2  
In sage p_60(10^100) got computed in 24 minutes : Time: CPU 1245.17 s, Wall: 1392.92 s –  joro Jul 28 '11 at 7:37
show 6 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.