A159481 Number of evil numbers <= n, see A001969.

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, 15, 16, 16, 16, 17, 18, 18, 19, 19, 19, 20, 21, 21, 21, 22, 22, 23, 24, 24, 25, 25, 25, 26, 26, 27, 28, 28, 28, 29, 30, 30, 31, 31, 31, 32, 32, 33, 34, 34, 35, 35, 35, 36, 37, 37, 37

Offset: 0

Author

Reinhard Zumkeller, Apr 16 2009

Keywords

• nonn
• easy

Examples

			a(10) = #{0,11,101,110,1001,1010} = #{0,3,5,6,9,10} = 6.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
• Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 52.

Crossrefs

Cf. A000120, A001969, A010059, A115384.

Programs

Mathematica

Accumulate[Table[If[EvenQ[DigitCount[n,2,1]],1,0],{n,0,80}]] (* Harvey P. Dale, Mar 19 2018 *)
Accumulate[1 - ThueMorse[Range[0, 100]]] (* Paolo Xausa, Oct 25 2024 *)

PARI

a(n)=n\2+(n%2&&hammingweight(n)%2) \\ Charles R Greathouse IV, Mar 22 2013

Python

def A159481(n): return (n+1>>1)+((n+1).bit_count()&1&n+1) # Chai Wah Wu, Mar 01 2023

Formula

a(n) = n + 1 - A115384(n).

Limit_{n->oo} n/a(n) = 1/2.

a(n) = Sum_{k=0..n} A010059(k).

a(n) = floor(n/2) - (1 + (-1)^n)*(1 - (-1)^A000120(n))/4 + 1. - Vladimir Shevelev, May 27 2009

G.f.: (1/(1 - x)^2 + Product_{k>=1} (1 - x^(2^k)))/2. - Ilya Gutkovskiy, Apr 03 2019