cp's OEIS Frontend

A368947 Row lengths of A368946: in the MIU formal system, number of (possibly not distinct) strings n steps distant from the MI string.

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