A379047 Rectangular array read by descending antidiagonals: the Type 2 runlength index array of A000002 (the Kolakoski sequence); see Comments.

1, 3, 2, 5, 4, 8, 6, 11, 28, 13, 7, 16, 35, 80, 53, 9, 18, 48, 121, 217, 112, 10, 22, 62, 135, 449, 332, 305, 12, 26, 67, 175, 472, 1478, 1451, 296, 14, 31, 89, 203, 513, 1974, 1947, 1358, 1331, 15, 38, 94, 244, 812, 2101, 2683, 1920, 1827, 964, 17, 40, 107

Offset: 1

Author

Clark Kimberling, Dec 16 2024

Keywords

• nonn
• tabl

Comments

We begin with a definition of Type 2 runlength array, V(s), of any sequence s for which all the runs referred to have finite length:

Suppose s is a sequence (finite or infinite), and define rows of V(s) as follows:

(row 0) = s

(row 1) = sequence of last terms of runs in (row 0); c(1) = complement of (row 1) in (row 0)

For n>=2,

(row n) = sequence of last terms of runs in c(n-1); c(n) = complement of (row n) in (row n-1),

where the process stops if and when c(n) is empty for some n.

***

The corresponding Type 2 runlength index array, The runlength index array, VI(s) is now contructed from V(s) in two steps:

(1) Let V*(s) be the array obtaining by repeating the construction of V(s) using (n,s(n)) in place of s(n).

(2) Then VI(s) results by retaining only n in V*.

Thus, loosely speaking, (row n) of VI(s) shows the indices in s of the numbers in (row n) of V(s).

The array VI(s) includes every positive integer exactly once.

***

Examples: (1) if s is monotonic, then VI(s) has just one row, the positive integers, A000027.

(2) if s = A010060 (Thue-Morse sequence), then VI(s) has exactly two rows: A003159 and A036554. The type 1 runlength index array of s also has exactly two rows: A285385 and A072989.

Examples

			Corner:
      1     3    5      6     7     9    10    12    14    15     17     19
      2     4    11    16    18    22    26    31    38    40     44     51
      8    28    35    48    62    67    89    94   107   130    150    157
     13    80   121   135   175   203   244   359   417   458    499    540
     53   217   449   472   513   812   879  1069  1272  1511   1725   1786
    112   332  1478  1974  2101  2423  2710  3282  3638  3715   3950   4145
    305  1451  1947  2683  2883  3605  3706  3827  4528  4749   4963   5076
    296  1358  1920  2590  2850  3542  5745  6400  7103  7567   7796   8346
   1331  1827  2491  2805  3437  5652  6373  7769  8265  9315  11508  11738
Using s = A000002 as an example, we have for V*(s):
(row 1) = ((1,1), (3,2), (5,1), (6,2), (7,1), (9,2), (10,1), (12,2), (14,1),...)
c(1) = ((2,2), (4,1), (8,2), (11,2), (13,1), (16,1), (18,2), (22,1), (26,2), ...)
(row 2) = ((2,2), (4,1), (11,2), (16,1), (18,2), (22,1), (26,2), (31,1), (35,2), ...)
c(2) = (8,2), (13,1), (28,1), ...)
(row 3) = (8,2), (28,1),
so that VI(s) has
(row 1) = (1,3,5,6,7,9,10,12, ...)
(row 2) = (2,4,11,16,18,22,26, ...)
(row 3) = (8,28,35,48,62,67,...)
		

Crossrefs

Cf. A000002, A379046 (Type 1 array).

Programs

Mathematica

r[seq_] := seq[[Flatten[Position[Append[Differences[seq[[All, 1]]], 1], _?(# != 0 &)]], 2]];  (* Type 1 *)
row[0] = Prepend[Nest[Flatten[Partition[#, 2] /. {{2, 2} -> {2, 2, 1, 1}, {2, 1} -> {2, 2, 1}, {1, 2} -> {2, 1, 1}, {1, 1} -> {2, 1}}] &, {2, 2}, 24], 1]; (* A000002 *)
row[0] = Transpose[{#, Range[Length[#]]}] &[row[0]];
k = 0; Quiet[While[Head[row[k]] === List, row[k + 1] = row[0][[r[
     SortBy[Apply[Complement, Map[row[#] &, Range[0, k]]], #[[2]] &]]]]; k++]];
m = Map[Map[#[[2]] &, row[#]] &, Range[k - 1]];
p[n_] := Take[m[[n]], 12]
t = Table[p[n], {n, 1, 12}]
Grid[t]  (* array *)
w[n_, k_] := t[[n]][[k]];
Table[w[n - k + 1, k], {n, 12}, {k, n, 1, -1}] // Flatten  (* sequence *)
(* Peter J. C. Moses, Dec 04 2024 *)