

A227349


Product of lengths of runs of 1bits in binary representation of n.


28



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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

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


LINKS

Antti Karttunen, Table of n, a(n) for n = 0..8192
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168, 2015
Index entries for sequences computed with run length transform


FORMULA

A167489(n) = a(n) * A227350(n).
A227193(n) = a(n)  A227350(n).
a(n) = Product_{i in row n of table A245562} i.  N. J. A. Sloane, Aug 10 2014
From Antti Karttunen, Apr 14 2017: (Start)
a(n) = A005361(A005940(1+n)).
a(n) = A284562(n) * A284569(n).
A283972(n) = n  a(n).
(End)


EXAMPLE

a(0) = 1, as zero has no runs of 1's, and an empty product is 1.
a(1) = 1, as 1 is "1" in binary, and the length of that only 1run is 1.
a(2) = 1, as 2 is "10" in binary, and again there is only one run of 1bits, of length 1.
a(3) = 2, as 3 is "11" in binary, and there is one run of two 1bits.
a(55) = 6, as 55 is "110111" in binary, and 2 * 3 = 6.
a(119) = 9, as 119 is "1110111" in binary, and 3 * 3 = 9.
From Omar E. Pol, Feb 10 2015: (Start)
Written as an irregular triangle in which row lengths is A011782:
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,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;
...
Right border gives A028310: 1 together with the positive integers.
(End)
From Omar E. Pol, Mar 19 2015: (Start)
Also, the sequence can be written as an irregular tetrahedron T(s, r, k) as shown below:
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,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;
...
Apart from the initial 1, we have that T(s, r, k) = T(s+1, r, k).
(End)


MAPLE

a:= proc(n) local i, m, r; m, r:= n, 1;
while m>0 do
while irem(m, 2, 'h')=0 do m:=h od;
for i from 0 while irem(m, 2, 'h')=1 do m:=h od;
r:= r*i
od; r
end:
seq(a(n), n=0..100); # Alois P. Heinz, Jul 11 2013
ans:=[];
for n from 0 to 100 do lis:=[]; t1:=convert(n, base, 2); L1:=nops(t1); out1:=1; c:=0;
for i from 1 to L1 do
if out1 = 1 and t1[i] = 1 then out1:=0; c:=c+1;
elif out1 = 0 and t1[i] = 1 then c:=c+1;
elif out1 = 1 and t1[i] = 0 then c:=c;
elif out1 = 0 and t1[i] = 0 then lis:=[c, op(lis)]; out1:=1; c:=0;
fi;
if i = L1 and c>0 then lis:=[c, op(lis)]; fi;
od:
a:=mul(i, i in lis);
ans:=[op(ans), a];
od:
ans; # N. J. A. Sloane, Sep 05 2014


MATHEMATICA

onBitRunLenProd[n_] := Times @@ Length /@ Select[Split @ IntegerDigits[n, 2], #[[1]] == 1 & ]; Array[onBitRunLenProd, 100, 0] (* JeanFrançois Alcover, Mar 02 2016 *)


PROG

(Python)
from operator import mul
from functools import reduce
from re import split
def A227349(n):
....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
(Sage)
# For the function RLT see A246660.
A227349_list = lambda len: RLT(lambda n: n, len)
A227349_list(88) # Peter Luschny, Sep 07 2014
(Scheme)
(define (A227349 n) (apply * (bisect (reverse (binexp>runcount1list n)) ( 1 (modulo n 2)))))
(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)))))
(define (binexp>runcount1list n) (if (zero? n) (list) (let loop ((n n) (rc (list)) (count 0) (prevbit (modulo n 2))) (if (zero? n) (cons count rc) (if (eq? (modulo n 2) prevbit) (loop (floor>exact (/ n 2)) rc (1+ count) (modulo n 2)) (loop (floor>exact (/ n 2)) (cons count rc) 1 (modulo n 2)))))))


CROSSREFS

Cf. A003714 (positions of ones), A005361, A005940.
Cf. A000120 (sum of lengths of runs of 1bits), A167489, A227350, A227193, A278222, A245562, A284562, A284569, A283972, A284582, A284583.
Run Length Transforms of other sequences: A246588, A246595, A246596, A246660, A246661, A246674.
Differs from similar A284580 for the first time at n=119, where a(119) = 9, while A284580(119) = 5.
Sequence in context: A284569 A272604 A284580 * A246028 A232186 A161161
Adjacent sequences: A227346 A227347 A227348 * A227350 A227351 A227352


KEYWORD

nonn,base


AUTHOR

Antti Karttunen, Jul 08 2013


EXTENSIONS

Data section extended up to term a(120) by Antti Karttunen, Apr 14 2017


STATUS

approved



