login
A207328
Nonlinearities of 4-variable Boolean functions ordered lexicographically.
1
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 3, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 3, 2, 3, 3, 4, 3, 4, 4, 3, 3, 4, 4, 3, 4, 3, 3, 2, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 3, 2, 3, 3, 4, 3, 4, 4
OFFSET
0,4
COMMENTS
Nonlinearity of a Boolean function is its minimum Hamming distance to the elements of the set of affine Boolean functions.
In this sequence, n represents the truth table of a Boolean function.
There are 2^2^4 = 65536 terms in this list, i.e. the number of 4-variable Boolean functions.
This is also the list of first 2^2^4 terms of r-th order nonlinearity values of (r+3)-variables Boolean functions ordered lexicographically.
LINKS
Erdener Uyan, Table of n, a(n) for n = 0..65535 (complete sequence)
EXAMPLE
n in GF(2^4)
a(1)=a((0000000000000001)_2)=1;
a(5)=a((0000000000000101)_2)=2;
a(15)=a((0000000000001111)_2)=0;
This can also be written as a triangle, though contains outliers in later iterations:
0,
1,
1,2,
1,2,2,3,
1,2,2,3,2,3,3,4,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,3,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,3,2,3,3,4,3,4,4,3,3,4,4,3,4,3,3,2...
PROG
(R w/ boolfun package)
for(n in 0:2^(2^4)-1){
f<- BooleanFunction(toBin(n, 2^4))
a[n]<-nl(f)
}
CROSSREFS
Cf. A207676 (that of 3-variable Boolean functions).
Cf. A000120, A000069, A001969, A007088 (sequences dealing with binary expansion of n).
Cf. A051253, A053168, A053189 (sequences that relate nonlinearity with Hamming weight for a special class of Boolean functions).
Sequence in context: A105111 A105112 A105113 * A105056 A105061 A105164
KEYWORD
nonn
AUTHOR
Erdener Uyan, Feb 28 2012
STATUS
approved