A165317 a(n) = the number of digits in the binary representation of n that each do not precede or follow a similarly valued digit.

1, 2, 0, 1, 3, 1, 0, 1, 2, 4, 2, 0, 2, 1, 0, 1, 2, 3, 1, 3, 5, 3, 2, 0, 1, 3, 1, 0, 2, 1, 0, 1, 2, 3, 1, 2, 4, 2, 1, 3, 4, 6, 4, 2, 4, 3, 2, 0, 1, 2, 0, 2, 4, 2, 1, 0, 1, 3, 1, 0, 2, 1, 0, 1, 2, 3, 1, 2, 4, 2, 1, 2, 3, 5, 3, 1, 3, 2, 1, 3, 4, 5, 3, 5, 7, 5, 4, 2, 3, 5, 3, 2, 4, 3, 2, 0, 1, 2, 0, 1, 3, 1, 0, 2, 3

Offset: 1

Author

Leroy Quet, Sep 14 2009

Keywords

• base
• nonn
• easy

Comments

A165316(n) + a(n) = the number of digits in the binary representation of n.

Also number of parts equal to 1 in the composition having index n. For the definition of the index of a composition see A298644. For example, a(18) = 3 since the binary form of 18 is (1)00(1)(0) which has 3 runs of length 1 (each placed between parentheses). The command c(n) from the Maple program yields the composition having index n. - Emeric Deutsch, Jan 29 2018

Examples

			184 in binary is 10111001. There are exactly three binary digits (the first and last 1's, and the leftmost 0) that are each not adjacent to a similar digit. So a(184) = 3.
		

Links

• John Tyler Rascoe, Table of n, a(n) for n = 1..8191

Crossrefs

Cf. A165316, A298644, A101211.

Programs

Maple

Runs := proc (L) local j, r, i, k: j := 1: r[j] := L[1]: for i from 2 to nops(L) do if L[i] = L[i-1] then r[j] := r[j], L[i] else j := j+1: r[j] := L[i] end if end do: [seq([r[k]], k = 1 .. j)] end proc: RunLengths := proc (L) map(nops, Runs(L)) end proc: c := proc (n) ListTools:-Reverse(convert(n, base, 2)): RunLengths(%) end proc: a := proc (n) local ct, j: ct := 0: for j to nops(c(n)) do if c(n)[j] = 1 then ct := ct+1 else end if end do: ct end proc: seq(a(n), n = 1 .. 105); # most of the Maple program is due to W. Edwin Clark. # Emeric Deutsch, Jan 29 2018

Python

def a(n): return ((n^(n<<1))&(n^(n>>1))).bit_count() + ((n&3)==2)
print([a(n) for n in range(1, 106)]) # Michael S. Branicky, May 12 2024

Extensions

Extended by Ray Chandler, Mar 13 2010