Revisions - MathOverflow

Return to Answer

Typos. Paper for possibly faster approach

view source

edited Aug 9 2011 at 8:57

joro
4,260●1●10●31

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

EDIT: Here is how the number was computed. The generating function is $\frac{1}{\prod\limits_{k=1}^{60}{1-x^k}}$ \frac{1}{\prod\limits_{k=1}^{60}{(1-x^k)}}$ means the sequence satisfies linear recurrence with constant coefficients. These are known to be tractable 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 width 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).$fibonacci(10^{100})$.

EDIT2 A closed form possibly leading to faster approach (avoiding computing the recurrence) appears in the paperA 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

Explained the computations per commenters requests

view source

edited Jul 27 2011 at 15:23

joro
4,260●1●10●31

EDIT: Here is how the number was computed. The generating function is $\frac{1}{\prod\limits_{k=1}^{60}{1-x^k}}$ means the sequence satisfies linear recurrence with constant coefficients. These are known to be tractable 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. The book has code parts of which I used. Got a linear recurrence of width 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.

clean up

view source

edited Jul 24 2011 at 20:15

joro
4,260●1●10●31

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

  p_60(10^100) =86656581294960581213175060679076908106704497466613021789269100257198717639235565191312316339492985931775559063255086528837813739104710297888706131590925777147446992989596305426558684312353832935177854304281051434707642789976633357008073006172513802039605620390971530655957695816047373679324636257282106902902642334621092094495020475520840128975825078563529533721223665030014973823745969613836273106408827327620882478583495948350012091274039702064403585282561588485459886814177864772537183125213711100412687405422437352195598054377411587222269453652608772595749758879318654363237967684143231492819869859849144643303192846597868095662984235221075244178993104547452731511881759746102529420779361469502083053597121420547771297370551721671548302500091286893415042409909386976998366647667730271589358498087377526580681061646805629741775292578165923941705511503682125111965696369869537104454897622661946756673714986529163822467578554047245492495510507170090948586721472176087890067187205068847873944550040070916438551321351396516213312259752977287529254685370643911843047105714953040605284080636692506692852386290861343553224074351341717615684759689286925891931418713944578600404523388228164949290655986905260347937245272959342219230306425929769819674715342009178833416712244795668148759773978550600441248548844394745844052334403899748841438534047816714279171794504022130682781281338860748886310942696518241739354639469191565831755281487651975490310571755217751161614063490987562368769323044232577035098658230233013237255973046519611557796486164097780600572765717192049207954645676522794492200060665810654697408765940922890681071570384648258924284066002369593013417037460844987760581310856784498330666017867379926932694902997867177534401534253516077108815999378705993544948398373531228390862058340486152600008916251487948597447302087222445574918132585218917475956102854139673493135870736987796597089097002154332556076681792911960393717282441400003891789494260210518618598398188973314601719313940864500046963578450894149843678435403526369044654570577736547494560409713817349951247573596666312987608479125353084495156167369686044416320507047788675965257815987123582326728091964213648779393844782376881912696986212395145284269498793326663270251644721155827704955889017550948057150607407340515621974551535912800395378923117298039858992279692113890732218616186715963928401879310471182014398714662911530318387903719384123094503523206696497344490492638446160520515345185475243301577733068288864511852204443105974689867573265717663992266843175679920468623776646192750361660066693548858340497070820836336832199589479748493873317664342726797884461623034017101485138334977039474244928106432671579231185307999275082811493423960476932458859071426598186180193873112974561741389243099450104083630784275091797080843197458051593402628198584022892884659157159673262136007475012211642068258586790111983004487115216316587714983184061600620955510042347951208525065607903584615122754411093720333997372104303686158116390169328647564729654602496822021852772627790051147655497081758653708323731069376329211820329894720964292204308512951279394392815381531228647996748926021980587998964261559656789935515903400714034275245390786720943646069317133415476977019995552930699089095507184260562010127210662513680400195596743618969063736866638772821443713466075147525295691845979077397586672472600601543352722962465248875034380223555307587552833073676295297462269930775994370058825449794499092333098572763536845613567842007659729575950101377792470604573148496958694358500851681021020417594633650488157803555292646903284496164708723320577897705653022386786879215494849887211690867003601123525598841552234310761205697727878524537734677467073785042424099919327513045482888697810675989587429823477178875557088606857135477182172185015519236919521892931144178066734476513787554644960056748117699500499619773294247239228662598512935502836101729578744392303964471746249068504824095375264500084786240673237030325688054879312901256140411126019876717562604656695370754259610380124733596290494150939078833029847277734279848103655035634005537012357440970178134041530010383962758911236744087548957247418495385838344050488193120198883656103937944047482394289200718538660178091001587195284171526798215466184392607070866663303013384407124487552431242699246058135314350852485524272063343281779127361940425132806724989541986633960769535303122467306918016412450564031174033910533590190086814981425286256620935490998866145273905397216624258819860307507105774061029397025943293906050905675435357400232306328073568576501790379120117667898974043944187447981387549878960713202932947775104921101559396576930010856892403392376903132049196798179726054506703688678257002906484375930174337243347713509605577865904845933780545352176065540746989843910448263598464743883743439272998551440273145595918471962680847257889187644711316597456792335590005247303224359521888113127081850435754309177603997607819802516595862380433682384768629515466542262017881243664146776012340346962436435902670624415630984638855161435213820664151078798248565386059057915029104772346437888653030556324179188240674032973292350468414546941023474634728292600948182617121556982271419859775728848796694902653386079448715972566638129584559954562361057167423402068307675741886341592218981106331969215861131581250781124740005504878113203950194519164264383901294959862497186017815081914576467308984426624348931287895061495731260738434212734724426778408532295618503758135224149897249857036284783900183976954684955435242114417114172532305756633722611320470393047211480479720666959127636504139868217145958399715530772463153560598077341901760982207337893156549165428179577945947050066009093850246495381004264287660200535241771035068278713633310388540I am not sure this is correct at all:-), yet Doron seems happy.

view source

answered Jul 24 2011 at 15:37

joro
4,260●1●10●31

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

  n=86656581294960581213175060679076908106704497466613021789269100257198717639235565191312316339492985931775559063255086528837813739104710297888706131590925777147446992989596305426558684312353832935177854304281051434707642789976633357008073006172513802039605620390971530655957695816047373679324636257282106902902642334621092094495020475520840128975825078563529533721223665030014973823745969613836273106408827327620882478583495948350012091274039702064403585282561588485459886814177864772537183125213711100412687405422437352195598054377411587222269453652608772595749758879318654363237967684143231492819869859849144643303192846597868095662984235221075244178993104547452731511881759746102529420779361469502083053597121420547771297370551721671548302500091286893415042409909386976998366647667730271589358498087377526580681061646805629741775292578165923941705511503682125111965696369869537104454897622661946756673714986529163822467578554047245492495510507170090948586721472176087890067187205068847873944550040070916438551321351396516213312259752977287529254685370643911843047105714953040605284080636692506692852386290861343553224074351341717615684759689286925891931418713944578600404523388228164949290655986905260347937245272959342219230306425929769819674715342009178833416712244795668148759773978550600441248548844394745844052334403899748841438534047816714279171794504022130682781281338860748886310942696518241739354639469191565831755281487651975490310571755217751161614063490987562368769323044232577035098658230233013237255973046519611557796486164097780600572765717192049207954645676522794492200060665810654697408765940922890681071570384648258924284066002369593013417037460844987760581310856784498330666017867379926932694902997867177534401534253516077108815999378705993544948398373531228390862058340486152600008916251487948597447302087222445574918132585218917475956102854139673493135870736987796597089097002154332556076681792911960393717282441400003891789494260210518618598398188973314601719313940864500046963578450894149843678435403526369044654570577736547494560409713817349951247573596666312987608479125353084495156167369686044416320507047788675965257815987123582326728091964213648779393844782376881912696986212395145284269498793326663270251644721155827704955889017550948057150607407340515621974551535912800395378923117298039858992279692113890732218616186715963928401879310471182014398714662911530318387903719384123094503523206696497344490492638446160520515345185475243301577733068288864511852204443105974689867573265717663992266843175679920468623776646192750361660066693548858340497070820836336832199589479748493873317664342726797884461623034017101485138334977039474244928106432671579231185307999275082811493423960476932458859071426598186180193873112974561741389243099450104083630784275091797080843197458051593402628198584022892884659157159673262136007475012211642068258586790111983004487115216316587714983184061600620955510042347951208525065607903584615122754411093720333997372104303686158116390169328647564729654602496822021852772627790051147655497081758653708323731069376329211820329894720964292204308512951279394392815381531228647996748926021980587998964261559656789935515903400714034275245390786720943646069317133415476977019995552930699089095507184260562010127210662513680400195596743618969063736866638772821443713466075147525295691845979077397586672472600601543352722962465248875034380223555307587552833073676295297462269930775994370058825449794499092333098572763536845613567842007659729575950101377792470604573148496958694358500851681021020417594633650488157803555292646903284496164708723320577897705653022386786879215494849887211690867003601123525598841552234310761205697727878524537734677467073785042424099919327513045482888697810675989587429823477178875557088606857135477182172185015519236919521892931144178066734476513787554644960056748117699500499619773294247239228662598512935502836101729578744392303964471746249068504824095375264500084786240673237030325688054879312901256140411126019876717562604656695370754259610380124733596290494150939078833029847277734279848103655035634005537012357440970178134041530010383962758911236744087548957247418495385838344050488193120198883656103937944047482394289200718538660178091001587195284171526798215466184392607070866663303013384407124487552431242699246058135314350852485524272063343281779127361940425132806724989541986633960769535303122467306918016412450564031174033910533590190086814981425286256620935490998866145273905397216624258819860307507105774061029397025943293906050905675435357400232306328073568576501790379120117667898974043944187447981387549878960713202932947775104921101559396576930010856892403392376903132049196798179726054506703688678257002906484375930174337243347713509605577865904845933780545352176065540746989843910448263598464743883743439272998551440273145595918471962680847257889187644711316597456792335590005247303224359521888113127081850435754309177603997607819802516595862380433682384768629515466542262017881243664146776012340346962436435902670624415630984638855161435213820664151078798248565386059057915029104772346437888653030556324179188240674032973292350468414546941023474634728292600948182617121556982271419859775728848796694902653386079448715972566638129584559954562361057167423402068307675741886341592218981106331969215861131581250781124740005504878113203950194519164264383901294959862497186017815081914576467308984426624348931287895061495731260738434212734724426778408532295618503758135224149897249857036284783900183976954684955435242114417114172532305756633722611320470393047211480479720666959127636504139868217145958399715530772463153560598077341901760982207337893156549165428179577945947050066009093850246495381004264287660200535241771035068278713633310388540

I am not sure this is correct at all :-)