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.
LINKS
Tilman Piesk, Rows 0..4 of the triangle, flattened
Tilman Piesk, Zhegalkin matrix (Wikiversity)
FORMULA
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 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
Tilman Piesk, Nov 01 2022
STATUS
approved