A368946 -id:A368946 - cp's OEIS frontend

A369172 Irregular triangle read by rows: row n lists the lengths of the strings of the MIU formal system at the n-th level of the tree generated by recursively applying the system rules, starting from the MI string.

2, 3, 3, 5, 4, 5, 9, 7, 6, 9, 3, 3, 17, 13, 11, 4, 4, 10, 17, 7, 7, 7, 7, 7, 7, 4, 5, 5, 33, 25, 21, 9, 9, 9, 9, 7, 7, 2, 19, 8, 8, 8, 8, 8, 8, 18, 33, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 8, 13, 5, 5, 5, 8, 13, 5, 5, 8, 13, 5, 8, 13, 5, 8, 13, 5, 5, 13, 5, 5, 5, 7, 6, 9, 9

Offset: 0

Paolo Xausa, Jan 15 2024

See A368946 for the description of the MIU formal system and the triangle of corresponding strings.

			Triangle begins:
  [0]  2;
  [1]  3  3;
  [2]  5  4  5;
  [3]  9  7  6  9  3  3;
  [4] 17 13 11  4  4 10 17  7  7  7  7  7  7  4  5  5;
  ...

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

Paolo Xausa, Table of n, a(n) for n = 0..3670 (rows 0..7 of the triangle, flattened).
Wikipedia, MU Puzzle.
Index entries for sequences from "Goedel, Escher, Bach".

Cf. A055642, A368946, A368947 (row lengths), A369206, A369207.

MIUStepOW3[s_] := Flatten[Map[{If[StringEndsQ[#, "1"], # <> "0", Nothing], # <> #, StringReplaceList[#, "111" -> "0"], StringReplaceList[#, "00" -> ""]}&, s]];
With[{rowmax = 5}, StringLength[NestList[MIUStepOW3, {"1"}, rowmax]]] + 1

T(n,k) = A055642(A368946(n,k)).

T(n,k) = A369206(n,k) + A369207(n,k) + 1.

A369206 Irregular triangle read by rows: row n lists the number of U characters for each of the strings of the MIU formal system at the n-th level of the tree generated by recursively applying the system rules, starting from the MI string.

Original entry on oeis.org

0, 1, 0, 2, 1, 0, 4, 2, 1, 0, 1, 1, 8, 4, 2, 2, 2, 1, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 16, 8, 4, 3, 3, 3, 3, 4, 4, 0, 2, 2, 2, 2, 2, 2, 2, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 3, 4, 4

Offset: 0

Paolo Xausa, Jan 16 2024

See A368946 for the description of the MIU formal system and the triangle of corresponding strings.

			Triangle begins:
  [0] 0;
  [1] 1 0;
  [2] 2 1 0;
  [3] 4 2 1 0 1 1;
  [4] 8 4 2 2 2 1 0 1 1 1 1 1 1 2 2 2;
  ...

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

Paolo Xausa, Table of n, a(n) for n = 0..3670 (rows 0..7 of the triangle, flattened).
Wikipedia, MU Puzzle.
Index entries for sequences from "Goedel, Escher, Bach".

Cf. A055641, A368946, A368947 (row lengths), A369172, A369207 (number of ones).

MIUStepOW3[s_] := Flatten[Map[{If[StringEndsQ[#, "1"], # <> "0", Nothing], # <> #, StringReplaceList[#, "111" -> "0"], StringReplaceList[#, "00" -> ""]}&, s]];
With[{rowmax = 5}, Map[StringCount[#, "0"]&, NestList[MIUStepOW3, {"1"}, rowmax]]]

T(n,k) = A055641(A368946(n,k)).

T(n,k) = A369172(n,k) - A369207(n,k) - 1.

A369207 Irregular triangle read by rows: row n lists the number of I characters for each of the strings of the MIU formal system at the n-th level of the tree generated by recursively applying the system rules, starting from the MI string.

Original entry on oeis.org

1, 1, 2, 2, 2, 4, 4, 4, 4, 8, 1, 1, 8, 8, 8, 1, 1, 8, 16, 5, 5, 5, 5, 5, 5, 1, 2, 2, 16, 16, 16, 5, 5, 5, 5, 2, 2, 1, 16, 5, 5, 5, 5, 5, 5, 16, 32, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 5, 10, 2, 2, 2, 5, 10, 2, 2, 5, 10, 2, 5, 10, 2, 5, 10, 2, 2, 10, 2, 2, 2, 2, 2, 4, 4

Offset: 0

Paolo Xausa, Jan 16 2024

See A368946 for the description of the MIU formal system and the triangle of corresponding strings.

			Triangle begins:
  [0] 1;
  [1] 1 2;
  [2] 2 2 4;
  [3] 4 4 4 8 1 1;
  [4] 8 8 8 1 1 8 16 5 5 5 5 5 5 1 2 2;
  ...

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

Paolo Xausa, Table of n, a(n) for n = 0..3670 (rows 0..7 of the triangle, flattened).
Wikipedia, MU Puzzle.
Index entries for sequences from "Goedel, Escher, Bach".

Cf. A268643, A368946, A368947 (row lengths), A369172, A369206 (number of zeros).

MIUStepOW3[s_] := Flatten[Map[{If[StringEndsQ[#, "1"], # <> "0", Nothing], # <> #, StringReplaceList[#, "111" -> "0"], StringReplaceList[#, "00" -> ""]}&, s]];
With[{rowmax = 5}, Map[StringCount[#, "1"]&, NestList[MIUStepOW3, {"1"}, rowmax]]]

T(n,k) = A268643(A368946(n,k)).

T(n,k) = A369172(n,k) - A369206(n,k) - 1.

A369174 Irregular triangle read by rows: row n lists the number of U characters for each of the distinct derivable strings in the MIU formal system that are n characters long.

Original entry on oeis.org

0, 1, 1, 0, 2, 2, 1, 2, 1, 1, 3, 3, 2, 3, 2, 2, 3, 2, 2, 2, 0, 4, 4, 3, 4, 3, 3, 4, 3, 3, 3, 1, 4, 3, 3, 3, 1, 3, 1, 1, 1, 0, 5, 5, 4, 5, 4, 4, 5, 4, 4, 4, 2, 5, 4, 4, 4, 2, 4, 2, 2, 2, 1, 5, 4, 4, 4, 2, 4, 2, 2, 2, 1, 4, 2, 2, 2, 1, 2, 2, 1, 2, 1, 1

Offset: 2

Paolo Xausa, Jan 15 2024

See A368946 for the description of the MIU formal system and A369173 for the triangle of the corresponding derivable strings.

			Triangle begins:
  [2] 0;
  [3] 1 1 0;
  [4] 2 2 1 2 1 1;
  [5] 3 3 2 3 2 2 3 2 2 2 0;
  [6] 4 4 3 4 3 3 4 3 3 3 1 4 3 3 3 1 3 1 1 1 0;
  ...

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

Paolo Xausa, Table of n, a(n) for n = 2..10922 (rows 2..14 of the triangle, flattened).
Wikipedia, MU Puzzle.
Index entries for sequences from "Goedel, Escher, Bach".

Cf. A024495 (row lengths), A055641, A368946, A369173, A369179 (number of ones).

A369174row[n_] := n - 1 - Select[Map[Count[#, 1]&, Tuples[{0, 1}, n - 1]], !Divisible[#, 3]&]; Array[A369174row, 6, 2]

T(n,k) = A055641(A369173(n,k)).

T(n,k) = n - 1 - A369179(n,k).

A369179 Irregular triangle read by rows: row n lists the number of I characters for each of the distinct derivable strings in the MIU formal system that are n characters long.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 2, 4, 1, 1, 2, 1, 2, 2, 1, 2, 2, 2, 4, 1, 2, 2, 2, 4, 2, 4, 4, 4, 5, 1, 1, 2, 1, 2, 2, 1, 2, 2, 2, 4, 1, 2, 2, 2, 4, 2, 4, 4, 4, 5, 1, 2, 2, 2, 4, 2, 4, 4, 4, 5, 2, 4, 4, 4, 5, 4, 4, 5, 4, 5, 5

Offset: 2

Paolo Xausa, Jan 16 2024

See A368946 for the description of the MIU formal system and A369173 for the triangle of the corresponding derivable strings.

			Triangle begins:
  [2] 1;
  [3] 1 1 2;
  [4] 1 1 2 1 2 2;
  [5] 1 1 2 1 2 2 1 2 2 2 4;
  [6] 1 1 2 1 2 2 1 2 2 2 4 1 2 2 2 4 2 4 4 4 5;
  ...

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

Paolo Xausa, Table of n, a(n) for n = 2..10922 (rows 2..14 of the triangle, flattened).
Wikipedia, MU Puzzle.
Index entries for sequences from "Goedel, Escher, Bach".

Cf. A024495 (row lengths), A268643, A368946, A369173, A369174 (number of zeros).

A369179row[n_] := Select[Map[Count[#, 1]&, Tuples[{0, 1}, n - 1]], !Divisible[#, 3]&]; Array[A369179row, 6, 2]

T(n,k) = A268643(A369173(n,k)).
T(n,k) = n - 1 - A369174(n,k).
T(n,k) mod 3 > 0.

A368954 Row lengths of A368953: in the MIU formal system, number of distinct strings n steps distant from the MI string.

Original entry on oeis.org

1, 2, 3, 6, 15, 48, 232, 1544, 14959, 203333, 3919437, 105126522

Offset: 0

Paolo Xausa, Jan 10 2024

See A368946 for the description of the MIU formal system and A368953 for the variant where duplicates within a row are removed.

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

Wikipedia, MU Puzzle.
Index entries for sequences from "Goedel, Escher, Bach"

Cf. A331536, A368946, A368947, A368953, A369408.

MIUStepDW3[s_] := DeleteDuplicates[Flatten[Map[{If[StringEndsQ[#, "1"], # <> "0", Nothing], # <> #, StringReplaceList[#, {"111" -> "0","00" -> ""}]}&, s]]];
With[{rowmax = 9}, Map[Length, NestList[MIUStepDW3, {"1"}, rowmax]]]

from itertools import islice
def occurrence_swaps(w, s, t):
    out, oi = [], w.find(s)
    while oi != -1:
        out.append(w[:oi] + t + w[oi+len(s):])
        oi = w.find(s, oi+1)
    return out
def moves(w): # moves for word w in MIU system, encoded as 310
    nxt = []
    if w[-1] == '1': nxt.append(w + '0')        # Rule 1
    if w[0] == '3': nxt.append(w + w[1:])       # Rule 2
    nxt.extend(occurrence_swaps(w, '111', '0')) # Rule 3
    nxt.extend(occurrence_swaps(w, '00', ''))   # Rule 4
    return nxt
def agen(): # generator of terms
    frontier = {'31'}
    while len(frontier) > 0:
        yield len(frontier)
        reach1 = set(m for p in frontier for m in moves(p))
        frontier, reach1 = reach1, set()
print(list(islice(agen(), 10))) # Michael S. Branicky, Jan 14 2024

a(n) <= A368947(n).

a(10)-a(11) from Michael S. Branicky, Jan 14 2024

A369412 Maximum length of a "normal" proof (see comments) for strings (theorems) in the MIU formal system that are n characters long.

Original entry on oeis.org

1, 4, 13, 11, 18, 16, 25, 23, 24, 22, 26, 24, 34, 32, 33, 31, 35, 33, 34, 32, 39, 37, 49

Offset: 2

Paolo Xausa, Jan 23 2024

See A368946 for the description of the MIU formal system, A369410 for the triangle of the corresponding proof lengths and A369409 for the definition of "normal" proof.

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

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

Cf. A024495, A368946, A369173, A369409, A369410, A369413.

MIUDigitsW3[n_] := Select[Tuples[{0, 1}, n - 1], !Divisible[Count[#, 1], 3]&];
MIUProofLineCount[t_] := Module[{c = Count[t, 0], ni}, ni = Length[t] + 2*c; While[ni > 1, If[OddQ[ni], ni = (ni+3)/2; c += 4, ni/=2; c++]]; c+1];
Map[Max, Map[MIUProofLineCount, Array[MIUDigitsW3, 15, 2], {2}]]

a(n) = max_{k=1..A024495(n)} A369410(n,k).

A369413 Maximum number of symbols of a "normal" proof (see comments) for strings (theorems) in the MIU formal system that are n characters long.

Original entry on oeis.org

2, 13, 94, 75, 165, 139, 308, 269, 348, 299, 482, 423, 647, 581, 780, 701, 893, 807, 1064, 965, 1281, 1175, 1654

Offset: 2

Paolo Xausa, Jan 23 2024

See A368946 for the description of the MIU formal system, A369411 for the triangle of the corresponding symbol lengths and A369409 for the definition of "normal" proof.

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

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

Cf. A024495, A368946, A369173, A369409, A369411, A369412.

MIUDigitsW3[n_] := Select[Tuples[{0, 1}, n - 1], !Divisible[Count[#, 1], 3]&];
MIUProofSymbolCount[t_] := Module[{c = Length[t], nu = Count[t,0], ni}, ni = 2*nu+c; c += nu(nu+c+2); While[ni > 1, If[OddQ[ni], c += (7*ni+3)/2 + 13; ni = (ni+3)/2, c += ni/2 + 1; ni/=2]]; c+1];
Map[Max, Map[MIUProofSymbolCount, Array[MIUDigitsW3, 15, 2], {2}]]

a(n) = max_{k=1..A024495(n)} A369411(n,k).

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

Original entry on oeis.org

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

Paolo Xausa, Jan 24 2024

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.

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

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

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

Cf. A368946, A369409.
Cf. A000079 (first column and, for n >= 2, row lengths), A062709 (right border, for n >= 2).
Permutation of A001651.

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

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

A369148 In the MIU formal system, total number (including duplicates) of strings up to n steps distant from the MI string.

Original entry on oeis.org

1, 3, 6, 12, 28, 88, 444, 3671, 47981, 976631, 29554002, 1326494644

Offset: 0

Paolo Xausa, Jan 14 2024

See A368946 for the description of the MIU formal system.

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

Wikipedia, MU Puzzle.
Index entries for sequences from "Goedel, Escher, Bach".

Cf. A331536 (without duplicates), A368946, A369173 (all MIU strings).

Partial sums of A368947.

MIUStepW3[s_] := Flatten[Map[{If[StringEndsQ[#, "1"], # <> "0", Nothing], # <> #, StringReplaceList[#, {"111" -> "0", "00" -> ""}]}&, s]];
With[{rowmax = 9}, Accumulate[Map[Length, NestList[MIUStepW3, {"1"}, rowmax]]]]

a(n) >= A331536(n+1).

cp's OEIS Frontend

A369172 Irregular triangle read by rows: row n lists the lengths of the strings of the MIU formal system at the n-th level of the tree generated by recursively applying the system rules, starting from the MI string.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A369206 Irregular triangle read by rows: row n lists the number of U characters for each of the strings of the MIU formal system at the n-th level of the tree generated by recursively applying the system rules, starting from the MI string.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A369207 Irregular triangle read by rows: row n lists the number of I characters for each of the strings of the MIU formal system at the n-th level of the tree generated by recursively applying the system rules, starting from the MI string.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A369174 Irregular triangle read by rows: row n lists the number of U characters for each of the distinct derivable strings in the MIU formal system that are n characters long.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A369179 Irregular triangle read by rows: row n lists the number of I characters for each of the distinct derivable strings in the MIU formal system that are n characters long.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A368954 Row lengths of A368953: in the MIU formal system, number of distinct strings n steps distant from the MI string.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A369412 Maximum length of a "normal" proof (see comments) for strings (theorems) in the MIU formal system that are n characters long.

Views

Author

Keywords

Comments

References