OFFSET
0,3
COMMENTS
For each n, let k go from 0 to 2^n-1. Write each k in binary using n bits, reverse the bits, then multiply by k. a(n) is the sum of these products.
For example, when n = 2, the 2-bit strings are 00, 01, 10, and 11 (in decimal: 0,1,2,3). When they are bit-reversed, we get 00, 10, 01, and 11 (in decimal: 0,2,1,3). Multiplying and adding the corresponding pairs, we get a(2) = 0*0 + 1*2 + 2*1 + 3*3 = 13.
LINKS
Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (18,-112,288,-256).
FORMULA
a(n) = Sum_{k=0..2^n-1} k * A030109(2^n+k).
a(n+1) = 4*a(n) + 2^(3n) + 2^(2n-1) - 2^(n-1).
a(n) = n*2^(2*n-3) + 2^(3n-2) + 2^(n-2) - 2^(2n-1).
From Colin Barker, Oct 01 2019: (Start)
G.f.: x*(1 - 5*x) / ((1 - 2*x)*(1 - 4*x)^2*(1 - 8*x)).
a(n) = 2^(n-3) * (2*(2^n-1)^2 + 2^n*n).
a(n) = 18*a(n-1) - 112*a(n-2) + 288*a(n-3) - 256*a(n-4) for n>3.
(End)
E.g.f.: (1/4)*(exp(2*x) + exp(8*x) + 2*exp(4*x)*(-1 + x)). - Stefano Spezia, Oct 01 2019
MATHEMATICA
CoefficientList[Series[x (1 - 5 x)/((1 - 2 x) (1 - 4 x)^2*(1 - 8 x)), {x, 0, 21}], x] (* Michael De Vlieger, Oct 01 2019 *)
PROG
(Python)
revbits = lambda i, n: int(bin(i)[2:].rjust(n, '0')[::-1], 2)
def a(n):
return sum(i * revbits(i, n) for i in range(2**n))
print([a(n) for n in range(22)])
(PARI) f(n) = (fromdigits(Vecrev(binary(n)), 2) - 1)/2; \\ A030109
a(n) = sum(k=0, 2^n, f(2^n+k)*k); \\ Michel Marcus, Oct 01 2019
(PARI) concat(0, Vec(x*(1 - 5*x) / ((1 - 2*x)*(1 - 4*x)^2*(1 - 8*x)) + O(x^25))) \\ Colin Barker, Oct 01 2019
CROSSREFS
KEYWORD
nonn,base,easy
AUTHOR
Peter Ward, Sep 30 2019
STATUS
approved