A369172 Irregular triangle read by rows: row n lists the lengths of 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.

2, 3, 3, 5, 4, 5, 9, 7, 6, 9, 3, 3, 17, 13, 11, 4, 4, 10, 17, 7, 7, 7, 7, 7, 7, 4, 5, 5, 33, 25, 21, 9, 9, 9, 9, 7, 7, 2, 19, 8, 8, 8, 8, 8, 8, 18, 33, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 8, 13, 5, 5, 5, 8, 13, 5, 5, 8, 13, 5, 8, 13, 5, 8, 13, 5, 5, 13, 5, 5, 5, 7, 6, 9, 9

Offset: 0

Author

Paolo Xausa, Jan 15 2024

Keywords

• nonn
• tabf

Comments

See A368946 for the description of the MIU formal system and the triangle of corresponding strings.

Examples

			Triangle begins:
  [0]  2;
  [1]  3  3;
  [2]  5  4  5;
  [3]  9  7  6  9  3  3;
  [4] 17 13 11  4  4 10 17  7  7  7  7  7  7  4  5  5;
  ...
		

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..3670 (rows 0..7 of the triangle, flattened).
• Wikipedia, MU Puzzle.
• Index entries for sequences from "Goedel, Escher, Bach".

Crossrefs

Cf. A055642, A368946, A368947 (row lengths), A369206, A369207.

Programs

Mathematica

MIUStepOW3[s_] := Flatten[Map[{If[StringEndsQ[#, "1"], # <> "0", Nothing], # <> #, StringReplaceList[#, "111" -> "0"], StringReplaceList[#, "00" -> ""]}&, s]];
With[{rowmax = 5}, StringLength[NestList[MIUStepOW3, {"1"}, rowmax]]] + 1

Formula

T(n,k) = A055642(A368946(n,k)).

T(n,k) = A369206(n,k) + A369207(n,k) + 1.