cp's OEIS Frontend

Each entry of this sequence represents the same small equivalence class (sec) of Boolean functions as the corresponding entry of A190939. While A190939 represents each sec by the unique odd number among the numeric values of its functions, this sequence represents each sec by the smallest among these numbers (as an entry of A227722).

All big equivalence classes (bec) of Boolean functions are also small equivalence classes. So all entries in the sequence of sona-becs (A227960) are also in this sequence of sona-secs.

This sequence takes its order from A190939, so it is not monotonic. Thus it is not a subsequence of A227722, and does not contain A227960 as a subsequence.

First entries: 1, 3, 5, 6, 15, 17, 18, 51, 20, 85, 105, 24, 102, 90, 60, 255.

First entries in numerical order: 1, 3, 5, 6, 15, 17, 18, 20, 24, 51, 60, 85, 90, 102, 105, 255.

Each subgroup {0,a,b,...} of nimber addition can be assigned an integer 1+2^a+2^b+...

These integers ordered by size give this sequence.

Without nimbers the sequence may be defined as follows:

The powerset af a set {0,...,n-1} with the symmetric difference as group operation forms the elementary abelian group (Z_2)^n.

The elements of the group can be numbered lexicographically from 0 to 2^n-1, with 0 representing the neutral element:

{}-->0 , {0}-->2^0=1 , {1}-->2^1=2 , {0,1}-->2^0+2^1=3 , ... , {0,...,n-1}-->2^n-1

So the subgroups of (Z_2)^n can be represented by subsets of {0,...,2^n-1}.

So each subgroup {0,a,b,...} of (Z_2)^n can be assigned an integer 1+2^a+2^b+...

For each (Z_2)^n there is a finite sequence of these numbers ordered by size, and it is the beginning of the finite sequence for (Z_2)^(n+1).

This leads to the infinite sequence:

* 1, (1 until here for (Z_2)^0)

* 3, (2 until here for (Z_2)^1)

* 5, 9, 15, (5 until here for (Z_2)^2)

* 17, 33, 51, 65, 85, 105, 129, 153, 165, 195, 255, (16 until here for (Z_2)^3)

* 257, 513, 771, 1025, 1285, 1545, 2049, 2313, 2565, 3075, 3855, 4097, 4369, 4641, 5185, 6273, 8193, 8481, 8721, 9345, 10305, 12291, 13107, 15555, 16385, 16705, 17025, 17425, 18465, 20485, 21845, 23205, 24585, 26265, 26985, 32769, 33153, 33345, 33825, 34833, 36873, 38505, 39321, 40965, 42405, 43605, 49155, 50115, 52275, 61455, 65535, (67 until here for (Z_2)^4)

* 65537, ...

The number of subgroups of (Z_2)^n is 1, 2, 5, 16, 67, 374, 2825, ... (A006116)

Comment from Tilman Piesk, Aug 27 2013: (Start)

Boolean functions correspond to integers, and belong to small equivalence classes (sec). So a sec can be seen as an infinite set of integers (represented in A227722 by the smallest one). Some secs contain only one odd integer. These unique odd integers, ordered by size, are shown in this sequence. (While the smallest integers from these secs are shown in A227963.)

(End)

Two Boolean functions belong to the same big equivalence class (bec) when they can be expressed by each other by negating and permuting arguments. E.g., when f(~p,r,q) = g(p,q,r), then f and g belong to the same bec. Geometrically this means that the functions correspond to hypercubes with binarily colored vertices that are equivalent up to rotation and reflection.

Boolean functions correspond to integers, so each bec can be denoted by the smallest integer corresponding to one of its functions. There are A000616(n) big equivalence classes of n-ary Boolean functions. Ordered by size they form the finite sequence A_n. It is the beginning of A_(n+1), which leads to this infinite sequence A.

Left diagonal (k=0) has only 2s. Two functions (contradiction and tautology) are always alone in their respective sec, regardless of arity.

Second diagonal (k=1) is 2^n-1 (A000225). These are the n-ary linear Boolean functions. Each sec contains a row of a binary Walsh matrix and its complement.

Right diagonal (k=n) is A051502, the numbers of small equivalence classes of n-ary functions, that contain the highest possible number of 2^n functions.