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.

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

Author

Paolo Xausa, Jan 10 2024

Keywords

• nonn
• tabf

Comments

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.

Examples

			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.
		

References

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

Links

• 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"

Crossrefs

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

Programs

Mathematica

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}]]