login
Number of runs of 1's in the binary representation of n.
88

%I #63 Jun 28 2024 10:07:15

%S 0,1,1,1,1,2,1,1,1,2,2,2,1,2,1,1,1,2,2,2,2,3,2,2,1,2,2,2,1,2,1,1,1,2,

%T 2,2,2,3,2,2,2,3,3,3,2,3,2,2,1,2,2,2,2,3,2,2,1,2,2,2,1,2,1,1,1,2,2,2,

%U 2,3,2,2,2,3,3,3,2,3,2,2,2,3,3,3,3,4,3,3,2,3,3,3,2,3

%N Number of runs of 1's in the binary representation of n.

%C a(n) is also the number of distinct parts 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

%C Positions of first occurrences of k are A002450(k). - _John Keith_, Aug 30 2021

%H Tilman Piesk (terms 0..9999) & Antti Karttunen, <a href="/A069010/b069010.txt">Table of n, a(n) for n = 0..16384</a>

%H Louis Marin, <a href="https://arxiv.org/abs/2406.16413">Counting Polyominoes in a Rectangle b X h</a>, arXiv:2406.16413 [cs.DM], 2024. See p. 148.

%H Vladimir Shevelev, <a href="http://arxiv.org/abs/1603.04434">Two analogs of Thue-Morse sequence</a>, arXiv:1603.04434 [math.NT], 2016.

%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

%F a(n) = ceiling(A005811(n)/2) = A005811(n) - A033264(n). If 2^k <= n < 3*2^(k-1) then a(n) = a(n-2^k)+1; if 3*2^(k-1) <= n < 2^(k+1) then a(n) = a(n-2^k).

%F a(2n) = a(n), a(2n+1) = a(n) + [n is even]. - _Ralf Stephan_, Aug 20 2003

%F G.f.: (1/(1-x)) * Sum_{k>=0} (t/(1+t))/(1+t^2), where t=x^2^k. - _Ralf Stephan_, Sep 07 2003

%F a(n) = A000120(n) - A014081(n) = A037800(n) + 1, n>0. - _Ralf Stephan_, Sep 10 2003

%e a(11) = 2 since 11 is 1011 in binary with two runs of 1's.

%e a(12) = 1 since 12 is 1100 in binary with one run of 1's.

%p f:= proc(n) option remember; if n::even then procname(n/2)

%p elif n mod 4 = 1 then 1 + procname((n-1)/2) else procname((n-1)/2) fi end proc:

%p f(0):= 0:

%p map(f, [$0..1000]); # _Robert Israel_, Sep 06 2015

%t Count[Split@ IntegerDigits[#, 2], n_ /; First@ n == 1] & /@ Range[0, 120] (* _Michael De Vlieger_, Sep 05 2015 *)

%o (PARI) a(n) = (1 + (hammingweight(bitxor(n, n>>1)))) >> 1; \\ _Gheorghe Coserea_, Sep 05 2015

%o (Scheme) (define (A069010 n) (/ (+ (A005811 n) (A000035 n)) 2)) ;; _Antti Karttunen_, Feb 05 2016

%o (Python)

%o def A069010(n):

%o return sum(1 for d in bin(n)[2:].split('0') if len(d)) # _Chai Wah Wu_, Nov 04 2016

%Y Cf. A000035, A000120, A005811, A014081, A033264, A037800.

%Y Cf. A268411 (parity of the terms), A268412 (positions of even terms), A268415 (of odd terms).

%Y Cf. A002450 (positions of record highs).

%Y Cf. also A227349, A246588.

%K base,easy,nonn

%O 0,6

%A _Henry Bottomley_, Apr 02 2002