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

[Prof. Dr. Alois Heinz]

Dear Valentin Bakoev,

thank you for your mail.  It helped to answer my questions.

I had looked into your paper before and there are no problems
with the paper.  But I was not able to find a satisfactory
explanation for your comments in the OEIS.  Now the situation
seems to be clear to me.

1) The comment in A000290 interprets "the sum 2^2+2^2+...2^2,
   (n-1)-times" as "an expression, which addends are partitioned".
   This means, that no powers of 2 larger than 2^2=4 are allowed
   to express its value 4n-4.  This is consistent to my interpretation
   "a(n+1) is also the number of partitions of 4n into the first
   3 powers of 2 (parts of size 1, 2, 4)."

2) The comments in A002577, A078125, A125792, A125801 regard
   the "input number n" as the input size, which is not correct here.
  
   When we say, that addition of two numbers can be performed in
   linear time - O(k) - or that multiplication of numbers can be
   performed in time O(k*log(k)*log(log(k))), k is always the total
   number of bits in the input, not the value of the numbers. 
   (Otherwise, addition would be very time consuming.) 
     
   So the number of bits k of the "input number n" for A002577 is
   k = ceiling (log_2 (n+1)).  A polynomial of degree n now has
   exponential size with respect to the input size k.  And the
   running time of the algorithm is exponential too, not polynomial.

I would suggest changing or deleting the comments in A000290,
A002577, A078125, A125792, A125801.

Best regards,  Alois

Valentin Bakoev schrieb:

> 
>Dear
>Professor Heinz,
>Dear
>Professor Povolotsky,
> 
>All my
>notes and comments in OEIS, that you ask me about,  are taken (or related to, or follow directly) from my paper
>“Algorithmic approach to counting of certain types m-ary partitions”, Discrete
>Mathematics, 275 (2004) pp.17-41. Naturally, many details from the paper are
>omitted in my notes in OEIS - they summarize some results and relations only. So
>I refer to the paper and I recommend it to the readers who want to know these
>details. I think that the paper contains the answers of all your questions to
>me. Anyway, I will try to answer you shortly:
>1)      My
>comment about the sequence A000290 concerns the number of all partitions of the
>sum 2^2+2^2+...2^2, (n-1)-times, into powers of 2. This sum is considered as an
>expression, which addends are partitioned. So we do not consider the partitions
>of the number, equal to the value of this expression. This is more general
>problem, as it is noted in the field “Formula” of A002577. The relation between
>it (i.e. the numbers of A002577) and the square numbers is given in the fields
>“Crossrefs” of A000290 and A002577;
>2)      The
>existence of an algorithm (with polynomial running-time) for computing the
>members of A002577, A125792 and other sequences of the same type is derived in
>Section 4 of the paper, mentioned above. I should note, that this running-time
>is obtained towards uniform cost criterion. The reasons to accept this
>criterion are discussed in the Introduction of the paper. This criterion is
>enough realistic for many practical purposes, for example when:
>-         the size of the input and the output
>in not so large and the 64-bits architectures and arithmetic are enough for
>computing of the intermediate results and the output;
>-         the
>number of partitions is computed by an efficient implementation of
>large-integer arithmetic – as in the packages Mathematica, Maple etc.
> 
>Thank you for your attention to my notes in
>OEIS!
> 
>Sincerely yours,
>Valentin Bakoev
>
>
>----- Original Message ----
>From: Prof. Dr. Alois Heinz <heinz at hs-heilbronn.de>
>To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>; v_bakoev at yahoo.com
>Sent: Monday, April 20, 2009 3:02:44 AM
>Subject: Question about A002577 (Number of partitions of 2^n into powers of 2)
>
>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
>  
>