|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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...
How to calculate the term for n=3, k=10:
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:
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
|
|
|
STATUS
|
approved
|
|
|
|