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