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

Author

M. F. Hasler, Nov 22 2009

Keywords

• base
• nonn

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.

Examples

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

Links

• Paolo Xausa, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000788, A070939, A023416, A059015, A380230.

Programs

Mathematica

#*BitLength[#] - Accumulate[DigitCount[#, 2, 1]] & [Range[100]] (* Paolo Xausa, Jan 17 2025 *)

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

Formula

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