login
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.
4

%I #29 Jan 18 2024 07:48:19

%S 31,310,311,31010,3110,31111,301,310,310101010,3110110,311110,

%T 311111111,3010,30101,3011111,3100,31010,31010101010101010,3101111,

%U 3110110110110,3110111,3111011,3111101,31111011110,3111110,3111111110,31111111111111111

%N 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 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 Douglas R. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979, pp. 33-41 and pp. 261-262.

%H 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 Wikipedia, <a href="https://en.wikipedia.org/wiki/MU_puzzle">MU Puzzle</a>

%H <a href="/index/Go#GEB">Index entries for sequences from "Goedel, Escher, Bach"</a>

%e After recursively applying the rules three times, we get the following tree (cf. Hofstadter (1979), page 40, Figure 11).

%e .

%e MI

%e 0 ---------------------- 31

%e / \

%e 1 2 <--- Rule applied

%e / \

%e MIU MII

%e 1 ---------------- 310 311

%e / / \

%e 2 1 2

%e / / \

%e MIUIU MIIU MIIII

%e 2 --------- 31010 3110 31111

%e / / / | | \

%e 2 2 1 2 3 3

%e / / / | | \

%e MIUIUIUIU MIIUIIU MIIIIU | MUI MIU

%e 3 --- 310101010 3110110 311110 | 301 310

%e MIIIIIIII

%e 311111111

%e .

%e After ordering the encoded strings lexicographically within a tree level (and removing duplicates, if present), the triangle begins:

%e [0] 31;

%e [1] 310 311;

%e [2] 31010 3110 31111;

%e [3] 301 310 310101010 3110110 311110 311111111;

%e ...

%e 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 MIUStepL[s_] := Union[Flatten[Map[{If[StringEndsQ[#, "1"], # <> "0", Nothing], # <> StringDrop[#, 1], StringReplaceList[#, {"111" -> "0", "00" -> ""}]}&, s]]];

%t With[{rowmax = 4}, Map[FromDigits, NestList[MIUStepL, {"31"}, rowmax], {2}]]

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

%K nonn,tabf

%O 0,1

%A _Paolo Xausa_, Jan 10 2024