%I #24 Jun 13 2017 08:00:15
%S 0,0,0,1,1,6,8,29,45,130,220,561,1001,2366,4368,9829,18565,40410,
%T 77540,164921,320001,669526,1309528,2707629,5326685,10919090,21572460,
%U 43942081,87087001,176565486,350739488,708653429,1410132405,2841788170,5662052980
%N Number of numbers == 0 (mod 3) in range 2^n to 2^(n+1) with odd number of 1's in binary expansion.
%C The first numbers with this property are 21, 42, 69, 81, 84, 87, 93, and 117. - _T. D. Noe_, Jun 20 2012
%H T. D. Noe, <a href="/A000773/b000773.txt">Table of n, a(n) for n = 1..501</a>
%H Nina Chen, <a href="https://www.kaggle.com/ncchen/recurrence-relation">Recurrence relation</a>.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,5,-3,-6).
%F 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
%F 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
%F 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
%e G.f. = x^4 + x^5 + 6*x^6 + 8*x^7 + 29*x^8 + 45*x^9 + 130*x^10 + 220*x^11 + ...
%t 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 *)
%Y Cf. A000069.
%K easy,nonn
%O 1,6
%A _Russ Cox_