программа на С
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 16
#define u16 unsigned short
#define u32 unsigned
#define max 20
typedef struct{u16 q[N];short nz;}u16N;
typedef struct{u16N u0,u1;}u16N2;
typedef struct{int n,g;}int2;
typedef struct{int len;int2* p;}int2arr;
u16N new16N(){u16N a;for(int i=0;i<N;i++)a.q[i]=0;a.nz=0;return a;}
int nZ(u16 q[N]){int cnt=N;for(int i=N-1;i>=0;i--)if(q[i])break;else cnt--;return cnt;}
u16N toU16N(u32 n){u16N a=new16N();a.q[0]=n;a.q[1]=(n>>16);a.nz=a.q[1]?2:(a.q[0]?1:0);return a;}
u16N sum(u16N a,u16N b){
int m=a.nz>=b.nz?a.nz:b.nz;
u16N s=new16N();
u32 c=0;
for(int i=0;i<m;i++){u32 t=c+a.q[i]+b.q[i];s.q[i]=t;c=t>>16;}
if(c&&m<N)s.q[m]=1;
s.nz=nZ(s.q);
return s;
}
int cmp(u16N a, u16N b){
int s=a.nz-b.nz;
if(s)return s;
for(int i=a.nz-1;i>=0;i--)if(s=a.q[i]-b.q[i])return s;
return 0;
}
u16N inv(u16N a){
u16N b;
for(int i=0;i<N;i++)
b.q[i]=~a.q[i];
b.nz=nZ(b.q);
return b;
}
u16N subt(u16N a, u16N b){return sum(a,sum(inv(b),toU16N(1)));}
u16N shL0(u16N a,int n){
u16N b=new16N();
u16 c=0;
for(int i=0;i<a.nz;i++){u32 r=c|((u32)a.q[i]<<n);b.q[i]=r;c=r>>16;}
if(a.nz<N)b.q[a.nz]=c;
b.nz=nZ(b.q);
return b;
}
u16N shL(u16N a,int n){
u16N b=shL0(a,n&0xf);
int n1=n>>4;
if(n1)for(int i=a.nz;i>=0;i--){int j=i+n1;if(j<N)b.q[j]=b.q[i];if(i<N)b.q[i]=0;}
b.nz=nZ(b.q);
return b;
}
u16N shR(u16N a){
u16N b=new16N();
for(int i=a.nz-1;i>=0;i--){u32 u=(i==a.nz-1?0:a.q[i+1]);u32 w=(u<<16)|a.q[i];b.q[i]=(w>>1);}
b.nz=nZ(b.q);
return b;
}
int max1(u16N a){
int k=-1;
if(a.nz){for(int i=15;i>=0;i--)if((a.q[a.nz-1]>>i)&1){k=i;break;}k+=(a.nz-1)<<4;}
return k;
}
u16N2 div2(u16N a,u16N b){
u16N2 res;
res.u0=new16N();
int d=max1(a)-max1(b);
if(d<0){res.u1=a;return res;}
u16N bb=shL(b,d);
if(cmp(a,bb)>=0){res.u0=toU16N(1);a=subt(a,bb);}
while(cmp(bb,b)){
bb=shR(bb);
res.u0=shL(res.u0,1);
int k=cmp(a,bb);
if(k>=0){if(!res.u0.nz)res.u0.nz=1;res.u0.q[0]|=1;a=subt(a,bb);}
}
res.u1=a;
return res;
}
void show(u16N a){
if(!a.nz){printf("0\n");return;}
int d[(int)(N*1.25)+1];
int cnt=0;
u16N b=toU16N(1000000);
while(a.nz){u16N2 c=div2(a,b);d[++cnt-1]=c.u1.q[0]+((u32)c.u1.q[1]<<16);a=c.u0;}
printf("%d",d[cnt-1]);
for(int i=cnt-2;i>=0;i--)printf(" %06d",d[i]);
}
int2arr f(int n,int l){
int q[max-1];
int cnt=0;
for(int i=0;i<l;i++)
if((n>>i)&1)q[++cnt-1]=i;
int q1[max],s[max];
int cnt1=0;
for(int i=0;i<cnt;i++)
if(i==0){q1[0]=q[0];q1[1]=q[0]+1;s[0]=s[1]=1;cnt1=2;}
else{
if(q[i]==q1[cnt1-1])s[cnt1-1]++;
else{q1[++cnt1-1]=q[i];s[cnt1-1]=1;}
q1[++cnt1-1]=q[i]+1;s[cnt1-1]=1;
}
int2arr a;
a.len=1<<cnt1;a.p=(int2*)malloc(a.len*sizeof(int2));
for(int i=0;i<a.len;i++){
int g=0;int n=0;
for(int j=0;j<cnt1;j++){int k=(i>>j)&1;n|=k<<q1[j];if(k&&s[j]>1)g++;}
a.p[i].n=n;a.p[i].g=g;
}
return a;
}
char* hms(char* time){
char* hms=(char*)malloc(9*sizeof(char));
for(int i=0;i<8;i++)hms[i]=time[i+11];
hms[8]='\0';
return hms;
}
int main(){
printf("max=%d\n\n",max);
int l=1;
u16N* m=(u16N*)malloc(2*sizeof(u16N));
m[0]=toU16N(0);m[1]=toU16N(1);
while(l<max){
int size=1<<l;
int size1=1<<(l+1);
u16N* m1=(u16N*)malloc(size1*sizeof(u16N));
for(int i=0;i<size1;i++)m1[i]=new16N();
for(int i=0;i<size;i++){
int2arr a=f(i,l);
for(int j=0;j<a.len;j++)m1[a.p[j].n]=sum(m1[a.p[j].n],shL0(m[i],a.p[j].g));
free(a.p);
}
free(m);m=m1;l++;
u16N s=new16N();
for(int i=0;i<size1;i++)s=sum(s,m1[i]);
int tm=time(0);
printf("%s",hms(ctime(&tm)));
printf("%4d = ",l);
show(s);printf("\n\n");
}
free(m);
return 0;
}