login
Product of lengths of runs of 1-bits in binary representation of n.
29

%I #95 Mar 23 2020 06:53:33

%S 1,1,1,2,1,1,2,3,1,1,1,2,2,2,3,4,1,1,1,2,1,1,2,3,2,2,2,4,3,3,4,5,1,1,

%T 1,2,1,1,2,3,1,1,1,2,2,2,3,4,2,2,2,4,2,2,4,6,3,3,3,6,4,4,5,6,1,1,1,2,

%U 1,1,2,3,1,1,1,2,2,2,3,4,1,1,1,2,1,1,2,3,2,2,2,4,3,3,4,5,2,2,2,4,2,2,4,6,2,2,2,4,4,4,6,8,3,3,3,6,3,3,6,9,4

%N Product of lengths of runs of 1-bits in binary representation of n.

%C This is the Run Length Transform of S(n) = {0, 1, 2, 3, 4, 5, 6, ...}. The Run Length Transform of a sequence {S(n), n >= 0} is defined to be the sequence {T(n), n >= 0} given by T(n) = Product_i S(i), where i runs through the lengths of runs of 1's in the binary expansion of n. E.g., 19 is 10011 in binary, which has two runs of 1's, of lengths 1 and 2. So T(19) = S(1)*S(2). T(0) = 1 (the empty product). - _N. J. A. Sloane_, Sep 05 2014

%C Like all run length transforms also this sequence satisfies for all i, j: A278222(i) = A278222(j) => a(i) = a(j). - _Antti Karttunen_, Apr 14 2017

%H Antti Karttunen, <a href="/A227349/b227349.txt">Table of n, a(n) for n = 0..8192</a>

%H N. J. A. Sloane, <a href="http://arxiv.org/abs/1503.01168">On the Number of ON Cells in Cellular Automata</a>, arXiv:1503.01168 [math.CO], 2015.

%H <a href="/index/Ru#rlt">Index entries for sequences computed with run length transform</a>

%F A167489(n) = a(n) * A227350(n).

%F A227193(n) = a(n) - A227350(n).

%F a(n) = Product_{i in row n of table A245562} i. - _N. J. A. Sloane_, Aug 10 2014

%F From _Antti Karttunen_, Apr 14 2017: (Start)

%F a(n) = A005361(A005940(1+n)).

%F a(n) = A284562(n) * A284569(n).

%F A283972(n) = n - a(n).

%F (End)

%e a(0) = 1, as zero has no runs of 1's, and an empty product is 1.

%e a(1) = 1, as 1 is "1" in binary, and the length of that only 1-run is 1.

%e a(2) = 1, as 2 is "10" in binary, and again there is only one run of 1-bits, of length 1.

%e a(3) = 2, as 3 is "11" in binary, and there is one run of two 1-bits.

%e a(55) = 6, as 55 is "110111" in binary, and 2 * 3 = 6.

%e a(119) = 9, as 119 is "1110111" in binary, and 3 * 3 = 9.

%e From _Omar E. Pol_, Feb 10 2015: (Start)

%e Written as an irregular triangle in which row lengths is A011782:

%e 1;

%e 1;

%e 1,2;

%e 1,1,2,3;

%e 1,1,1,2,2,2,3,4;

%e 1,1,1,2,1,1,2,3,2,2,2,4,3,3,4,5;

%e 1,1,1,2,1,1,2,3,1,1,1,2,2,2,3,4,2,2,2,4,2,2,4,6,3,3,3,6,4,4,5,6;

%e ...

%e Right border gives A028310: 1 together with the positive integers.

%e (End)

%e From _Omar E. Pol_, Mar 19 2015: (Start)

%e Also, the sequence can be written as an irregular tetrahedron T(s, r, k) as shown below:

%e 1;

%e ..

%e 1;

%e ..

%e 1;

%e 2;

%e ....

%e 1,1;

%e 2;

%e 3;

%e ........

%e 1,1,1,2;

%e 2,2;

%e 3;

%e 4;

%e ................

%e 1,1,1,2,1,1,2,3;

%e 2,2,2,4;

%e 3,3;

%e 4;

%e 5;

%e ................................

%e 1,1,1,2,1,1,2,3,1,1,1,2,2,2,3,4;

%e 2,2,2,4,2,2,4,6;

%e 3,3,3,6;

%e 4,4;

%e 5;

%e 6;

%e ...

%e Apart from the initial 1, we have that T(s, r, k) = T(s+1, r, k).

%e (End)

%p a:= proc(n) local i, m, r; m, r:= n, 1;

%p while m>0 do

%p while irem(m, 2, 'h')=0 do m:=h od;

%p for i from 0 while irem(m, 2, 'h')=1 do m:=h od;

%p r:= r*i

%p od; r

%p end:

%p seq(a(n), n=0..100); # _Alois P. Heinz_, Jul 11 2013

%p ans:=[];

%p for n from 0 to 100 do lis:=[]; t1:=convert(n, base, 2); L1:=nops(t1); out1:=1; c:=0;

%p for i from 1 to L1 do

%p if out1 = 1 and t1[i] = 1 then out1:=0; c:=c+1;

%p elif out1 = 0 and t1[i] = 1 then c:=c+1;

%p elif out1 = 1 and t1[i] = 0 then c:=c;

%p elif out1 = 0 and t1[i] = 0 then lis:=[c, op(lis)]; out1:=1; c:=0;

%p fi;

%p if i = L1 and c>0 then lis:=[c, op(lis)]; fi;

%p od:

%p a:=mul(i, i in lis);

%p ans:=[op(ans), a];

%p od:

%p ans; # _N. J. A. Sloane_, Sep 05 2014

%t onBitRunLenProd[n_] := Times @@ Length /@ Select[Split @ IntegerDigits[n, 2], #[[1]] == 1 & ]; Array[onBitRunLenProd, 100, 0] (* _Jean-François Alcover_, Mar 02 2016 *)

%o (Python)

%o from operator import mul

%o from functools import reduce

%o from re import split

%o def A227349(n):

%o return reduce(mul, (len(d) for d in split('0+',bin(n)[2:]) if d)) if n > 0 else 1 # _Chai Wah Wu_, Sep 07 2014

%o (Sage) # uses[RLT from A246660]

%o A227349_list = lambda len: RLT(lambda n: n, len)

%o A227349_list(88) # _Peter Luschny_, Sep 07 2014

%o (Scheme)

%o (define (A227349 n) (apply * (bisect (reverse (binexp->runcount1list n)) (- 1 (modulo n 2)))))

%o (define (bisect lista parity) (let loop ((lista lista) (i 0) (z (list))) (cond ((null? lista) (reverse! z)) ((eq? i parity) (loop (cdr lista) (modulo (1+ i) 2) (cons (car lista) z))) (else (loop (cdr lista) (modulo (1+ i) 2) z)))))

%o (define (binexp->runcount1list n) (if (zero? n) (list) (let loop ((n n) (rc (list)) (count 0) (prev-bit (modulo n 2))) (if (zero? n) (cons count rc) (if (eq? (modulo n 2) prev-bit) (loop (floor->exact (/ n 2)) rc (1+ count) (modulo n 2)) (loop (floor->exact (/ n 2)) (cons count rc) 1 (modulo n 2)))))))

%Y Cf. A003714 (positions of ones), A005361, A005940.

%Y Cf. A000120 (sum of lengths of runs of 1-bits), A167489, A227350, A227193, A278222, A245562, A284562, A284569, A283972, A284582, A284583.

%Y Run Length Transforms of other sequences: A246588, A246595, A246596, A246660, A246661, A246674.

%Y Differs from similar A284580 for the first time at n=119, where a(119) = 9, while A284580(119) = 5.

%K nonn,base

%O 0,4

%A _Antti Karttunen_, Jul 08 2013

%E Data section extended up to term a(120) by _Antti Karttunen_, Apr 14 2017