\datethis @*Intro. I'm trying to calculate a few million Ulam numbers. This sequence $$(U_1,U_2,\ldots{})=(1,2,3,4,6,8,11,13,16,18,26,\ldots{})$$ is defined by setting $U_1=1$, $U_2=2$, and thereafter letting $U_{n+1}$ be the smallest number greater than $U_n$ that can be written $U_j+U_k$ for exactly one pair $(j,k)$ with $1\le j unsigned int ubit[nsize+1], vbit[nsize+1]; char decode[64]; /* table for computing the ruler function */ int count[gsize],example[gsize]; main() { register unsigned int j,jj,k,kk,kq,kr,del,c,n,u,prevu,gap; @; gap=1; ubit[0]=0x6, kr=n=prevu=2, kq=0, kk=4; /*$U_1=1$,$U_2=2$*/ while (1) { @; @; k=kr+(kq<<5); del=k-prevu; count[del]++, example[del]=k; if (del>gap) { if (del>=gsize) { fprintf(stderr,"Unexpectedly large gap (%d)! Recompile me...\n",del); return -666; } gap=del; printf("New gap %d: U_%d=%d, U_%d=%d\n",gap,n-1,prevu,n,k); fflush(stdout); } prevu=k; if ((n%m)==0) { printf("U_%d=%d is about %.5g*%d\n",n,k,((double)k)/n,n); fflush(stdout); } } done: @; printf("There are %d Ulam numbers less than %d.\n",n,nmax); } @ As we compute, we'll implicitly have$k=32|kq|+|kr|$, where$0\le|kr|<32$; also |kk=1<>kr)&1|, etc. @= for (j=c=0,jj=j+kq;j=nsize) goto update_done; del=(ubit[j]<>(31-kr))>>1; @; } if (jj>=nsize) goto update_done; u=ubit[kq]&(kk-1); del=(u<>(31-kr))>>1; @; if (c!=0) { jj++,del=c; @; } update_done:@; @ @= u=(ubit[jj]^del)&~vbit[jj]; vbit[jj]|=ubit[jj]&del; ubit[jj]=u; @ @= u=ubit[kq]&-(kk+kk); /* erase bits$\le k$*/ while (!u) { if (++kq>=nsize) goto done; u=ubit[kq]; } kk=u&-u; /* now we must calculate$|kr|=\lg|kk|\$ */ kr=decode[(mhmartin*kk)>>27]; n++; @ @d mhmartin 0x07dcd629 @= for (k=0,j=1;j;k++,j<<=1) decode[(mhmartin*j)>>27]=k; @ @= for (j=1;j<=gap;j++) if (count[j]) printf("gap %d occurred %d time%s, last was %d\n", j,count[j],count[j]==1?"":"s",example[j]); @*Index.