cp's OEIS Frontend

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

%I A358167 #49 Dec 25 2022 14:06:57
%S A358167 0,1,0,2,0,6,8,14,0,30,40,54,72,86,96,126,128,158,168,182,200,214,224,
%T A358167 254,0,510,680,854,1224,1334,1632,1950,2176,2430,2600,3030,3144,3510,
%U A358167 3808,3870,4320,4382,4680,5046,5160
%N A358167 Irregular triangle read by rows: T(n, k) = k-th fixed point in Zhegalkin permutation n (row n of A197819).
%C A358167 Let R = A197819(n, ...) and F = a(n, ...). Then F are the fixed points of R.
%C A358167 But there is a second relationship between F and R:
%C A358167   Let X(i) = R(i) XOR i. Then X(i) is an element of F.
%C A358167   Let I_k = {i | X(i) = F(k)}. Let Q = A197819(n-1, ...).
%C A358167   Then I_k = {Q(k) XOR f | f in F}.
%C A358167 Row lengths are 2, 2, 4, 16, 256, 65536, ..., i.e., A001146(n-1) for n > 0.
%C A358167 Row sums are 1, 2, 28, 2032, 8388352, ..., i.e., A147537(A000225) for n > 0.
%H A358167 Tilman Piesk, <a href="/A358167/b358167.txt">Rows 0..4 of the triangle, flattened</a>
%H A358167 Tilman Piesk, <a href="https://commons.wikimedia.org/wiki/File:Fixed_points_in_Zhegalkin_permutation_3.svg">row 3</a> and <a href="https://commons.wikimedia.org/wiki/File:Fixed_points_in_Zhegalkin_permutation_4.svg">row 4</a> as binary matrices, <a href="https://commons.wikimedia.org/wiki/File:Zhegalkin_256;_fixed.svg">row 3 as part of the permutation</a>
%H A358167 Tilman Piesk, <a href="https://en.wikiversity.org/wiki/Zhegalkin_matrix#Fixed_points">Zhegalkin matrix</a> (Wikiversity)
%F A358167 For n>0: T(n, k) = [A197819(n-1, k) XOR k] + [2^(2^(n-1)) * k].
%F A358167   (On this page "XOR" always is the bitwise exclusive or.)
%F A358167 For n>0: T(n, A058891(n)) = A058891(n+1) is the unique power of 2 in row n.
%e A358167 Triangle begins:
%e A358167      k  0    1    2   3    4   5   6    7    8    9   10   11   12   13   14   15
%e A358167   n
%e A358167   0     0,   1
%e A358167   1     0,   2
%e A358167   2     0,   6,   8, 14
%e A358167   3     0,  30,  40, 54,  72, 86, 96, 126, 128, 158, 168, 182, 200, 214, 224, 254
%e A358167   4     0, 510, 680...
%e A358167 A197819(3, 168) = a(3, 10) = 168.
%e A358167 How to calculate the term for n=3, k=10:
%e A358167   p = A197819(n-1, k) = A197819(2, 10) = 2
%e A358167   p XOR k = 2 XOR 10 = 8
%e A358167   shifted_k = 2^(2^(n-1)) * k = 2^(2^2) * 10 = 160
%e A358167   (p XOR k) + shifted_k = 8 + 160 = 168
%e A358167 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.
%e A358167   (With x0 = 01010101, x1 = 00110011, x2 = 00001111.)
%e A358167 Example for the second relationship with A197819, as described in COMMENTS:
%e A358167   Let R = A197819(3, 0..255), F = a(3, 0..15), Q = A197819(2, 0..15).
%e A358167   I_3 = {i | R(i) XOR i = F(3)}
%e A358167       = {Q(3) XOR f | f in F} = {5 XOR f | f in F}
%e A358167       = {5, 27, 45, 51, 77, 83, 101, 123, 133, 155, 173, 179, 205, 211, 229, 251}
%e A358167   R(5) XOR 5  =  R(27) XOR 27  =  R(45) XOR 45  =  R(51) XOR 51  =  ...  =  F(3)
%e A358167    51  XOR 5  =    45  XOR 27  =    27  XOR 45  =     5  XOR 51  =  ...  =   54
%o A358167 (Python)
%o A358167 def a(n, k):
%o A358167     if n == 0:
%o A358167         assert k < 2
%o A358167         return k
%o A358167     else:
%o A358167         row_length = 1 << (1 << (n-1))  # 2 ** 2 ** (n-1)
%o A358167         assert k < row_length
%o A358167     p = a197819(n-1, k)
%o A358167     p_xor_k = p ^ k
%o A358167     shifted_k = row_length * k
%o A358167     return p_xor_k + shifted_k
%Y A358167 Cf. A197819, A001146, A147537, A000225, A058891.
%K A358167 nonn,tabf
%O A358167 0,4
%A A358167 _Tilman Piesk_, Nov 01 2022