A000773 Number of numbers == 0 (mod 3) in range 2^n to 2^(n+1) with odd number of 1's in binary expansion.

0, 0, 0, 1, 1, 6, 8, 29, 45, 130, 220, 561, 1001, 2366, 4368, 9829, 18565, 40410, 77540, 164921, 320001, 669526, 1309528, 2707629, 5326685, 10919090, 21572460, 43942081, 87087001, 176565486, 350739488, 708653429, 1410132405, 2841788170, 5662052980

Offset

1,6

Comments

The first numbers with this property are 21, 42, 69, 81, 84, 87, 93, and 117. - T. D. Noe, Jun 20 2012

Links

T. D. Noe, Table of n, a(n) for n = 1..501

Nina Chen, Recurrence relation.

Index entries for linear recurrences with constant coefficients, signature (1,5,-3,-6).

Formula

a(n) = (1/6)*(2^n - (-1)^n - 3^((n+1)/2)). G.f.: x^3 / ((1+x)*(1-2*x)*(1-3*x^2)). - Ralf Stephan, Aug 08 2004

a(n) = a(n-1) + 2 * a(n-2) + 3^(n/2) * (1 + (-1)^n) / 18 for all n in Z. - Michael Somos, Jan 23 2014

a(n) = - 6 * a(n-4) - 3 * a(n-3) + 5 * a(n-2) + a(n-1) for n > 4. - Hugo Pfoertner, Jun 13 2017

Example

G.f. = x^4 + x^5 + 6*x^6 + 8*x^7 + 29*x^8 + 45*x^9 + 130*x^10 + 220*x^11 + ...

Mathematica

nn = 35; CoefficientList[Series[x^3/((1 + x) (1 - 2 x) (1 - 3 x^2)), {x, 0, nn}], x] (* T. D. Noe, Jun 20 2012 *)

Crossrefs

Cf. A000069.

Sequence in context: A229335 A007829 A345003 * A258283 A039720 A056097

Adjacent sequences: A000770 A000771 A000772 * A000774 A000775 A000776

Keyword

easy,nonn

Author

Russ Cox

Status

approved