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,4

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.

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

Example

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

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

Prog

(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

Crossrefs

Cf. A000120, A001969, A010059, A115384.

Sequence in context: A092038 A269990 A324473 * A194206 A307482 A046699

Adjacent sequences: A159478 A159479 A159480 * A159482 A159483 A159484

Keyword

nonn,easy

Author

Reinhard Zumkeller, Apr 16 2009

Status

approved