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

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

Offset: 0

Author

Antti Karttunen, Jul 08 2013

Keywords

• nonn
• base

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

Examples

			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 1-run is 1.
a(2) = 1, as 2 is "10" in binary, and again there is only one run of 1-bits, of length 1.
a(3) = 2, as 3 is "11" in binary, and there is one run of two 1-bits.
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)
		

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 [math.CO], 2015.
• Index entries for sequences computed with run length transform

Crossrefs

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

Cf. A000120 (sum of lengths of runs of 1-bits), 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.

Programs

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] (* Jean-François Alcover, Mar 02 2016 *)

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

# uses[RLT from 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) (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)))))))

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)

a(4n+1) = a(2n) = a(n). If n is odd, then a(4n+3) = 2*a(2n+1)-a(n). If n is even, then a(4n+3) = 2*a(2n+1) = 2*a(n/2). - Chai Wah Wu, Jul 17 2025

Extensions

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