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

%I #38 Jan 30 2024 04:11:29

%S 31,301,310,311,3001,3010,3011,3100,3101,3110,30001,30010,30011,30100,

%T 30101,30110,31000,31001,31010,31100,31111,300001,300010,300011,

%U 300100,300101,300110,301000,301001,301010,301100,301111,310000,310001,310010,310100,310111,311000,311011,311101,311110,311111

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

%C See A368946 for the description of the MIU formal system.

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

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

%C Row n has length A024495(n).

%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="/A369173/b369173.txt">Table of n, a(n) for n = 2..10922</a> (rows 2..14 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 Triangle begins:

%e [2] 31;

%e [3] 301 310 311;

%e [4] 3001 3010 3011 3100 3101 3110;

%e [5] 30001 30010 30011 30100 30101 30110 31000 31001 31010 31100 31111;

%e ...

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

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

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

%K nonn,tabf,easy

%O 2,1

%A _Paolo Xausa_, Jan 15 2024