A368947
Row lengths of A368946: in the MIU formal system, number of (possibly not distinct) strings n steps distant from the MI string.
Original entry on oeis.org
1, 2, 3, 6, 16, 60, 356, 3227, 44310, 928650, 28577371, 1296940642
Offset: 0
- Douglas R. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979, pp. 33-41.
-
MIUStepW3[s_] := Flatten[Map[{If[StringEndsQ[#, "1"], # <> "0", Nothing], # <> #, StringReplaceList[#, {"111" -> "0","00" -> ""}]}&, s]];
With[{rowmax = 9}, Map[Length, NestList[MIUStepW3, {"1"}, rowmax]]]
-
from itertools import islice
def occurrence_swaps(w, s, t):
out, oi = [], w.find(s)
while oi != -1:
out.append(w[:oi] + t + w[oi+len(s):])
oi = w.find(s, oi+1)
return out
def moves(w): # moves for word w in MIU system, encoded as 310
nxt = []
if w[-1] == '1': nxt.append(w + '0') # Rule 1
if w[0] == '3': nxt.append(w + w[1:]) # Rule 2
nxt.extend(occurrence_swaps(w, '111', '0')) # Rule 3
nxt.extend(occurrence_swaps(w, '00', '')) # Rule 4
return nxt
def agen(): # generator of terms
frontier = ['31']
while len(frontier) > 0:
yield len(frontier)
reach1 = [m for p in frontier for m in moves(p)]
frontier, reach1 = reach1, []
print(list(islice(agen(), 10))) # Michael S. Branicky, Jan 14 2024
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.
Original entry on oeis.org
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
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.
- Douglas R. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979, pp. 33-41 and pp. 261-262.
-
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}]]
Showing 1-2 of 2 results.
Comments