seq A100661

[Joerg Arndt]

http://www.research.att.com/~njas/sequences/A100661

The following _seems_ to be true:

OGF =  \frac{2\,(1-x)\,\prod_{n=1}^{\infty}{\left(1+x^{2^n-1}\right)} - 1}{(1-x)^2}
= 1 + 2 x + x^2 + 2 x^3 + 3 x^4 + 2 x^5 + x^6 + 2 x^7 + 3 x^8 + 2 x^9 + 3 x^{10}
 + 4 x^{11} + 3 x^{12} + 2 x^{13} + x^{14} + 2 x^{15} + 3 x^{16} + 2 x^{17}
 + 3 x^{18} + 4 x^{19} + 3 x^{20} + 2 x^{21} + 3 x^{22} + 4 x^{23} + 3 x^{24}
 + 4 x^{25} + 5 x^{26} + ...

I.e. in sequence A079559 replace zeros by -1, then take cumulative seq.
http://www.research.att.com/~njas/sequences/A079559

Greedy computation:
one can subtract the greatest integer of the form $2^k-1$ until
$x$ is zero and count the number of subtractions.
[ comment in A100661:
 "a(n) is the number of terms needed to represent n
  as a sum of numbers of the form 2^k-1" ]


a(n) is the number of bits in the binary words of the
sequence A108918:
http://www.research.att.com/~njas/sequences/A108918
Figure:
        ....1 1     ....1 =  1 =  1
        ...11 2     ...1. =  2 =  1 + 1
        ...1. 1     ...11 =  3 =  3
        ..1.1 2     ..1.. =  4 =  3 + 1
        ..111 3     ..1.1 =  5 =  3 + 1 + 1
        ..11. 2     ..11. =  6 =  3 + 3
        ..1.. 1     ..111 =  7 =  7
        .1..1 2     .1... =  8 =  7 + 1
        .1.11 3     .1..1 =  9 =  7 + 1 + 1
        .1.1. 2     .1.1. = 10 =  7 + 3
        .11.1 3     .1.11 = 11 =  7 + 3 + 1
        .1111 4     .11.. = 12 =  7 + 3 + 1 + 1
        .111. 3     .11.1 = 13 =  7 + 3 + 3
        .11.. 2     .111. = 14 =  7 + 7
        .1... 1     .1111 = 15 = 15
        1...1 2     1.... = 16 = 15 + 1
        1..11 3     1...1 = 17 = 15 + 1 + 1
        1..1. 2     1..1. = 18 = 15 + 3
        1.1.1 3     1..11 = 19 = 15 + 3 + 1
        1.111 4     1.1.. = 20 = 15 + 3 + 1 + 1
        1.11. 3     1.1.1 = 21 = 15 + 3 + 3
        1.1.. 2     1.11. = 22 = 15 + 7
        11..1 3     1.111 = 23 = 15 + 7 + 1
        11.11 4     11... = 24 = 15 + 7 + 1 + 1
        11.1. 3     11..1 = 25 = 15 + 7 + 3
        111.1 4     11.1. = 26 = 15 + 7 + 3 + 1
        11111 5     11.11 = 27 = 15 + 7 + 3 + 1 + 1
        1111. 4     111.. = 28 = 15 + 7 + 3 + 3
        111.. 3     111.1 = 29 = 15 + 7 + 7
        11... 2     1111. = 30 = 15 + 15
        1.... 1     11111 = 31 = 31
Binary words in subset-lex order and their bit counts (left columns).
The least number of terms of the form $2^k-1$ needed
in the sum $x=\sum_k{2^k-1}$ (right columns) equals the bit count.


Can anyone confirm?