[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.

A000123 Number of binary partitions: number of partitions of 2n into
powers of 2
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