cp's OEIS Frontend

A368954 Row lengths of A368953: in the MIU formal system, number of distinct strings n steps distant from the MI string.

%I A368954 #32 Jan 25 2024 15:02:00
%S A368954 1,2,3,6,15,48,232,1544,14959,203333,3919437,105126522
%N A368954 Row lengths of A368953: in the MIU formal system, number of distinct strings n steps distant from the MI string.
%C A368954 See A368946 for the description of the MIU formal system and A368953 for the variant where duplicates within a row are removed.
%D A368954 Douglas R. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979, pp. 33-41.
%H A368954 Wikipedia, <a href="https://en.wikipedia.org/wiki/MU_puzzle">MU Puzzle</a>.
%H A368954 <a href="/index/Go#GEB">Index entries for sequences from "Goedel, Escher, Bach"</a>
%F A368954 a(n) <= A368947(n).
%t A368954 MIUStepDW3[s_] := DeleteDuplicates[Flatten[Map[{If[StringEndsQ[#, "1"], # <> "0", Nothing], # <> #, StringReplaceList[#, {"111" -> "0","00" -> ""}]}&, s]]];
%t A368954 With[{rowmax = 9}, Map[Length, NestList[MIUStepDW3, {"1"}, rowmax]]]
%o A368954 (Python)
%o A368954 from itertools import islice
%o A368954 def occurrence_swaps(w, s, t):
%o A368954     out, oi = [], w.find(s)
%o A368954     while oi != -1:
%o A368954         out.append(w[:oi] + t + w[oi+len(s):])
%o A368954         oi = w.find(s, oi+1)
%o A368954     return out
%o A368954 def moves(w): # moves for word w in MIU system, encoded as 310
%o A368954     nxt = []
%o A368954     if w[-1] == '1': nxt.append(w + '0')        # Rule 1
%o A368954     if w[0] == '3': nxt.append(w + w[1:])       # Rule 2
%o A368954     nxt.extend(occurrence_swaps(w, '111', '0')) # Rule 3
%o A368954     nxt.extend(occurrence_swaps(w, '00', ''))   # Rule 4
%o A368954     return nxt
%o A368954 def agen(): # generator of terms
%o A368954     frontier = {'31'}
%o A368954     while len(frontier) > 0:
%o A368954         yield len(frontier)
%o A368954         reach1 = set(m for p in frontier for m in moves(p))
%o A368954         frontier, reach1 = reach1, set()
%o A368954 print(list(islice(agen(), 10))) # _Michael S. Branicky_, Jan 14 2024
%Y A368954 Cf. A331536, A368946, A368947, A368953, A369408.
%K A368954 nonn,hard,more
%O A368954 0,2
%A A368954 _Paolo Xausa_, Jan 10 2024
%E A368954 a(10)-a(11) from _Michael S. Branicky_, Jan 14 2024