login
A358167
Irregular triangle read by rows: T(n, k) = k-th fixed point in Zhegalkin permutation n (row n of A197819).
1
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,4
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.
LINKS
Tilman Piesk, row 3 and row 4 as binary matrices, row 3 as part of the permutation
Tilman Piesk, Zhegalkin matrix (Wikiversity)
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.
EXAMPLE
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
PROG
(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
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Tilman Piesk, Nov 01 2022
STATUS
approved