login
The binary "look and say" sequence.
10

%I #63 Oct 05 2022 22:58:18

%S 1,11,101,111011,11110101,100110111011,111001011011110101,

%T 111100111010110100110111011,100110011110111010110111001011011110101,

%U 1110010110010011011110111010110111100111010110100110111011

%N The binary "look and say" sequence.

%C I conjecture that the ratio r(n) of the number of "1"s to the number of "0"s in a(n) converges to 5/3 (or some nearby limit). - _Joseph L. Pe_, Jan 31 2003

%C The ratio r(n) of the number of "1"s to the number of "0"s in a(n) actually converges to ((101 - 10*sqrt(93))*a^2 + (139 - 13*sqrt(93))*a - 76)/108, where a = (116 + 12*sqrt(93))^(1/3). This ratio has decimal expansion 1.6657272222676... - _Nathaniel Johnston_, Nov 07 2010 [Corrected by _Kevin J. Gomez_, Dec 12 2017]

%C Reading terms as binary numbers and converting to decimal gives A049190. - _Andrey Zabolotskiy_, Dec 12 2017

%C From _Jianing Song_, Oct 05 2022: (Start)

%C "000" or "11111" never appear in any a(n). Proof:

%C When "000" appears for the first time in a(n),

%C - if it reads as "..00 0's", then a(n-1) must contain at least 4 consecutive 0's, which is impossible;

%C - if it reads as "...000... 0's" or "...000... 1's", then a(n-1) must contain at least 8 consecutive 0's or at least 8 consecutive 1's.

%C In conclusion, a(n-1) must contain at least 8 consecutive 1's.

%C When "11111" appears for the first time in a(n),

%C - if it reads as "...1111 1's", then a(n-1) must contain at least 15 consecutive 1's, which is impossible;

%C - if it reads as "...111 1's, 1... 0's", then a(n-1) must contain at least 7 consecutive 1's, which is impossible;

%C - if it reads as "...11 1's, 11... 0's", then a(n-1) must contain at least 3 consecutive 0's;

%C - if it reads as "...1 1's, 111... 0's", then a(n-1) must contain at least 7 consecutive 0's;

%C - if it reads as "... 1's, 1111... 0's", then a(n-1) must contain at least 15 consecutive 0's;

%C - if it reads as "...11111... 0's" or "...11111... 1's", then a(n-1) must contain at least 31 consecutive 0's or at least 31 consecutive 1's.

%C In conclusion, a(n-1) must contain at least 3 consecutive 0's. Combining these two results, one can easily show that "000" or "11111" cannot appear. (End)

%H John Cerkan, <a href="/A001387/b001387.txt">Table of n, a(n) for n = 1..17</a>

%H J. H. Conway, <a href="https://doi.org/10.1007/978-1-4612-4808-8_53">The weird and wonderful chemistry of audioactive decay</a>, Eureka 46 (1986) 5-16, reprinted in: Open Problems in Communications and Computations, Springer, 1987, 173-188.

%H Nathaniel Johnston, <a href="http://www.nathanieljohnston.com/2010/11/the-binary-look-and-say-sequence/">The Binary "Look-and-Say" Sequence</a>

%H Thomas Morrill, <a href="https://arxiv.org/abs/2004.06414">Look, Knave</a>, arXiv:2004.06414 [math.CO], 2020.

%H Torsten Sillke, <a href="http://www.mathematik.uni-bielefeld.de/~sillke/SEQUENCES/series001">The binary form of Conway's sequence</a>

%e To get the 5th term, for example, note that 4th term has three (11 in binary!) 1's, one (1) 0 and two (10) 1's, giving 11 1 1 0 10 1.

%t a[1] := 1; a[n_] := a[n] = FromDigits[Flatten[{IntegerDigits[Length[#],2], First[#]}& /@ Split[IntegerDigits[a[n-1]]]]]; Map[a, Range[20]] (* _Peter J. C. Moses_, Mar 24 2013 *)

%t Nest[Append[#, FromDigits@ Flatten@ Map[Reverse /@ IntegerDigits[Tally@ #, 2] &, Split@ IntegerDigits@ Last@ #]] &, {1}, 9] (* _Michael De Vlieger_, Dec 12 2017 *)

%o (Python)

%o from itertools import accumulate, groupby, repeat

%o def summarize(n, _): return int("".join(bin(len(list(g)))[2:]+k for k, g in groupby(str(n))))

%o def aupto(terms): return list(accumulate(repeat(1, terms), summarize))

%o print(aupto(11)) # _Michael S. Branicky_, Sep 18 2022

%Y Cf. A005150, A001391, A049190, A049194.

%K nonn,base

%O 1,2

%A _Thomas L. York_

%E New name from _Andrey Zabolotskiy_, Dec 13 2017