login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A080791 Number of nonleading 0's in binary expansion of n. 49
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

In this version we consider number zero to have no nonleading 0's, thus a(0) = 0. Another version (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, a(2n + 1) = a(n). - Ralf Stephan from Cino Hillard's PARI program, Dec 16 2013 [Warning: may be wrong, needs to be checked. - N. J. A. Sloane, Mar 07 2016] Corrected by Alonso del Arte, May 21 2017 after consultation with Chai Wah Wu and Ray Chandler

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.

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

PROG

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

(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, A000120, A048881, A054429, A092339, A102364, A120511, A233271, A233272, A233273.

Sequence in context: A050606 A277721 A023416 * A124748 A161225 A174980

Adjacent sequences:  A080788 A080789 A080790 * A080792 A080793 A080794

KEYWORD

easy,nonn

AUTHOR

Cino Hilliard, Mar 25 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 22 10:37 EDT 2017. Contains 290946 sequences.