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

Author

Russ Cox

Keywords

• easy
• nonn

Comments

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

Examples

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

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).

Crossrefs

Cf. A000069.

Programs

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 *)

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