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

1, 2, 3, 6, 15, 48, 232, 1544, 14959, 203333, 3919437, 105126522

Offset

0,2

Comments

See A368946 for the description of the MIU formal system and A368953 for the variant where duplicates within a row are removed.

References

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

Links

Table of n, a(n) for n=0..11.

Wikipedia, MU Puzzle.

Index entries for sequences from "Goedel, Escher, Bach"

Formula

a(n) <= A368947(n).

Mathematica

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

Prog

(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 = set(m for p in frontier for m in moves(p))
        frontier, reach1 = reach1, set()
print(list(islice(agen(), 10))) # Michael S. Branicky, Jan 14 2024

Crossrefs

Cf. A331536, A368946, A368947, A368953, A369408.

Sequence in context: A141351 A088793 A322197 * A216144 A121688 A082094

Adjacent sequences: A368951 A368952 A368953 * A368955 A368956 A368957

Keyword

nonn,hard,more

Author

Paolo Xausa, Jan 10 2024

Extensions

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

Status

approved