[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