A086784 Number of non-trailing zeros in binary representation of n.

0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 1, 1, 0, 1, 0, 0, 0, 3, 2, 2, 1, 2, 1, 1, 0, 2, 1, 1, 0, 1, 0, 0, 0, 4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0, 3, 2, 2, 1, 2, 1, 1, 0, 2, 1, 1, 0, 1, 0, 0, 0, 5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1, 4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0, 4, 3, 3, 2, 3

Offset: 0

Author

Reinhard Zumkeller, Aug 03 2003

Keywords

• nonn
• base

Comments

a(n) is also the number of parts smaller than the largest part in the integer partition having viabin number n. The viabin number of an integer partition is defined in the following way. Consider the southeast border of the Ferrers board of the integer partition and consider the binary number obtained by replacing each east step with 1 and each north step, except the last one, with 0. The corresponding decimal form is, by definition, the viabin number of the given integer partition. "Viabin" is coined from "via binary". For example, consider the integer partition [2,2,2,1]. The southeast border of its Ferrers board yields 10100, leading to the viabin number 20. - Emeric Deutsch Jul 24 2017

Examples

			a(34) = 3; indeed the binary representation of 34 is 100010, having 3 non-trailing zeros. - _Emeric Deutsch_ Jul 24 2017
		

Links

• Paolo Xausa, Table of n, a(n) for n = 0..10000
• Eric Weisstein's World of Mathematics, Binary Carry Sequence
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A007088.

Programs

Maple

a := proc (n) local b, c: b := proc (n) if `mod`(n, 2) = 0 then 1+b((1/2)*n) else 0 end if end proc: c := proc (n) if n = 0 then 2 elif n = 1 then 0 elif `mod`(n, 2) = 0 then 1+c((1/2)*n) else c((1/2)*n-1/2) end if end proc: if n = 0 then 0 else c(n)-b(n) end if end proc: seq(a(n), n = 0 .. 101); # b and c are the Maple programs for A007814 and A023416, respectively. - Emeric Deutsch Jul 24 2017

Mathematica

A086784[n_] := If[n == 0, 0, DigitCount[n, 2, 0] - IntegerExponent[n, 2]];
Array[A086784, 100, 0] (* Paolo Xausa, Oct 01 2024 *)

PARI

a(n)=if(n==0,0,exponent(n)+1-hammingweight(n)-valuation(n,2)); \\ Antoine Mathys, Nov 20 2024

Python

def A086784(n): return bin(n>>(~n & n-1).bit_length())[2:].count('0') if n else 0 # Chai Wah Wu, Oct 14 2022

Formula

a(n) = A023416(n) - A007814(n) for n>0.

a(2^n) = a(A000079(n)) = 0; a(2^n - 1) = a(A000225(n)) = 0;

a(2^n + 1) = a(A000051(n)) = n - 1;

a(3*2^n - 1) = a(A055010(n)) = 1 for n>0;

a(2^n - 3) = a(A036563(n)) = 1, for n>2;

a((4^n - 1)/3) = a(A002450(n)) = n.

a(n) = if n mod 4 = 1 then a(floor(n/4)) + A007814(floor(n/2)) else a(floor(n/2)); a(0) = a(1) = 0.