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,1

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.

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"

Example

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.

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

Crossrefs

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

Sequence in context: A295975 A002225 A124335 * A368946 A042870 A152033

Adjacent sequences: A368950 A368951 A368952 * A368954 A368955 A368956

Keyword

nonn,tabf

Author

Paolo Xausa, Jan 10 2024

Status

approved