cp's OEIS Frontend

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.

%I A369173 #38 Jan 30 2024 04:11:29
%S A369173 31,301,310,311,3001,3010,3011,3100,3101,3110,30001,30010,30011,30100,
%T A369173 30101,30110,31000,31001,31010,31100,31111,300001,300010,300011,
%U A369173 300100,300101,300110,301000,301001,301010,301100,301111,310000,310001,310010,310100,310111,311000,311011,311101,311110,311111
%N 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.
%C A369173 See A368946 for the description of the MIU formal system.
%C A369173 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 A369173 Strings are encoded using the map M -> 3, I -> 1 and U -> 0, and then sorted.
%C A369173 Row n has length A024495(n).
%D A369173 Douglas R. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979, pp. 33-41 and pp. 261-262.
%H A369173 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 A369173 Wikipedia, <a href="https://en.wikipedia.org/wiki/MU_puzzle">MU Puzzle</a>.
%H A369173 <a href="/index/Go#GEB">Index entries for sequences from "Goedel, Escher, Bach"</a>.
%e A369173 Triangle begins:
%e A369173   [2] 31;
%e A369173   [3] 301 310 311;
%e A369173   [4] 3001 3010 3011 3100 3101 3110;
%e A369173   [5] 30001 30010 30011 30100 30101 30110 31000 31001 31010 31100 31111;
%e A369173   ...
%t A369173 A369173row[n_] := Map[FromDigits[Join[{3}, #]]&, Select[Tuples[{0, 1}, n - 1], !Divisible[Count[#, 1], 3]&]]; Array[A369173row, 5, 2]
%Y A369173 Cf. A368946, A024495 (row lengths), A369174 (number of zeros), A369179 (number of ones), A369409.
%Y A369173 Cf. A369586 (shortest proofs), A369408 (length of shortest proofs), A369587 (number of symbols of shortest proofs).
%K A369173 nonn,tabf,easy
%O A369173 2,1
%A A369173 _Paolo Xausa_, Jan 15 2024