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

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, 40, 37, 34, 31, 28, 25, 22, 19, 128, 125, 122, 119, 116, 113, 110, 107, 104, 101, 98, 95, 92, 89, 86, 83, 80, 77, 74, 71, 68, 65, 62, 59, 56, 53, 50, 47, 44, 41, 38, 35

Offset: 0

Author

Paolo Xausa, Jan 24 2024

Keywords

• nonn
• tabf
• easy

Comments

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

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.

See A368946 for the description of the MIU formal system.

Examples

			The first levels of the graph are shown below. Cf. Matos and Antunes (1998), p. 7, figure 1.
                           +--1
                           |
                        +--2
                        |
            +-----------4-----------+
            |                       |
      +-----8-----+           +-----5-----+
      |           |           |           |
   +-16--+     +-13--+     +-10--+     +--7--+
   |     |     |     |     |     |     |     |
  32    29    26    23    20    17    14    11
                       ...
Written as an irregular triangle, the sequence begins:
  [0]  1;
  [1]  2;
  [2]  4;
  [3]  8  5;
  [4] 16 13 10  7;
  [5] 32 29 26 23 20 17 14 11;
  ...
		

References

• Douglas R. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979, pp. 33-41.

Links

• Paolo Xausa, Table of n, a(n) for n = 0..16384 (rows 0..15 of the triangle, flattened).
• Armando B. Matos and Luis Filipe Antunes, Short Proofs for MIU theorems, Technical Report Series DCC-98-01, University of Porto, 1998.
• Wikipedia, MU Puzzle.
• Index entries for sequences from "Goedel, Escher, Bach".

Crossrefs

Cf. A368946, A369409.

Cf. A000079 (first column and, for n >= 2, row lengths), A062709 (right border, for n >= 2).

Permutation of A001651.

Programs

Mathematica

A369414row[n_] := If[n <= 1, {n+1}, Range[2^n, 3+2^(n-2), -3]];
Array[A369414row, 8, 0]

Formula

T(n,1) = n + 1 for n < 2.

T(n,k) = 2^n - 3*(k-1) for n >= 2 and 1 <= k <= 2^(n-2).