A369173 Irregular triangle read by rows: row n lists all of the distinct derivable strings in the MIU formal system that are n characters long.

31, 301, 310, 311, 3001, 3010, 3011, 3100, 3101, 3110, 30001, 30010, 30011, 30100, 30101, 30110, 31000, 31001, 31010, 31100, 31111, 300001, 300010, 300011, 300100, 300101, 300110, 301000, 301001, 301010, 301100, 301111, 310000, 310001, 310010, 310100, 310111, 311000, 311011, 311101, 311110, 311111

Offset: 2

Author

Paolo Xausa, Jan 15 2024

Keywords

• nonn
• tabf
• easy

Comments

See A368946 for the description of the MIU formal system.

A string S can be derived in the MIU formal system if and only if S contains just one M (as its first character) and an arbitrary number of I and U characters, where the number of I characters is not divisible by 3 (see Wikipedia link).

Strings are encoded using the map M -> 3, I -> 1 and U -> 0, and then sorted.

Row n has length A024495(n).

Examples

			Triangle begins:
  [2] 31;
  [3] 301 310 311;
  [4] 3001 3010 3011 3100 3101 3110;
  [5] 30001 30010 30011 30100 30101 30110 31000 31001 31010 31100 31111;
  ...
		

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

Crossrefs

Cf. A368946, A024495 (row lengths), A369174 (number of zeros), A369179 (number of ones), A369409.

Cf. A369586 (shortest proofs), A369408 (length of shortest proofs), A369587 (number of symbols of shortest proofs).

Programs

Mathematica

A369173row[n_] := Map[FromDigits[Join[{3}, #]]&, Select[Tuples[{0, 1}, n - 1], !Divisible[Count[#, 1], 3]&]]; Array[A369173row, 5, 2]