cp's OEIS Frontend

A369414 Irregular triangle read by rows: row n lists the values of the vertices at the n-th level of the MI graph (see comments).

%I A369414 #19 Jan 25 2024 14:31:32
%S A369414 1,2,4,8,5,16,13,10,7,32,29,26,23,20,17,14,11,64,61,58,55,52,49,46,43,
%T A369414 40,37,34,31,28,25,22,19,128,125,122,119,116,113,110,107,104,101,98,
%U A369414 95,92,89,86,83,80,77,74,71,68,65,62,59,56,53,50,47,44,41,38,35
%N A369414 Irregular triangle read by rows: row n lists the values of the vertices at the n-th level of the MI graph (see comments).
%C A369414 The vertices of the graph consist of all of the positive integers that are not divisible by 3. A vertex v (for v >= 4) has 2*v as left child and 2*v - 3 as right child (see example).
%C A369414 Matos and Antunes (1998) use this graph to illustrate the fact that, for a string (theorem) S belonging to the MIU formal system containing no U characters, the length of the path from vertex v (where v is the number of I characters in S) to the root corresponds to the number of times step 2 of their algorithm for generating "normal" proofs (described in A369409) is applied.
%C A369414 See A368946 for the description of the MIU formal system.
%D A369414 Douglas R. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979, pp. 33-41.
%H A369414 Paolo Xausa, <a href="/A369414/b369414.txt">Table of n, a(n) for n = 0..16384</a> (rows 0..15 of the triangle, flattened).
%H A369414 Armando B. Matos and Luis Filipe Antunes, <a href="https://www.researchgate.net/publication/2845974_Short_proofs_for_MIU_theorems">Short Proofs for MIU theorems</a>, Technical Report Series DCC-98-01, University of Porto, 1998.
%H A369414 Wikipedia, <a href="https://en.wikipedia.org/wiki/MU_puzzle">MU Puzzle</a>.
%H A369414 <a href="/index/Go#GEB">Index entries for sequences from "Goedel, Escher, Bach"</a>.
%F A369414 T(n,1) = n + 1 for n < 2.
%F A369414 T(n,k) = 2^n - 3*(k-1) for n >= 2 and 1 <= k <= 2^(n-2).
%e A369414 The first levels of the graph are shown below. Cf. Matos and Antunes (1998), p. 7, figure 1.
%e A369414                            +--1
%e A369414                            |
%e A369414                         +--2
%e A369414                         |
%e A369414             +-----------4-----------+
%e A369414             |                       |
%e A369414       +-----8-----+           +-----5-----+
%e A369414       |           |           |           |
%e A369414    +-16--+     +-13--+     +-10--+     +--7--+
%e A369414    |     |     |     |     |     |     |     |
%e A369414   32    29    26    23    20    17    14    11
%e A369414                        ...
%e A369414 Written as an irregular triangle, the sequence begins:
%e A369414   [0]  1;
%e A369414   [1]  2;
%e A369414   [2]  4;
%e A369414   [3]  8  5;
%e A369414   [4] 16 13 10  7;
%e A369414   [5] 32 29 26 23 20 17 14 11;
%e A369414   ...
%t A369414 A369414row[n_] := If[n <= 1, {n+1}, Range[2^n, 3+2^(n-2), -3]];
%t A369414 Array[A369414row, 8, 0]
%Y A369414 Cf. A368946, A369409.
%Y A369414 Cf. A000079 (first column and, for n >= 2, row lengths), A062709 (right border, for n >= 2).
%Y A369414 Permutation of A001651.
%K A369414 nonn,tabf,easy
%O A369414 0,2
%A A369414 _Paolo Xausa_, Jan 24 2024