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,5

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

Links

N. J. A. Sloane, Table of n, a(n) for n = 0..10000

Index entries for sequences related to binary expansion of n

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 Hillard'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

Example

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.

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

Prog

(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
(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
(Python) def a(n): return bin(n)[2:].count("0") if n>0 else 0 # Indranil Ghosh, Apr 10 2017

Crossrefs

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

Sequence in context: A352521 A277721 A023416 * A336361 A364260 A334204

Adjacent sequences: A080788 A080789 A080790 * A080792 A080793 A080794

Keyword

easy,nonn

Author

Cino Hilliard, Mar 25 2003

Status

approved