Partition calculation
Bart Goddard
Hi folks,
If you can hear me through all the noise, I've got
a little conundrum.
Let p(n) be the number of integer partitions of
integer n. Euler gave the recursion formula
p(n) = sum_k (-1)^(k+1) ( p(n-k(3k-1)/2) - p(n-k(3k+1)/2) ).
Andres and Eriksson, in _Integer Partitions_ state, without
proof or hint, that using this formula, one can compute
p(n) in O(n^(3/2)) operations. I am unable to verify this
assertion.
If anyone has any hints or references, I'd love to
have them.
In this paper:
Calkin, et al., _almost_ say that this is not true.
I have another informal source that says there's no
faster way to compute p(n) than using the Euler
recurrance.
Bart
--
Cheerfully resisting change since 1959.
Gerry
> Hi folks,
>
> If you can hear me through all the noise, I've got
> a little conundrum.
>
> Let p(n) be the number of integer partitions of
> integer n. Euler gave the recursion formula
>
> p(n) = sum_k (-1)^(k+1) ( p(n-k(3k-1)/2) - p(n-k(3k+1)/2) ).
>
> Andres and Eriksson, in _Integer Partitions_ state, without
> proof or hint, that using this formula, one can compute
> p(n) in O(n^(3/2)) operations. I am unable to verify this
> assertion.
>
> If anyone has any hints or references, I'd love to
> have them.
The sum has O(sqrt n) terms. So, if you had already calculated
p(k) for all k less than n, you'd need O(sqrt n) additions to
get p(n). To calculate all those p(k), you need O(sum sqrt k)
operations, and sum sqrt k is n^(3/2). Does that seem OK?
--
GM
Henry
That deals with the number of operations of addition and
subtraction.
But the time take will be more than O(n^(3/2) for large n because the
average time per operation (using unlimited precision integer
arithmetic) will increase with increasing n. For large n, the number
of digits of p(n) (in binary or decimal) is roughly proportional to
sqrt(n). So overall something like O(n^2) might be more realistic
As an example, using Java code similar to the applet at
http://www.btinternet.com/~se16/js/partitions.htm
(though without the counter or GUI)
took me about 20 seconds to calculate p(1000000) =
27493510569775696512677516320986352688173429315980054758203125984302147328114964173055050741660736621590157844774296248940493063070200461792764493033510116079342457190155718943509725312466108452006369558934464248716828789832182345009262853831404597021307130674510624419227311238999702284408609370935531629697851569569892196108480158600569421098519
but about 75 seconds to calculate p(2000000) =
1142149040516629749037121530402138096853926160881948532505004601437486969047069848233533537228547558093788739002612142642220379461285625596845952597486179818841905527749813150474498721747633064058840437916036245712660272843036962395856213719373419360640609193628394201054990897781263014274799184617869958648852094318304681098737364938930543346705147603014542998991252631960051596213531387338008165217582822943454514251881668474896643416706191144360737225405767060795784657847417376966116043766
Bart Goddard
news:3367c7c9-262e-4fc8...@s9g2000yqd.googlegroups.com:
>> The sum has O(sqrt n) terms. So, if you had already calculated
>> p(k) for all k less than n, you'd need O(sqrt n) additions to
>> get p(n). To calculate all those p(k), you need O(sum sqrt k)
>> operations, and sum sqrt k is n^(3/2). Does that seem OK?
>
> That deals with the number of operations of addition and
> subtraction.
>
> But the time take will be more than O(n^(3/2) for large n because the
> average time per operation
Yeah, that solves my problem. My source meant to say "additions"
rather than "bit operations." I get to do the wasn't-my-fault
dance.
Thanks Gerry and Henry.
Chip Eastham
I did a Prolog implementation of this last year,
and was unable to achieve O(n^1.5) running time
due to language limitations. [Prolog has lists
but not (randomly addressable) arrays.] I'd
suspect that apart from the big-integer arithmetic
the improved running time is fairly easy to get
with pointer arithmetic in languages like C.
Brief mention at the end of this thread in
comp.lang.prolog:
[Is it possible to count solutions that cannot
fit in memory -- comp.lang.prolog]
http://groups.google.com/group/comp.lang.prolog/browse_frm/thread/2d8bf9e8b9a40b7/c8f1c22a9fac7b80?hl=en&lnk=gst&q=+partitions#c8f1c22a9fac7b80
regards, chip