|
%I #19 Jan 25 2024 14:31:32
%S 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 40,37,34,31,28,25,22,19,128,125,122,119,116,113,110,107,104,101,98,
%U 95,92,89,86,83,80,77,74,71,68,65,62,59,56,53,50,47,44,41,38,35
%N 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 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 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 See A368946 for the description of the MIU formal system.
%D Douglas R. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979, pp. 33-41.
%H 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 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 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>.
%F T(n,1) = n + 1 for n < 2.
%F T(n,k) = 2^n - 3*(k-1) for n >= 2 and 1 <= k <= 2^(n-2).
%e The first levels of the graph are shown below. Cf. Matos and Antunes (1998), p. 7, figure 1.
%e +--1
%e |
%e +--2
%e |
%e +-----------4-----------+
%e | |
%e +-----8-----+ +-----5-----+
%e | | | |
%e +-16--+ +-13--+ +-10--+ +--7--+
%e | | | | | | | |
%e 32 29 26 23 20 17 14 11
%e ...
%e Written as an irregular triangle, the sequence begins:
%e [0] 1;
%e [1] 2;
%e [2] 4;
%e [3] 8 5;
%e [4] 16 13 10 7;
%e [5] 32 29 26 23 20 17 14 11;
%e ...
%t A369414row[n_] := If[n <= 1, {n+1}, Range[2^n, 3+2^(n-2), -3]];
%t Array[A369414row, 8, 0]
%Y Cf. A368946, A369409.
%Y Cf. A000079 (first column and, for n >= 2, row lengths), A062709 (right border, for n >= 2).
%Y Permutation of A001651.
%K nonn,tabf,easy
%O 0,2
%A _Paolo Xausa_, Jan 24 2024
|
