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).

%I A368946 #61 Jan 30 2024 03:43:09
%S A368946 31,310,311,31010,3110,31111,310101010,3110110,311110,311111111,301,
%T A368946 310,31010101010101010,3110110110110,31111011110,3010,3100,3111111110,
%U A368946 31111111111111111,3011111,3101111,3110111,3111011,3111101,3111110,3010,30101,31010
%N 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).
%C A368946 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.
%C A368946 Rule 1: if a string ends with I, we can append U at the end.
%C A368946 Rule 2: if a string is of the form Mx, we can build the string Mxx.
%C A368946 Rule 3: if a string contains III, we can replace it with U.
%C A368946 Rule 4: if a string contains UU, we can remove it.
%C A368946 Hofstadter asks whether the string MU can be obtained by repeatedly applying the above rules and then proves it cannot.
%C A368946 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.
%C A368946 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.
%C A368946 See A368953 for a variant where, within a row, duplicates (if present) are removed and encoded strings are lexicographically ordered.
%C A368946 A369173 gives all of the derivable strings within the MIU system.
%D A368946 Douglas R. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979, pp. 33-41 and pp. 261-262.
%H A368946 Paolo Xausa, <a href="/A368946/b368946.txt">Table of n, a(n) for n = 0..3670</a> (rows 0..7 of the triangle, flattened).
%H A368946 Wikipedia, <a href="https://en.wikipedia.org/wiki/MU_puzzle">MU Puzzle</a>.
%H A368946 <a href="/index/Go#GEB">Index entries for sequences from "Goedel, Escher, Bach"</a>
%e A368946 After recursively applying the rules three times, we get the following tree (cf. Hofstadter (1979), page 40, Figure 11).
%e A368946 .
%e A368946                            MI
%e A368946   0 ---------------------- 31
%e A368946                          /    \
%e A368946                         1      2 <--- Rule applied
%e A368946                        /        \
%e A368946                      MIU        MII
%e A368946   1 ---------------- 310        311
%e A368946                     /          /   \
%e A368946                    2          1     2
%e A368946                   /          /       \
%e A368946               MIUIU       MIIU      MIIII
%e A368946   2 --------- 31010       3110      31111         Here rule 3 can
%e A368946                /          /       / |   | \       be applied twice:
%e A368946               2          2       1  2   3  3 <--- it is first applied
%e A368946              /          /       /   |   |   \     to the leftmost
%e A368946         MIUIUIUIU   MIIUIIU  MIIIIU |  MUI  MIU   III substring
%e A368946   3 --- 310101010   3110110  311110 |  301  310
%e A368946                                 MIIIIIIII
%e A368946                                 311111111
%e A368946 .
%e A368946 By reading the tree from top to bottom, left to right, the triangle begins:
%e A368946   [0] 31;
%e A368946   [1] 310 311;
%e A368946   [2] 31010 3110 31111;
%e A368946   [3] 310101010 3110110 311110 311111111 301 310;
%e A368946   [4] 31010101010101010 3110110110110 ... 3010 ... 3010 30101 31010;
%e A368946   ...
%e A368946 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.
%t A368946 MIUStepO[s_] := Flatten[Map[{If[StringEndsQ[#, "1"], # <> "0", Nothing], # <> StringDrop[#, 1], StringReplaceList[#, "111" -> "0"], StringReplaceList[#, "00" -> ""]}&, s]];
%t A368946 With[{rowmax = 4}, Map[FromDigits, NestList[MIUStepO, {"31"}, rowmax], {2}]]
%o A368946 (Python)
%o A368946 from itertools import islice
%o A368946 def occurrence_swaps(w, s, t):
%o A368946     out, oi = [], w.find(s)
%o A368946     while oi != -1:
%o A368946         out.append(w[:oi] + t + w[oi+len(s):])
%o A368946         oi = w.find(s, oi+1)
%o A368946     return out
%o A368946 def moves(w): # moves for word w in MIU system, encoded as 310
%o A368946     nxt = []
%o A368946     if w[-1] == '1': nxt.append(w + '0')        # Rule 1
%o A368946     if w[0] == '3': nxt.append(w + w[1:])       # Rule 2
%o A368946     nxt.extend(occurrence_swaps(w, '111', '0')) # Rule 3
%o A368946     nxt.extend(occurrence_swaps(w, '00', ''))   # Rule 4
%o A368946     return nxt
%o A368946 def agen(): # generator of terms
%o A368946     frontier = ['31']
%o A368946     while len(frontier) > 0:
%o A368946         yield from [int(t) for t in frontier]
%o A368946         reach1 = [m for p in frontier for m in moves(p)]
%o A368946         frontier, reach1 = reach1, []
%o A368946 print(list(islice(agen(), 28))) # _Michael S. Branicky_, Jan 14 2024
%Y A368946 Cf. A331536, A368953 (variant).
%Y A368946 Cf. A368947 (row lengths), A369172 (length of strings), A369173 (all MIU strings), A369206 (number of zeros), A369207 (number of ones), A369409.
%Y A368946 Cf. A369586 (shortest proofs), A369408 (length of shortest proofs), A369587 (number of symbols of shortest proofs).
%K A368946 nonn,tabf
%O A368946 0,1
%A A368946 _Paolo Xausa_, Jan 10 2024