A080791 Number of nonleading 0's in binary expansion of n.

0, 0, 1, 0, 2, 1, 1, 0, 3, 2, 2, 1, 2, 1, 1, 0, 4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 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, 6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2, 5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1, 5, 4, 4, 3, 4, 3, 3, 2, 4

Offset: 0

Author

Cino Hilliard, Mar 25 2003

Keywords

• easy
• nonn

Comments

In this version we consider the number zero to have no nonleading 0's, thus a(0) = 0. The variant A023416 has a(0) = 1.

Number of steps required to reach 1, starting at n + 1, under the operation: if x is even divide by 2 else add 1. This is the x + 1 problem (as opposed to the 3x + 1 problem).

Examples

			a(4) = 2 since 4 in binary is 100, which has two zeros.
a(5) = 1 since 5 in binary is 101, which has only one zero.
		

Links

• N. J. A. Sloane, Table of n, a(n) for n = 0..10000
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A000120, A007814, A023416, A029837, A036987, A080791-A080801, A048881, A054429, A092339, A102364, A120511, A233271, A233272, A233273.

Programs

Maple

seq(numboccur(0, Bits[Split](n)), n=0..100); # Robert Israel, Oct 26 2017

Mathematica

{0}~Join~Table[Last@ DigitCount[n, 2], {n, 120}] (* Michael De Vlieger, Mar 07 2016 *)
f[n_] := If[OddQ@ n, f[n -1] -1, f[n/2] +1]; f[0] = f[1] = 0; Array[f, 105, 0] (* Robert G. Wilson v, May 21 2017 *)
Join[{0}, Table[Count[IntegerDigits[n, 2], 0], {n, 1, 100}]] (* Vincenzo Librandi, Oct 27 2017 *)

PARI

a(n)=if(n,a(n\2)+1-n%2)

PARI

A080791(n)=if(n,logint(n,2)+1-hammingweight(n)) \\ M. F. Hasler, Oct 26 2017

Python

def a(n): return bin(n)[2:].count("0") if n>0 else 0 # Indranil Ghosh, Apr 10 2017

Scheme

;; with memoizing definec-macro from Antti Karttunen's IntSeq-library)
(define (A080791 n) (- (A029837 (+ 1 n)) (A000120 n)))
;; Alternative version based on a simple recurrence:
(definec (A080791 n) (if (zero? n) 0 (+ (A080791 (- n 1)) (A007814 n) (A036987 (- n 1)) -1)))
;; from Antti Karttunen, Dec 12 2013

Formula

From Antti Karttunen, Dec 12 2013: (Start)

a(n) = A029837(n+1) - A000120(n).

a(0) = 0, and for n > 0, a(n) = (a(n-1) + A007814(n) + A036987(n-1)) - 1.

For all n >= 1, a(A054429(n)) = A048881(n-1) = A000120(n) - 1.

Equally, for all n >= 1, a(n) = A000120(A054429(n)) - 1.

(End)

Recurrence: a(2n) = a(n) + 1 (for n > 0), a(2n + 1) = a(n). - Ralf Stephan from Cino Hilliard's PARI program, Dec 16 2013. Corrected by Alonso del Arte, May 21 2017 after consultation with Chai Wah Wu and Ray Chandler, "n > 0" added by M. F. Hasler, Oct 26 2017

a(n) = A023416(n) for all n > 0. - M. F. Hasler, Oct 26 2017

G.f. g(x) satisfies g(x) = (1+x)*g(x^2) + x^2/(1-x^2). - Robert Israel, Oct 26 2017