[seqfan] Question about A002577 (Number of partitions of 2^n into powers of 2)
Prof. Dr. Alois Heinz
heinz at hs-heilbronn.de
Mon Apr 20 02:02:44 CEST 2009
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
More information about the SeqFan
mailing list