この記事は、式神巨大数2021への投稿用です。
投稿の要綱[]
- プログラムの名前は、「くまむし数列数出力プログラム」です。
- プログラムの部門は、プログラム化部門です。
- プログラムのソースは、下記のソースコードにあるコードです。
- プログラムの言語は、Javascriptです。
- プログラムの実行方法は、 largenumber() です。
- プログラムの出力方式は、目的の巨大数が関数 largenumber() の戻り値として出力されるという方式です。
- プログラムが出力する巨大数の情報は、「このプログラムが出力する巨大数は ユーザーブログ:Kanrokoti/くまむし数列 で定義されているくまむし数列数です。」です。
説明[]
- 巨大数「くまむし数列数」は引数無しの関数 largenumber() として実装されています。
- FGH \(f_X(n)\) は関数 fgh(s,m,n) として実装されています。
- 展開関数 \(s[t]\) は expand(s,t) として実装されています。
- 二項関係 \(a<b\) は compare(a,b) として実装されています。
テストの仕方[]
- fgh(), expand(), compare() のテストは、同じ関数が https://koteitan.github.io/kumawormseq/ に実装されているので、ブラウザで これを開いてデバッグモードに入る(Chromeではctrl+shift+jを押す)ことで可能です。
- ソースコードは https://github.com/koteitan/kumawormseq/blob/main/kumawormseq.js でも見られるので、そちらの方がハイライトされて見やすいと思います。
ソースコード[]
/* Expantion rule of [1] */
var expand=function(a,t){
var n=a.length;
if(n==0){
return []; /* rule 1. */
}else if(a[n-1]==0){
return a.slice(0,n-1); /* rule 1-1. */
}else{
/*rule 1-2-*. ---------------------------*/
var i0=-1; /* child root */
for(var i=n-2;i>=0;i--){
if(a[i]<a[n-1]){
i0=i;
break;
}
}
/* finding good part and bad part. ------*/
var g; /* good part */
var b; /* bad part */
if(i<0){/* child root not found */
/* rule 1-2-2. */
g=[a[0]];
b=a.slice(1);
b[b.length-1]--;
}else{/* child root found */
j0=-1; /* bad root */
for(var j=i0-1;j>=0;j--){
if(a[j]==a[i0] && compare(a.slice(j), a.slice(i0))<0){
j0=j;
break;
}
}
if(j0<0){ /* j0 not found */
/* rule 1-2-1-2. */
g=[a[0]];
b=a.slice(1);
b[b.length-1]--;
}else{ /* j0 found */
var j1=-1;
for(var jd=j0+1;jd<=i0;jd++){
if(a[jd]==a[i0]){
j1=jd;
break;
}
}
/* rule 1-2-1-1. */
g=a.slice(0,j1+1);
b=a.slice(j1+1,n);
b[b.length-1]--;
}
}
var e=g;
for(k=0;k<t;k++){
e=e.concat(b);
}
return e;
}
}
/* Ordering of [1] */
var compare=function(a,b){
var len;
len=a.length;
len=a.length <= b.length?a.length:b.length;
for(var i=0;i<len;i++){
if(a[i]>b[i]) return +1;
else if(a[i]<b[i]) return -1;
}
if(a.length==b.length) return 0;
else if (a.length>b.length) return +1;
else return -1;
}
/* FGH of [1] */
var fgh=function(s,m,n){
if(m==0){
return n; /* rule 1. */
}else if(m==1){
if(s.length==0){
return n+1; /* rule 2-1. */
}else{
if(s[s.length-1]==0){
return fgh(expand(s,n),n,n); /* rule 2-2-2. */
}else{
return fgh(expand(s,n),1,n); /* rule 2-2-2. */
}
}
}else{
return fgh(s,1,fgh(s,m-1,n)); /* rule 3. */
}
}
/* FGH of [1] */
var largenumber=function(){
var n=1;
for(var i=0;i<100;i++) n*=10;
return fgh([0,n],n,n);
}