

A297824


The number of iterations to remove all runs from the binary string 11011100...n (formed by concatenating the first n binary numbers, see A058935(n)).


2



0, 1, 1, 1, 1, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 6, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 9, 10, 10, 10, 10, 10, 10, 9, 8, 8, 10, 7, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 9, 10, 9, 10, 9, 10, 10, 8, 9, 9, 10, 10, 9, 7, 9, 10, 10, 10, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,6


COMMENTS

Each iteration removes all runs of two or more identical bits that appear at the beginning of that iteration. By definition, the bits of the final string will be an initial segment, possibly empty, of 0, 1, 0, 1, ... (A000035) or 1, 0, 1, 0, ... (A059841). A297825 gives the lengths of the final strings; the sign of each nonzero term indicates which case occurs.


LINKS



EXAMPLE

a(21) = 6 because 1101110010111011110001001101010111100110111101111100001000110010100111010010101 > 01001010100011010110101 > 01101010100101 > 0010101101 > 101001 > 1011 > 10, where each arrow points to the result of one iteration.


PROG

(PARI)
{remove_runs(v) = my(w, run_found = 0);
if(#v == 1, w = v, w = []);
for(k = 2, #v,
if(v[k1] == v[k],
run_found = 1,
if(run_found == 0, w = concat(w, v[k1]), run_found = 0);
if(k == #v, w = concat(w, v[k]))
)
); w}
{a(n) = my(v = [], L, c = 0); \\ remove "write(...); " if don't need other bfile
for(k = 1, n, v = concat(v, binary(k)));
L = #v;
while(1,
v = remove_runs(v);
if(#v == L, write("b297825.txt", n, " ", L*(if(L == 0, 0, 2*v[1]  1))); break, L = #v);
c++
); c}
for(n = 1, 10000, write("b297824.txt", n, " ", a(n))) \\ created two bfiles


CROSSREFS



KEYWORD

nonn,base


AUTHOR



STATUS

approved



