Boolean functions (original question)

Marc LeBrun mlb at
Thu Jan 4 15:54:41 CET 2001

 >=Russ Cox
 > It is tempting to guess that a(5) = 33 and
 > a(6) = 63.

It'll be interesting to see what it turns out to be!  Why that +/- 1 I 
wonder?  I hope someone's even now writing the computer program to count 
them (cleverly optimized as Antti Karttunen suggested).

 > Perhaps someone else can see an argument why
 > chains of XOR should be the hardest function?

Maybe not a rigorous one.

But as I mentioned before it's certainly a candidate, since every argument 
contributes information to the value.

If XOR[n] is one of the hardest then so are all the 2^(n-1)-1 images of it 
having arguments swapped with their complements (eg EQV when 
n=2).  Swapping basically just transposes the "hyper truth table" along one 
of its axes.

This family also exhausts the set of all the all-argument dependent 
functions, since any other rearrangement of the outputs will cause the 
values to be the same for some arguments.

So maybe that does prove it?

Even so, in order to determine the sequence values it remains to find a 
construction giving provably minimal-operation expressions for XOR[n].

More information about the SeqFan mailing list