%I #24 Oct 25 2024 10:41:32
%S 1,1,1,2,2,3,4,4,4,5,6,6,7,7,7,8,8,9,10,10,11,11,11,12,13,13,13,14,14,
%T 15,16,16,16,17,18,18,19,19,19,20,21,21,21,22,22,23,24,24,25,25,25,26,
%U 26,27,28,28,28,29,30,30,31,31,31,32,32,33,34,34,35,35,35,36,37,37,37
%N Number of evil numbers <= n, see A001969.
%H Reinhard Zumkeller, <a href="/A159481/b159481.txt">Table of n, a(n) for n = 0..10000</a>
%H Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, p. 52.
%F a(n) = n + 1 - A115384(n).
%F Limit_{n->oo} n/a(n) = 1/2.
%F a(n) = Sum_{k=0..n} A010059(k).
%F a(n) = floor(n/2) - (1 + (-1)^n)*(1 - (-1)^A000120(n))/4 + 1. - _Vladimir Shevelev_, May 27 2009
%F G.f.: (1/(1 - x)^2 + Product_{k>=1} (1 - x^(2^k)))/2. - _Ilya Gutkovskiy_, Apr 03 2019
%e a(10) = #{0,11,101,110,1001,1010} = #{0,3,5,6,9,10} = 6.
%t Accumulate[Table[If[EvenQ[DigitCount[n,2,1]],1,0],{n,0,80}]] (* _Harvey P. Dale_, Mar 19 2018 *)
%t Accumulate[1 - ThueMorse[Range[0, 100]]] (* _Paolo Xausa_, Oct 25 2024 *)
%o (PARI) a(n)=n\2+(n%2&&hammingweight(n)%2) \\ _Charles R Greathouse IV_, Mar 22 2013
%o (Python)
%o def A159481(n): return (n+1>>1)+((n+1).bit_count()&1&n+1) # _Chai Wah Wu_, Mar 01 2023
%Y Cf. A000120, A001969, A010059, A115384.
%K nonn,easy
%O 0,4
%A _Reinhard Zumkeller_, Apr 16 2009