A358167 Irregular triangle read by rows: T(n, k) = k-th fixed point in Zhegalkin permutation n (row n of A197819).

0, 1, 0, 2, 0, 6, 8, 14, 0, 30, 40, 54, 72, 86, 96, 126, 128, 158, 168, 182, 200, 214, 224, 254, 0, 510, 680, 854, 1224, 1334, 1632, 1950, 2176, 2430, 2600, 3030, 3144, 3510, 3808, 3870, 4320, 4382, 4680, 5046, 5160

Offset: 0

Author

Tilman Piesk, Nov 01 2022

Keywords

• nonn
• tabf

Comments

Let R = A197819(n, ...) and F = a(n, ...). Then F are the fixed points of R.

But there is a second relationship between F and R:

Let X(i) = R(i) XOR i. Then X(i) is an element of F.

Let I_k = {i | X(i) = F(k)}. Let Q = A197819(n-1, ...).

Then I_k = {Q(k) XOR f | f in F}.

Row lengths are 2, 2, 4, 16, 256, 65536, ..., i.e., A001146(n-1) for n > 0.

Row sums are 1, 2, 28, 2032, 8388352, ..., i.e., A147537(A000225) for n > 0.

Examples

			Triangle begins:
     k  0    1    2   3    4   5   6    7    8    9   10   11   12   13   14   15
  n
  0     0,   1
  1     0,   2
  2     0,   6,   8, 14
  3     0,  30,  40, 54,  72, 86, 96, 126, 128, 158, 168, 182, 200, 214, 224, 254
  4     0, 510, 680...
A197819(3, 168) = a(3, 10) = 168.
How to calculate the term for n=3, k=10:
  p = A197819(n-1, k) = A197819(2, 10) = 2
  p XOR k = 2 XOR 10 = 8
  shifted_k = 2^(2^(n-1)) * k = 2^(2^2) * 10 = 160
  (p XOR k) + shifted_k = 8 + 160 = 168
168 in little-endian binary is 00010101. The corresponding algebraic normal form is XOR(AND(x0, x1), AND(x0, x2), AND(x0, x1, x2)). (Its ANDs correspond to the 3 binary 1s.) The truth table of this Boolean function is again 00010101.
  (With x0 = 01010101, x1 = 00110011, x2 = 00001111.)
Example for the second relationship with A197819, as described in COMMENTS:
  Let R = A197819(3, 0..255), F = a(3, 0..15), Q = A197819(2, 0..15).
  I_3 = {i | R(i) XOR i = F(3)}
      = {Q(3) XOR f | f in F} = {5 XOR f | f in F}
      = {5, 27, 45, 51, 77, 83, 101, 123, 133, 155, 173, 179, 205, 211, 229, 251}
  R(5) XOR 5  =  R(27) XOR 27  =  R(45) XOR 45  =  R(51) XOR 51  =  ...  =  F(3)
   51  XOR 5  =    45  XOR 27  =    27  XOR 45  =     5  XOR 51  =  ...  =   54
		

Links

• Tilman Piesk, Rows 0..4 of the triangle, flattened
• Tilman Piesk, row 3 and row 4 as binary matrices, row 3 as part of the permutation
• Tilman Piesk, Zhegalkin matrix (Wikiversity)

Crossrefs

Cf. A197819, A001146, A147537, A000225, A058891.

Programs

Python

def a(n, k):
    if n == 0:
        assert k < 2
        return k
    else:
        row_length = 1 << (1 << (n-1))  # 2 ** 2 ** (n-1)
        assert k < row_length
    p = a197819(n-1, k)
    p_xor_k = p ^ k
    shifted_k = row_length * k
    return p_xor_k + shifted_k

Formula

For n>0: T(n, k) = [A197819(n-1, k) XOR k] + [2^(2^(n-1)) * k].

(On this page "XOR" always is the bitwise exclusive or.)

For n>0: T(n, A058891(n)) = A058891(n+1) is the unique power of 2 in row n.