A207328 Nonlinearities of 4-variable Boolean functions ordered lexicographically.

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

Adjacent sequences: A207325 A207326 A207327 * A207329 A207330 A207331

Keyword

nonn

Author

Erdener Uyan, Feb 28 2012

Status

approved