User doron zeilberger - MathOverflow

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 Doron Zeilberger for Help with a double sum, please

2010-05-04T14:33:53Z

Olivier Gerard just told me about this wonderful website! Regarding the question it can be done in one nano-second using the Maple package

http://www.math.rutgers.edu/~zeilberg/tokhniot/MultiZeilberger

accopmaying my article with Moa Apagodu

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/multiZ.html

Here is the command:

F:=(-1)^k*binomial(m,k)*(k+m-1-j)!/(k+m)!*simplify((k+m-1/2)!/(k+m-1/2-j)!)/2^(k-j): lprint(MulZeil(F,[j,k],m,M,{})[1]);

and here is the output: -1/4*(2*m+1)/(m+1)+M

(Note that I had to divide the summand by 1/2^(m+1) if you don't you get FAIL, the prgram does not like extraneous factors)

Translated to humaneze we have that (my S(m) is hte original S(m) times 2^(m+1)) S(m+1)=(2m+1)/(m+1)S(m)

Since S(1)=0 (check!) This is a completely rigorous proof.

P.S. The proof can be gotten by finding the so-called multi-certificate

lprint(MulZeil(F,[j,k],m,M,{})[2]);

-Doron Zeilbeger

Comment by Doron Zeilberger

2011-08-07T19:51:46Z

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.

Comment by Doron Zeilberger

2011-07-28T00:39:16Z

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.

Comment by Doron Zeilberger

2011-07-24T16:16:54Z

The answer is correct, Bravo! I am not sure who joro is, but Gerogi Guniski sent me Email a few minutes ago, with the correct answer, and whether he is joro or not, Georgi won the prize! Georgy, Can you do p_60(10^1000)? p_60(10^10000)?