A168160 Number of 0's in the matrix whose lines are the binary expansion of the numbers 1,...,n.

0, 2, 2, 7, 8, 9, 9, 19, 21, 23, 24, 26, 27, 28, 28, 47, 50, 53, 55, 58, 60, 62, 63, 66, 68, 70, 71, 73, 74, 75, 75, 111, 115, 119, 122, 126, 129, 132, 134, 138, 141, 144, 146, 149, 151, 153, 154, 158, 161, 164, 166, 169, 171, 173, 174, 177, 179, 181, 182, 184, 185, 186

Offset

1,2

Comments

The matrix is to be taken of minimal size, i.e., have n lines and the number of columns needed to write n in base 2 in the last line, A070939(n). Otherwise said, there is no zero column.

The number of zeros in the last line of the matrix is given by A023416(n).

One has a(n)=a(n-1) iff n = 2^k-1 for some k.

Links

Table of n, a(n) for n=1..62.

Formula

a(n) = n*A070939(n) - A000788(n).

Example

a(4)=7 is the number of zeros in the matrix
[001] /* = 1 in binary */
[010] /* = 2 in binary */
[011] /* = 3 in binary */
[100] /* = 4 in binary */

Prog

(PARI) A168160(n)=n*#binary(n)-sum(i=1, n, norml2(binary(i)))
(Python)
def A168160(n): return n*(a:=n.bit_length())-(n+1)*n.bit_count()-(sum((m:=1<<j)*((k:=n>>j)-(r if n<<1>=m*(r:=k<<1|1) else 0)) for j in range(1, a+1))>>1) # Chai Wah Wu, Nov 11 2024

Crossrefs

Cf. A000788, A070939, A023416, A059015.

Sequence in context: A151864 A019732 A199467 * A005300 A019087 A293607

Adjacent sequences: A168157 A168158 A168159 * A168161 A168162 A168163

Keyword

base,nonn,changed

Author

M. F. Hasler, Nov 22 2009

Status

approved