A261692 -id:A261692 - cp's OEIS frontend

A261693 Irregular triangle read by rows in which row n lists the positive odd numbers in decreasing order starting with 2^n - 1. T(0, 1) = 0 and T(n, k) for n >= 1, 1 <= k <= 2^(n-1).

0, 1, 3, 1, 7, 5, 3, 1, 15, 13, 11, 9, 7, 5, 3, 1, 31, 29, 27, 25, 23, 21, 19, 17, 15, 13, 11, 9, 7, 5, 3, 1, 63, 61, 59, 57, 55, 53, 51, 49, 47, 45, 43, 41, 39, 37, 35, 33, 31, 29, 27, 25, 23, 21, 19, 17, 15, 13, 11, 9, 7, 5, 3, 1, 127, 125, 123, 121, 119, 117, 115, 113, 111, 109, 107, 105, 103, 101, 99, 97, 95, 93

Offset: 0

Omar E. Pol, Sep 25 2015

Also the first differences of A261692.
Number of cells turned ON at n-th stage of the cellular automaton of A261692.
This irregular triangle A (instead of T) appears also in the linearization of the following product of Chebyshev T polynomials (A053120): PrT(n) := Product_{j=1..n} T(2^j, x)  = (1/2^(n-1))*Sum_{k=1..2^(n-1)} T(2*A(n, k), x), for n >= 1. Proof via 2*T(n, x)*T(m, x) = T(n+m, x) + T(|n-m|, x). - Wolfdieter Lang, Oct 26 2019

			With the terms written as an irregular triangle T in which row lengths are the terms of A011782 the sequence begins:
0;
1;
3, 1;
7, 5, 3, 1;
15, 13, 11, 9, 7, 5, 3, 1;
31, 29, 27, 25, 23, 21, 19, 17, 15, 13, 11, 9, 7, 5, 3, 1;
...
-------------------------------------------------------------------------------
From _Wolfdieter Lang_, Oct 26 2019: (Start)
Chebyshev T(2^j)-products (the argument x is here omitted):
n = 1: T(2) = (2^0)*T(2*1),
n = 2: T(2)*T(4) = (1/2)*(T(2*3) + T(2*1)) = (T(6) + T(2))/2,
n = 3: T(2)*T(4)*T(8) =  (1/2^2)*(T(2*7) + T(2*5) + T(2*3) + T(2*1))
       = (T(14) + T(10) + T(6) + T(2))/4.
... (End)

Cf. A036563, A005408, A011782, A080079, A099375, A147582, A262617, A261692, A262621.

Column 1 is A000225. Row sums give A000302, n >= 1.

A261693 := n -> Bits:-Nor(2*n, 2*n):
seq(A261693(n), n=0..81); # Peter Luschny, Sep 23 2019

Table[Reverse[2 Range[2^(n - 1)] - 1], {n, 0, 7}] /. {} -> 0 // Flatten (* Michael De Vlieger, Oct 05 2015 *)

tabf(nn) = {for (n=0, nn, print1(n, ":"); for (k=1, 2^(n-2), print1(2^(n-1) - 2*k + 1, ", ");); print(););} \\ Michel Marcus, Oct 27 2015

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

As a sequence: a(n) = A262621(n)/4, n >= 1, and a(0) = 0.

Corrections by Wolfdieter Lang, Nov 15 2019

A262620 Number of "ON" cells at n-th stage in simple 2-dimensional cellular automaton on the square grid (see Comments lines for definition).

Original entry on oeis.org

1, 5, 17, 21, 49, 69, 81, 85, 145, 197, 241, 277, 305, 325, 337, 341, 465, 581, 689, 789, 881, 965, 1041, 1109, 1169, 1221, 1265, 1301, 1329, 1349, 1361, 1365, 1617, 1861, 2097, 2325, 2545, 2757, 2961, 3157, 3345, 3525, 3697, 3861, 4017, 4165, 4305, 4437, 4561, 4677, 4785, 4885, 4977, 5061, 5137, 5205, 5265, 5317, 5361, 5397

Offset: 0

Omar E. Pol, Oct 16 2015

On the infinite square grid consider four 90-degree wedges forming a "X" with the vertex located at the center of a cell.
At stage 0 we start with an ON cell in the vertex of the wedges, so a(0) = 1.
In order to construct the structure we use the following rules for the South wedge:
- The cells turned ON remain ON forever.
- At stage 1 we turn ON the nearest cell to the initial ON cell.
- If n is a power of 2, at stage n we turn "ON" 2*n - 1 connected cells in the n-th row of the wedge.
- Otherwise, if n is not a power of 2, at stage n we turn "ON" k - 2 connected cells in the n-th row of the wedge, where k is the number of ON cells in row n - 1.
- The "ON" cells of row n must be centered respect to the "ON" cells of row n - 1.
The structures in the other three wedges are copies of the structure in the South wedge but they grow in direction East, North and West.
Note that in every wedge the structure seems to grow into the holes of a virtual structure similar to the Sierpiński's triangle but using square cells.
A262621 gives the number of cells turned "ON" at n-th stage.
This is analog of A256266, but here we are working on the square grid and we have four wedges, not six wedges.

			Illustration of the structure after 15 generations:
.
.                                   O
.                                 O O O
.                               O O O O O
.                             O O O O O O O
.                           O O O O O O O O O
.                         O O O O O O O O O O O
.                       O O O O O O O O O O O O O
.                     O O O O O O O O O O O O O O O
.                   O               O               O
.                 O O             O O O             O O
.               O O O           O O O O O           O O O
.             O O O O         O O O O O O O         O O O O
.           O O O O O       O       O       O       O O O O O
.         O O O O O O     O O     O O O     O O     O O O O O O
.       O O O O O O O   O O O   O   O   O   O O O   O O O O O O O
.     O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O
.       O O O O O O O   O O O   O   O   O   O O O   O O O O O O O
.         O O O O O O     O O     O O O     O O     O O O O O O
.           O O O O O       O       O       O       O O O O O
.             O O O O         O O O O O O O         O O O O
.               O O O           O O O O O           O O O
.                 O O             O O O             O O
.                   O               O               O
.                     O O O O O O O O O O O O O O O
.                       O O O O O O O O O O O O O
.                         O O O O O O O O O O O
.                           O O O O O O O O O
.                             O O O O O O O
.                               O O O O O
.                                 O O O
.                                   O
.
There are 341 ON cells in the structure, so a(15) = 341.
Note that every circle in the structure should be replaced with a square cell.

Cf. A147562, A160720, A256266, A261692, A261693, A262621.

a(n) = 1 + 4*A261692(n).

A369802 Inversion count of the Eytzinger array layout of n elements.

Original entry on oeis.org

0, 0, 1, 1, 4, 6, 7, 7, 14, 20, 25, 29, 32, 34, 35, 35, 50, 64, 77, 89, 100, 110, 119, 127, 134, 140, 145, 149, 152, 154, 155, 155, 186, 216, 245, 273, 300, 326, 351, 375, 398, 420, 441, 461, 480, 498, 515, 531, 546, 560, 573, 585, 596, 606, 615, 623, 630

Offset: 0

Darío Clavijo, Feb 01 2024

nonn

The Eytzinger array layout (A375825) arranges elements so that a binary search can be performed starting at element k=1 and at a given k step to 2*k or 2*k+1 according as the target is smaller or larger than the element at k.

This layout is a permutation of the elements and its inversion count (number of swaps needed to sort by the bubble sort algorithm) is a measure of how much it differs from an ordinary sorted array.

			For n=5, the Eytzinger array layout is {4, 2, 5, 1, 3} and it contains a(5) = 6 element pairs which are not in ascending order (out of 10 element pairs altogether).

Sergey Slotin, Eytzinger binary search

Cf. A006095, A261692, A375825.

from sympy.combinatorics.permutations import Permutation
def a(n):
  def eytzinger(t, k=1, i=0):
    if (k < len(t)):
      i = eytzinger(t, k * 2, i)
      t[k] = i
      i += 1
      i = eytzinger(t, k * 2 + 1, i)
    return i
  t = [0] * (n+1)
  eytzinger(t)
  return Permutation(t[1:]).inversions()
print([a(n) for n in range(0, 58)])

a(2^n-1) = A006095(n).

Conjecture: a(n) = (A261692(n)-n)/2.

cp's OEIS Frontend

A261693 Irregular triangle read by rows in which row n lists the positive odd numbers in decreasing order starting with 2^n - 1. T(0, 1) = 0 and T(n, k) for n >= 1, 1 <= k <= 2^(n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A262620 Number of "ON" cells at n-th stage in simple 2-dimensional cellular automaton on the square grid (see Comments lines for definition).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A369802 Inversion count of the Eytzinger array layout of n elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula