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,2

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.

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

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

Example

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

Mathematica

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

Crossrefs

Cf. A368946, A369409.

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

Permutation of A001651.

Sequence in context: A361191 A248573 A372129 * A125733 A333555 A352378

Adjacent sequences: A369411 A369412 A369413 * A369415 A369416 A369417

Keyword

nonn,tabf,easy

Author

Paolo Xausa, Jan 24 2024

Status

approved