cp's OEIS Frontend

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.

%I A368953 #29 Jan 18 2024 07:48:19
%S A368953 31,310,311,31010,3110,31111,301,310,310101010,3110110,311110,
%T A368953 311111111,3010,30101,3011111,3100,31010,31010101010101010,3101111,
%U A368953 3110110110110,3110111,3111011,3111101,31111011110,3111110,3111111110,31111111111111111
%N 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.
%C A368953 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.
%D A368953 Douglas R. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979, pp. 33-41 and pp. 261-262.
%H A368953 Paolo Xausa, <a href="/A368953/b368953.txt">Table of n, a(n) for n = 0..16809</a> (rows 0..8 of the triangle, flattened).
%H A368953 Wikipedia, <a href="https://en.wikipedia.org/wiki/MU_puzzle">MU Puzzle</a>
%H A368953 <a href="/index/Go#GEB">Index entries for sequences from "Goedel, Escher, Bach"</a>
%e A368953 After recursively applying the rules three times, we get the following tree (cf. Hofstadter (1979), page 40, Figure 11).
%e A368953 .
%e A368953                            MI
%e A368953   0 ---------------------- 31
%e A368953                          /    \
%e A368953                         1      2 <--- Rule applied
%e A368953                        /        \
%e A368953                      MIU        MII
%e A368953   1 ---------------- 310        311
%e A368953                     /          /   \
%e A368953                    2          1     2
%e A368953                   /          /       \
%e A368953               MIUIU       MIIU      MIIII
%e A368953   2 --------- 31010       3110      31111
%e A368953                /          /       / |   | \
%e A368953               2          2       1  2   3  3
%e A368953              /          /       /   |   |   \
%e A368953         MIUIUIUIU   MIIUIIU  MIIIIU |  MUI  MIU
%e A368953   3 --- 310101010   3110110  311110 |  301  310
%e A368953                                 MIIIIIIII
%e A368953                                 311111111
%e A368953 .
%e A368953 After ordering the encoded strings lexicographically within a tree level (and removing duplicates, if present), the triangle begins:
%e A368953   [0] 31;
%e A368953   [1] 310 311;
%e A368953   [2] 31010 3110 31111;
%e A368953   [3] 301 310 310101010 3110110 311110 311111111;
%e A368953   ...
%e A368953 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.
%t A368953 MIUStepL[s_] := Union[Flatten[Map[{If[StringEndsQ[#, "1"], # <> "0", Nothing], # <> StringDrop[#, 1], StringReplaceList[#, {"111" -> "0", "00" -> ""}]}&, s]]];
%t A368953 With[{rowmax = 4}, Map[FromDigits, NestList[MIUStepL, {"31"}, rowmax], {2}]]
%Y A368953 Cf. A331536, A368946, A368954 (row lengths), A369173 (all MIU strings).
%K A368953 nonn,tabf
%O A368953 0,1
%A A368953 _Paolo Xausa_, Jan 10 2024