Notes from Russ Cox <rsc(AT)plan9.bell-labs.com> on the calculation
of A056287.

Date: Thu, 4 Jan 2001 13:58:23 -0500

I don't have any good ideas about a(5), but
computing a(4) only needs to consider 64k functions, 
which you can represent as 16-bit numbers.
Backing off to a(3), the four functions a, b, c
are 00001111, 00110011, 01010101.  Then the
negations, ands, and ors are all the corresponding
bitwise functions.

Let m = 2^2^n.

It's basically an a(n)*m^2 search
to figure out the best way to build each function.
It could almost be breadth first search but you
don't know how to combine things.  Instead, the
search algorithm is almost dynamic programming:

	addtoqueue(singular functions a, b, c, ~a, ~b, ~c).

	while(something's in the queue)
		i = head of queue
		for each computable function j
			if using i and j is a cheaper way to compute
			i&j, write down the new cost for i*j, and 
			add i&j to the queue if not already there.

			similarly for i|j.

	walk through list of costs of functions,
	find a hard one, and print it.

The attached C program does this.  It prints
the size of the queue every 4k elements processed.
Once it finishes, it prints a hardest function.
Then it prompts for functions in binary so you
can find out if your own are hardest functions.

g% a.out 4
8.62616.60353.58380.....
0001011001101000 ((d*!c*b*!a+(!d+!b)*(c+a))*(d+b)+c*a)*(!d*!b+!a+!c) requires 15 ops
> 0110100110010110
0110100110010110 (d+!c)*(!d+c)*(b+a)*(!b+!a)+(d*!c+!d*c)*(b+!a)*(!b+a) requires 15 ops
>

It takes half an hour on my 233MHz Pentium II to
handle n=4.

Russ

--- cut here ---

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

enum {
	MAXN = 4,
	MAXM = 1<<(1<<MAXN),
	MAXQUEUE = MAXM+1,
};

#define MAXN 4

typedef unsigned char uchar;
typedef unsigned long ulong;

uchar cost[MAXM];	/* no. of literals used = 1+no. of operations */
ulong parents[MAXM];	/* two 16-bit parent numbers (MAXN <= 4) */
#define P(a,b) (((a)<<16)|(b))

#define NQUEUE 
ulong queue[MAXQUEUE];	/* queue of functions to examine */
ulong rp, wp;		/* queue read, write pointer */
uchar inqueue[MAXM];	/* inq[f] = is f in the queue? */

int n;
ulong m;		/* 1<<(1<<n) */

int debug;

/* write function in binary */
char*
fmtbool(char *buf, int x)
{
	int i;

	for(i=0; i<(1<<n); i++)
		buf[i] = (x&(1<<((1<<n)-1-i))) ? '1' : '0';
	buf[i] = '\0';
	return buf;
}

/* write function expression using parent histories */
char*
fmtexpr(char *buf, long f, int isplus)
{
	char buf0[80], buf1[80];
	int c;
	ulong a, b;
	char *l, *r;

	a = (parents[f]>>16)&0xFFFF;
	b = parents[f]&0xFFFF;
	if(a==0)
		sprintf(buf, "%c", "abcd"[b-1]);
	else if(b==0)
		sprintf(buf, "!%c", "abcd"[a-1]);
	else{
		if((a&b)==f)
			c = '*';
		else if((a|b)==f)
			c = '+';
		else{
			c = 0;
			assert(0);
		}

		if(isplus || c=='*'){
			l = "";
			r = "";
		}else{
			l = "(";
			r = ")";
		}
		sprintf(buf, "%s%s%c%s%s", l, fmtexpr(buf0, a, c=='+'),
			c, fmtexpr(buf1, b, c=='+'), r);
	}
	return buf;
}

void
addqueue(ulong f)
{
	if(inqueue[f])
		return;

	inqueue[f] = 1;
	queue[wp] = f;
	if(++wp == MAXQUEUE)
		wp = 0;
	assert(wp != rp);
}

int
emptyqueue(void)
{
	return wp == rp;
}

ulong
fromqueue(void)
{
	ulong f;

	assert(wp != rp);

	f = queue[rp];
	if(++rp == MAXQUEUE)
		rp = 0;
	inqueue[f] = 0;
	return f;
}

/* boolean for literal a, b, c, d, etc. */
ulong
literal(int i)
{
	int f, j;

	f = 0;
	for(j=0; j<(1<<n); j++)
		f |= (j & (1<<i)) ? (1<<j) : 0;
	return f;
}

/* negate */
ulong
neg(ulong f)
{
	return (m-1)^f;
}

/* note that we can build f out of a and b */
void
build(ulong f, ulong a, ulong b)
{
	if(cost[f]!=0 && cost[f] < cost[a]+cost[b])
		return;

	cost[f] = cost[a]+cost[b];
	parents[f] = P(a,b);

if(debug){
char buf0[80], buf1[80], buf2[80];
printf("%s(%d) from %s(%d), %s(%d)\n",
	fmtexpr(buf0, f, 1), cost[f],
	fmtexpr(buf1, a, 1), cost[a],
	fmtexpr(buf2, b, 1), cost[b]);
}

	addqueue(f);
}

int
main(int argc, char **argv)
{
	char buf0[80], buf1[80];
	ulong f, i, j, worstf, x;

	/* bad argument processing */
	while(argc > 1 && argv[1][0]=='-'){
		if(strcmp(argv[1], "-D")==0)
			debug = 1;
		else{
		Usage:
			fprintf(stderr, "usage: h [-D] n\n");
			exit(1);
		}
		argc--;
		argv++;
	}

	if(argc != 2)
		goto Usage;

	setbuf(stdout, 0);
	n = atoi(argv[1]);
	m = 1<<(1<<n);

	for(i=0; i<n; i++){
		f = literal(i);
		cost[f] = 1;
		parents[f] = P(0,i+1);
		addqueue(f);
		cost[neg(f)] = 1;
		parents[neg(f)] = P(i+1,0);
		addqueue(neg(f));
	}

	x = 0;
	while(!emptyqueue()){
if(x++%4096 == 0)
printf("%ld.", (wp-rp+MAXQUEUE)%MAXQUEUE);
		i = fromqueue();
		for(j=0; j<m; j++){
			if(cost[j]==0)	/* not built yet */
				continue;
			build(i&j, i, j);
			build(i|j, i, j);
		}
	}

	worstf = 0;
	for(i=0; i<m; i++)
		if(cost[i] > cost[worstf])
			worstf = i;

	printf("\n%s %s requires %d ops\n", fmtbool(buf0, worstf),
		fmtexpr(buf1, worstf, 1), cost[worstf]-1);

	for(;;){
		printf("> ");
		gets(buf0);
		f = strtol(buf0, 0, 2);
		printf("%s %s requires %d ops\n", fmtbool(buf0, f),
			fmtexpr(buf1, f, 1), cost[f]-1);
	}
}