|
%I #58 May 26 2021 08:57:10
%S 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,
%T 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,
%U 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
%N Number of nonleading 0's in binary expansion of n.
%C 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.
%C 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).
%H N. J. A. Sloane, <a href="/A080791/b080791.txt">Table of n, a(n) for n = 0..10000</a>
%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F From _Antti Karttunen_, Dec 12 2013: (Start)
%F a(n) = A029837(n+1) - A000120(n).
%F a(0) = 0, and for n > 0, a(n) = (a(n-1) + A007814(n) + A036987(n-1)) - 1.
%F For all n >= 1, a(A054429(n)) = A048881(n-1) = A000120(n) - 1.
%F Equally, for all n >= 1, a(n) = A000120(A054429(n)) - 1.
%F (End)
%F 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
%F a(n) = A023416(n) for all n > 0. - _M. F. Hasler_, Oct 26 2017
%F G.f. g(x) satisfies g(x) = (1+x)*g(x^2) + x^2/(1-x^2). - _Robert Israel_, Oct 26 2017
%e a(4) = 2 since 4 in binary is 100, which has two zeros.
%e a(5) = 1 since 5 in binary is 101, which has only one zero.
%p seq(numboccur(0, Bits[Split](n)), n=0..100); # _Robert Israel_, Oct 26 2017
%t {0}~Join~Table[Last@ DigitCount[n, 2], {n, 120}] (* _Michael De Vlieger_, Mar 07 2016 *)
%t 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 *)
%t Join[{0}, Table[Count[IntegerDigits[n, 2], 0], {n, 1, 100}]] (* _Vincenzo Librandi_, Oct 27 2017 *)
%o (PARI) a(n)=if(n,a(n\2)+1-n%2)
%o (PARI) A080791(n)=if(n,logint(n,2)+1-hammingweight(n)) \\ _M. F. Hasler_, Oct 26 2017
%o (Scheme) ;; with memoizing definec-macro from Antti Karttunen's IntSeq-library)
%o (define (A080791 n) (- (A029837 (+ 1 n)) (A000120 n)))
%o ;; Alternative version based on a simple recurrence:
%o (definec (A080791 n) (if (zero? n) 0 (+ (A080791 (- n 1)) (A007814 n) (A036987 (- n 1)) -1)))
%o ;; from _Antti Karttunen_, Dec 12 2013
%o (Python) def a(n): return bin(n)[2:].count("0") if n>0 else 0 # _Indranil Ghosh_, Apr 10 2017
%Y Cf. A000120, A007814, A023416, A029837, A036987, A080791-A080801, A048881, A054429, A092339, A102364, A120511, A233271, A233272, A233273.
%K easy,nonn
%O 0,5
%A _Cino Hilliard_, Mar 25 2003
|
