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

[Prof. Dr. Alois Heinz]

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.

In A002577, if the input size is k bit, output a(n) with fewest bits b(k)
is generated by n=2^(k-1). 

We have b(k) = 2, 6, 20, 87, 395, 1743, 7442 bits
(or 1, 2, 6, 27, 119, 525, 2241 decimal digits) for k = 2..8 bits.

When the input size increases by +1, the output size increases by a 
factor (>2).

This looks like exponential growth.

How can a(n) then be computed and printed in polynomial running-time?

Alois