[seqfan] Re: The Ehrenfeucht-Mycielski sequence A038219

[Fred Lunnon]

Neil, is this of any assistance?  Dunno if I'll get around to
improving it!  Regards, Fred
______________________________________________________

# https://oeis.org/A038219 : NJAS requests Maple program, seqfan list 21/05/19
# Dumb program: improve via auxiliary arrays  l_[n], maxi_[n] ? Fred Lunnon

b := [0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1,
1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0,
0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0,
0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1,
0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1];
maxn := nops(b); # number 105 terms ex OEIS

emfun := array(0..max(3,maxn)); # initial sequence values
emfun[0] := 2; emfun[1] := 0; emfun[2] := 1; emfun[3] := 0;
for n from 4 to maxn do # sequence argument
  maxi := n; maxl := 0; # suffix match record: end+1 & length,
  i := n; while i > maxl+1 do
    i := i-1; l := 0; # suffix match current: end+1 & length
    while emfun[i-1-l] = emfun[n-1-l] and i > l+1 do l := l+1 od;
    if l > maxl then maxl := l; maxi := i fi od; # update record
  emfun[n] := 1 - emfun[maxi] od: # update sequence

a := [seq(emfun[i], i = 1..maxn)]; # stripped sentinels
if a = b then true else false fi; # test true
______________________________________________________



On 5/21/19, Neil Sloane <njasloane at gmail.com> wrote:
> Dear Seqfans,  This is a very interesting sequence.  It is by definition a
> "maximally unpredictable sequence", but actually it has a simple
> construction, so of course it is not unpredictable at all.
> There is an open problem: show that 0's and 1's have density 1/2.   This
> might be much easier to settle than the Kolakoski sequence A000002.  (One
> reason I say that is that A253060 and A253061 are so regular.)
>
> There are a bunch of related sequences:
> Cf. A201881 (run lengths).
> Cf. also A253059, Locations of 0's and 1's: A253060, A253061.
> For first appearance of subwords see A308173.
> A308174, A308175 are used in the calculation of a(n).
>
> Remy Sigrist has kindly extended several of these sequences, and has
> provided a 100000-term b-file for A038219, so there is plenty of data.
>
> For once, the Wikipedia article (see the link in A038219) is actually
> helpful.
>
> There is presently no Maple program. The naive algorithm is O(n^3), but the
> Wikipedia article mentions a much faster algorithm in the paper
> Herman, Grzegorz,
> and Soltys, Michael, On the Ehrenfeucht-Mycielski sequence, Journal of
> Discrete Algorithms, 7 (No. 4, 2009), 500-508.
>
> However, even a naive Maple program would be useful.
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>