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

1, 2, 3, 6, 16, 60, 356, 3227, 44310, 928650, 28577371, 1296940642

Offset: 0

Author

Paolo Xausa, Jan 10 2024

Keywords

• nonn
• hard
• more

Comments

See A368946 for the description of the MIU formal system.

References

• Douglas R. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979, pp. 33-41.

Links

• Wikipedia, MU Puzzle.
• Index entries for sequences from "Goedel, Escher, Bach"

Crossrefs

Cf. A331536, A368946, A368954.

Programs

Mathematica

MIUStepW3[s_] := Flatten[Map[{If[StringEndsQ[#, "1"], # <> "0", Nothing], # <> #, StringReplaceList[#, {"111" -> "0","00" -> ""}]}&, s]];
With[{rowmax = 9}, Map[Length, NestList[MIUStepW3, {"1"}, rowmax]]]

Python

from itertools import islice
def occurrence_swaps(w, s, t):
    out, oi = [], w.find(s)
    while oi != -1:
        out.append(w[:oi] + t + w[oi+len(s):])
        oi = w.find(s, oi+1)
    return out
def moves(w): # moves for word w in MIU system, encoded as 310
    nxt = []
    if w[-1] == '1': nxt.append(w + '0')        # Rule 1
    if w[0] == '3': nxt.append(w + w[1:])       # Rule 2
    nxt.extend(occurrence_swaps(w, '111', '0')) # Rule 3
    nxt.extend(occurrence_swaps(w, '00', ''))   # Rule 4
    return nxt
def agen(): # generator of terms
    frontier = ['31']
    while len(frontier) > 0:
        yield len(frontier)
        reach1 = [m for p in frontier for m in moves(p)]
        frontier, reach1 = reach1, []
print(list(islice(agen(), 10))) # Michael S. Branicky, Jan 14 2024

Formula

a(n) >= A368954(n).

Extensions

a(10)-a(11) from Michael S. Branicky, Jan 14 2024