A331536 -id:A331536 - cp's OEIS frontend

A368946 Irregular triangle read by rows: row n lists the strings of the MIU formal system at the n-th level of the tree generated by recursively applying the system rules, starting from the MI string (see comments and example).

31, 310, 311, 31010, 3110, 31111, 310101010, 3110110, 311110, 311111111, 301, 310, 31010101010101010, 3110110110110, 31111011110, 3010, 3100, 3111111110, 31111111111111111, 3011111, 3101111, 3110111, 3111011, 3111101, 3111110, 3010, 30101, 31010

Offset: 0

Paolo Xausa, Jan 10 2024

In the MIU formal system, invented by Douglas R. Hofstadter, we start with the string (axiom) MI and build new strings (theorems) by applying the following rules.
Rule 1: if a string ends with I, we can append U at the end.
Rule 2: if a string is of the form Mx, we can build the string Mxx.
Rule 3: if a string contains III, we can replace it with U.
Rule 4: if a string contains UU, we can remove it.
Hofstadter asks whether the string MU can be obtained by repeatedly applying the above rules and then proves it cannot.
At each recursion level, strings are obtained by applying the rules in order (1 to 4) to each string of the previous level. When the same rule can be applied more than once, it is first applied to the leftmost substring that can be affected.
Following the mapping adopted by Hofstadter himself (see Hofstadter (1979), p. 261), we can encode the characters M, I, and U with 3, 1, and 0, respectively.
See A368953 for a variant where, within a row, duplicates (if present) are removed and encoded strings are lexicographically ordered.
A369173 gives all of the derivable strings within the MIU system.

			After recursively applying the rules three times, we get the following tree (cf. Hofstadter (1979), page 40, Figure 11).
.
                           MI
  0 ---------------------- 31
                         /    \
                        1      2 <--- Rule applied
                       /        \
                     MIU        MII
  1 ---------------- 310        311
                    /          /   \
                   2          1     2
                  /          /       \
              MIUIU       MIIU      MIIII
  2 --------- 31010       3110      31111         Here rule 3 can
               /          /       / |   | \       be applied twice:
              2          2       1  2   3  3 <--- it is first applied
             /          /       /   |   |   \     to the leftmost
        MIUIUIUIU   MIIUIIU  MIIIIU |  MUI  MIU   III substring
  3 --- 310101010   3110110  311110 |  301  310
                                MIIIIIIII
                                311111111
.
By reading the tree from top to bottom, left to right, the triangle begins:
  [0] 31;
  [1] 310 311;
  [2] 31010 3110 31111;
  [3] 310101010 3110110 311110 311111111 301 310;
  [4] 31010101010101010 3110110110110 ... 3010 ... 3010 30101 31010;
  ...
Please note that some strings may be duplicated in different rows and within the same row: within the first four rows, the string MIU (310) is present in rows 1 and 3. In row 4, the string MUIU (3010) is present twice: it can be generated both by applying rule 3 to MIIIIU (311110) and by applying rule 1 to MUI (301). The initial string MI (31) first reappears in row 5.

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

Paolo Xausa, Table of n, a(n) for n = 0..3670 (rows 0..7 of the triangle, flattened).
Wikipedia, MU Puzzle.
Index entries for sequences from "Goedel, Escher, Bach"

Cf. A331536, A368953 (variant).
Cf. A368947 (row lengths), A369172 (length of strings), A369173 (all MIU strings), A369206 (number of zeros), A369207 (number of ones), A369409.
Cf. A369586 (shortest proofs), A369408 (length of shortest proofs), A369587 (number of symbols of shortest proofs).

MIUStepO[s_] := Flatten[Map[{If[StringEndsQ[#, "1"], # <> "0", Nothing], # <> StringDrop[#, 1], StringReplaceList[#, "111" -> "0"], StringReplaceList[#, "00" -> ""]}&, s]];
With[{rowmax = 4}, Map[FromDigits, NestList[MIUStepO, {"31"}, rowmax], {2}]]

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 from [int(t) for t in frontier]
        reach1 = [m for p in frontier for m in moves(p)]
        frontier, reach1 = reach1, []
print(list(islice(agen(), 28))) # Michael S. Branicky, Jan 14 2024

A369408 Irregular triangle read by rows: T(n,k) is the length of the shortest proof for the MIU formal system string (theorem) given by A369173(n,k).

Original entry on oeis.org

1, 4, 2, 2, 11, 5, 8, 5, 8, 3, 9, 9, 6, 9, 5, 6, 9, 6, 3, 6, 3

Offset: 2

Paolo Xausa, Jan 22 2024

See A368946 for the description of the MIU formal system and A369173 for the triangle of the corresponding derivable strings.
The length of the shortest proof for a string (theorem) S is the number of lines of the shortest possible derivation of S.
A369173(n,k) first appears in row T(n,k) - 1 in triangle A368946.

			Triangle begins:
  [2]  1;
  [3]  4  2  2;
  [4] 11  5  8  5  8  3;
  [5]  9  9  6  9  5  6  9  6  3  6  3;
  ...
For the theorem MUI (301), which is given by A369173(3,1), the shortest derivation from the axiom MI is MI (31) -> MII (311) -> MIIII (31111) -> MIU (301) (4 lines), so T(3,1) = 4.

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

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

Cf. A024495 (row lengths), A331536, A368946, A369173, A369410.

Cf. A369586 (proofs), A369587 (number of symbols).

MIUStringsW3[n_] := Map[FromCharacterCode[# + 48]&, Select[Tuples[{0, 1}, n - 1], ! Divisible[Count[#, 1], 3] &]];
MIUStepDW3[s_] := DeleteDuplicates[Flatten[Map[{If[StringEndsQ[#, "1"], # <> "0", Nothing], # <> #, StringReplaceList[#, {"111" -> "0", "00" -> ""}]} &, s]]];
Module[{rowmax = 5, treedepth = 10, tree}, tree = NestList[MIUStepDW3, {"1"}, treedepth]; Map[Quiet[Check[Position[tree, #, {2}][[1,1]], "Not found"]]&, Array[MIUStringsW3, rowmax - 1, 2], {2}]]

T(n,k) <= A369410(n,k).

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

Original entry on oeis.org

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

Offset: 0

Paolo Xausa, Jan 10 2024

See A368946 for the description of the MIU formal system.

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

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

Cf. A331536, A368946, A368954.

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

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

a(n) >= A368954(n).

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

A368953 Irregular triangle read by rows: row n lists (in lexicographical order and with duplicates removed) the strings of the MIU formal system at the n-th level of the tree generated by recursively applying the system rules, starting from the MI string.

Original entry on oeis.org

31, 310, 311, 31010, 3110, 31111, 301, 310, 310101010, 3110110, 311110, 311111111, 3010, 30101, 3011111, 3100, 31010, 31010101010101010, 3101111, 3110110110110, 3110111, 3111011, 3111101, 31111011110, 3111110, 3111111110, 31111111111111111

Offset: 0

Paolo Xausa, Jan 10 2024

This is a variant of A368946 (see there for the description of the MIU system) where, within a row, duplicates are removed and encoded strings are ordered lexicographically.

			After recursively applying the rules three times, we get the following tree (cf. Hofstadter (1979), page 40, Figure 11).
.
                           MI
  0 ---------------------- 31
                         /    \
                        1      2 <--- Rule applied
                       /        \
                     MIU        MII
  1 ---------------- 310        311
                    /          /   \
                   2          1     2
                  /          /       \
              MIUIU       MIIU      MIIII
  2 --------- 31010       3110      31111
               /          /       / |   | \
              2          2       1  2   3  3
             /          /       /   |   |   \
        MIUIUIUIU   MIIUIIU  MIIIIU |  MUI  MIU
  3 --- 310101010   3110110  311110 |  301  310
                                MIIIIIIII
                                311111111
.
After ordering the encoded strings lexicographically within a tree level (and removing duplicates, if present), the triangle begins:
  [0] 31;
  [1] 310 311;
  [2] 31010 3110 31111;
  [3] 301 310 310101010 3110110 311110 311111111;
  ...
Please note that some strings may be present in different rows: within the first four rows, the string MIU (310) is present in rows 1 and 3.

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

Paolo Xausa, Table of n, a(n) for n = 0..16809 (rows 0..8 of the triangle, flattened).
Wikipedia, MU Puzzle
Index entries for sequences from "Goedel, Escher, Bach"

Cf. A331536, A368946, A368954 (row lengths), A369173 (all MIU strings).

MIUStepL[s_] := Union[Flatten[Map[{If[StringEndsQ[#, "1"], # <> "0", Nothing], # <> StringDrop[#, 1], StringReplaceList[#, {"111" -> "0", "00" -> ""}]}&, s]]];
With[{rowmax = 4}, Map[FromDigits, NestList[MIUStepL, {"31"}, rowmax], {2}]]

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

Original entry on oeis.org

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

Offset: 0

Paolo Xausa, Jan 10 2024

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

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

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

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

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

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

a(n) <= A368947(n).

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

A369148 In the MIU formal system, total number (including duplicates) of strings up to n steps distant from the MI string.

Original entry on oeis.org

1, 3, 6, 12, 28, 88, 444, 3671, 47981, 976631, 29554002, 1326494644

Offset: 0

Paolo Xausa, Jan 14 2024

See A368946 for the description of the MIU formal system.

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

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

Cf. A331536 (without duplicates), A368946, A369173 (all MIU strings).

Partial sums of A368947.

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

a(n) >= A331536(n+1).

cp's OEIS Frontend

A368946 Irregular triangle read by rows: row n lists the strings of the MIU formal system at the n-th level of the tree generated by recursively applying the system rules, starting from the MI string (see comments and example).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Python

A369408 Irregular triangle read by rows: T(n,k) is the length of the shortest proof for the MIU formal system string (theorem) given by A369173(n,k).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A368953 Irregular triangle read by rows: row n lists (in lexicographical order and with duplicates removed) the strings of the MIU formal system at the n-th level of the tree generated by recursively applying the system rules, starting from the MI string.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A369148 In the MIU formal system, total number (including duplicates) of strings up to n steps distant from the MI string.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula