\datethis @* Intro. A quickie to find a longest string that avoids the interesting set of unavoidable'' $m$-ary strings of length $n$ constructed by Champarnaud, Hansel, and Perrin. Their construction can be viewed as finding the minimum number of arcs to remove from the de Bruijn graph of $(n-1)$-tuples so that the resulting graph has no oriented cycles. (Because each $n$-letter string corresponds to an arc that must be avoided.) This program constructs the graph and finds a longest path. @d m 2 /* this many letters in the alphabet */ @d n 20 /* this many letters in each string */ @d space (1<<(n-1)) /* $m^{n-1}$ */ @c #include char avoid[m*space]; /* nonzero if the arc is removed */ int deg[space]; /* outdegree, also used as pointer to next level */ int link[space]; /* stack of vertices whose degree has dropped to zero */ int a[n+1]; /* staging area */ int count; /* the number of vertices on the current level */ int code; /* an $n$-tuple represented in $m$-ary notation */ main() { register int d,j,k,l,q; register int top; /* top of the linked stack */ @; for (d=0; count; d++) { printf("Vertices at distance %d: %d\n",d,count); for (l=top, top=-1, count=0; l>=0; l=link[l]) @ } @; } @ Algorithm 7.2.1.1F gives us the relevant prime powers here. @= for (j=0;j; for (j=n;a[j]==m-1;j--); if (j==0) break; a[j]++; for (k=j+1;k<=n;k++) a[k]=a[k-j]; } printf("m=%d, n=%d: avoiding one arc in each of %d disjoint cycles\n",m,n,d); @ At this point $\lambda=a_1\ldots a_j$ is a prime string and $\alpha=a_1\ldots a_n=\lambda^{n/j}$. The crux of the Champarnaud/Hansel/Perrin method is to find the shortest prime $\mu$ such that $\alpha$ has the form $\mu^{\lfloor n/\vert\mu\vert\rfloor}\beta$, and to avoid the string $\beta\mu^{\lfloor n/\vert\mu\vert\rfloor}$. We have $\mu=\lambda$ and $\beta=\epsilon$ if \$j= { d++; if (jq) break; l=k; if (k==n) break; } } for (code=0,k=q+1;k<=n;k++) code=m*code+a[k]; for (k=1;k<=q;k++) code=m*code+a[k]; @; } @ @= avoid[code]=1; q=code/m; deg[q]--; if (deg[q]==0) deg[q]=-1, link[q]=top, top=q, count++; @ @= for (j=m-1; j>=0; j--) { k=l+j*space; if (!avoid[k]) { q=k/m; deg[q]--; if (deg[q]==0) deg[q]=l, link[q]=top, top=q, count++; } } @ Here I apologize for using a dirty trick: The current value of |k| happens to be the most recent value of |l|, a vertex with no predecessors. @= printf("Path:"); for (code=k,j=1;j=0) { printf(" %d",deg[k]%m); k=deg[k]; } @* Index.