=
ptrq=stack[s].ptrq,ptrp=stack[s].ptrp;
lbq=stack[s].lbq,ubq=stack[s].ubq;
lbp=stack[s].lbp,ubp=stack[s].ubp;
outdeg[ubq]--, outsum[ubq]-=s;
outdeg[ubp]--, outsum[ubp]-=s;
q=tail[s], p=a[s]-q, r=stack[s].r;
@ After the test in this step is passed, we'll have |ubp>ubq| and |lbp>lbq|.
@=
lbp=l[p];
if (lbp>=s) goto failpq;
while (b[lbp]p) goto failpq;
for (ubp=lbp;a[ubp+1]<=p;ubp++);
if (ubp==s-1) lbp=ubp;
if (p==q) lbq=lbp,ubq=ubp;
else {
lbq=l[q];
if (lbq>=ubp) goto failpq;
while (b[lbq]=ubp) goto failpq;
if (a[lbq]>q) goto failpq;
for (ubq=lbq;a[ubq+1]<=q && ubq+1=
{
i=undo[--ptr];
if (i>=0) a[i>>24]=i&0xffffff;
else b[(i&0x3fffffff)>>24]=i&0xffffff;
}
@ At this point we know that $a[ubp]\le p\le b[ubp]$.
@=
if (a[ubp]!=p) {
newa(ubp,p);
for (j=ubp-1;(a[j]<<1)>1;
if (i>b[j]) goto failp;
newa(j,i);
}
for (j=ubp+1;a[j]<=a[j-1];j++) {
i=a[j-1]+1;
if (i>b[j]) goto failp;
newa(j,i);
}
}
if (b[ubp]!=p) {
newb(ubp,p);
for (j=ubp-1;b[j]>=b[j+1];j--) {
i=b[j+1]-1;
if (ib[j-1]<<1;j++) {
i=b[j-1]<<1;
if (i;
@ If, say, we've just set |a[8]=b[8]=132|, special considerations apply,
because the only addition chains of length~8 for 132 are
$$\eqalign{
&1,2,4,8,16,32,64,128,132;\cr
&1,2,4,8,16,32,64,68,132;\cr
&1,2,4,8,16,32,64,66,132;\cr
&1,2,4,8,16,32,34,66,132;\cr
&1,2,4,8,16,32,33,66,132;\cr
&1,2,4,8,16,17,33,66,132.\cr}$$
The values of |a[4]| and |b[4]| must therefore be 16; and then, of course,
we also must have |a[3]=b[3]=8|, etc. Similar reasoning applies
whenever we set $a[j]=b[j]=2^j+2^k$ for $k\le j-4$.
Such cases may seem extremely special. But my hunch is that they are
important, because efficient chains need such values. When we try
to prove that no efficient chain exists, we want to show that
such values can't be present. Numbers with small |l[p]| are harder
to rule out, so it should be helpful to penalize them.
@=
i=p-(1<<(ubp-1));
if (i && ((i&(i-1))==0) && (i<<4)>=1,j--);
if (b[j]<(1<=
if (a[ubq]!=q) {
if (a[ubq]>q) goto failq;
newa(ubq,q);
for (j=ubq-1;(a[j]<<1)>1;
if (i>b[j]) goto failq;
newa(j,i);
}
for (j=ubq+1;a[j]<=a[j-1];j++) {
i=a[j-1]+1;
if (i>b[j]) goto failq;
newa(j,i);
}
}
if (b[ubq]!=q) {
if (b[ubq]=b[j+1];j--) {
i=b[j+1]-1;
if (ib[j-1]<<1;j++) {
i=b[j-1]<<1;
if (i;
@ @=
i=q-(1<<(ubq-1));
if (i && ((i&(i-1))==0) && (i<<4)>=1,j--);
if (b[j]<(1<