[seqfan] Re: Question about A002577 (Number of partitions of 2^n into powers of 2)

Georgi Guninski guninski at guninski.com
Mon Apr 20 11:35:00 CEST 2009


On Mon, Apr 20, 2009 at 02:02:44AM +0200, Prof. Dr. Alois Heinz wrote:
> Seqfans, in A002577 (Number of partitions of 2^n into powers of 2)
> 
> http://www.research.att.com/~njas/sequences/A002577
> 
> and also in A078125, A125792, A125801
> 
> I found this comment in the MAPLE field: "There exists an algorithm
>   (with polynomial running-time) for computing the members of A002577,
>   A125792 and other sequences of the same type."
> 
> I have heavy doubts that this can be true.
>

A002577(n)=A000123(2^(n-1))
A000123 Number of binary partitions: number of partitions of 2n into
powers of 2
A000123(n)=A018819(2n)
A018819  Binary partition function: number of partitions of n into
powers of 2

i am interested in the exponentially easier question if the binary
partition function is efficiently computable (say for n about 2^100). if
virtual memory storage is a problem one is allowed to do reduction
modulo integer.






More information about the SeqFan mailing list