19
$\begingroup$

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

Improve this question
$\endgroup$
27
  • 17
    $\begingroup$ 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. $\endgroup$
    – Joe Silverman
    Commented Jul 23, 2011 at 23:17
  • 8
    $\begingroup$ 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. $\endgroup$
    – Steve Huntsman
    Commented Jul 23, 2011 at 23:17
  • 13
    $\begingroup$ Actually, I'm voting against closing. $\endgroup$
    – André Henriques
    Commented Jul 23, 2011 at 23:30
  • 15
    $\begingroup$ tea.mathoverflow.net/discussion/1091/… $\endgroup$
    – Steve Huntsman
    Commented Jul 23, 2011 at 23:41
  • 28
    $\begingroup$ Doron, now that the problem was solved and the solution was confirmed, what was your point/motivation to start with? $\endgroup$
    – Gil Kalai
    Commented Jul 24, 2011 at 19:18

2 Answers 2

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 4
    $\begingroup$ 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. $\endgroup$
    – Doron Zeilberger
    Commented Jul 28, 2011 at 0:39
  • 1
    $\begingroup$ I failed to compute p_60(10^1000) in 12 hours. $\endgroup$
    – joro
    Commented Jul 28, 2011 at 18:47
  • $\begingroup$ Doron, after the symbol cranching stage once the quasi-polynomial expression was found, how quickly can shalosh compute p_60(10,000) $\endgroup$
    – Gil Kalai
    Commented Jul 28, 2011 at 20:46
  • 6
    $\begingroup$ 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. $\endgroup$
    – Doron Zeilberger
    Commented Aug 7, 2011 at 19:51
  • 3
    $\begingroup$ A link to the Sills-Zeilberger paper, which appeared recently on the arXiv: arxiv.org/abs/1108.4391 $\endgroup$
    – Abhinav Kumar
    Commented Aug 23, 2011 at 15:11
24
$\begingroup$

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

Improve this answer
$\endgroup$
10
  • 9
    $\begingroup$ @Doron, please try math.stackexchange.com ;-) $\endgroup$
    – joro
    Commented Jul 24, 2011 at 17:32
  • 10
    $\begingroup$ 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 :(. $\endgroup$
    – Chao Xu
    Commented Jul 24, 2011 at 18:16
  • 9
    $\begingroup$ 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. $\endgroup$
    – Gil Kalai
    Commented Jul 24, 2011 at 21:10
  • 2
    $\begingroup$ @Gil @Chao explained how the result was computed and gave full source code. $\endgroup$
    – joro
    Commented Jul 27, 2011 at 15:24
  • 2
    $\begingroup$ In sage p_60(10^100) got computed in 24 minutes : Time: CPU 1245.17 s, Wall: 1392.92 s $\endgroup$
    – joro
    Commented Jul 28, 2011 at 7:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .