概要

フカシギの数え方(英:The Art of 1064)は、JST ERATO 湊離散構造処理系プロジェクト[1]によって制作され、日本科学未来館にて2012年8月~2013年4月の間展示されていた[2]作品群。中でもアニメーション作品の方はYouTubeやニコニコ動画にもアップロードされており、ネット上では主にこのアニメーション作品の事を差す場合が多い。一見ほのぼの教育アニメに見える序盤の展開からは想像も付かない内容の強烈さから、一躍話題となった。

テーマは後述する一見簡単な命題に見えて、数値が爆発する関数を取り扱っている。クッキークリッカー[3]寿司 虚空編と同様に、巨大数論的な内容が大衆の興味関心を惹きつけたものの一つである。

命題

n×nで区分された格子状の道を、左上から右下まで遠回りを許しつつ同じ場所を通らない道順の数。つまり経路問題の一種である。経路問題のうち最短距離を求めるものであれば、容易にこれを求めることができる公式が存在するが、遠回りを許す場合の場合の数を求める公式は現在のところ見つかっておらず、基本的には数えるしかないのが現状である。

しかしこの関数は後述するようにかなり大きな数に膨れ上がるため、単純な数え上げだけでは要する時間が指数関数的に増大し、いずれは限界が来てしまう。そのため、この数え上げの手続きを最適化するためのアルゴリズムが必要となり[4]、このアルゴリズムの必要性こそが、この作品における主題である。

数値一覧

先述の 湊離散構造処理系プロジェクト、およびR.Spaansや他の貢献者によって、n=26までの数値が現在判明している。全ての桁はオンライン整数列データベースに記載されている[5]ため、ここでは指数表記を用いて記述する。

n 全探索に要する時間(2000億通り/秒) 発見年月日 貢献者(OEIS記載のもの)
0 1
1 2
2 12
3 184
4 8,512
5 1,262,816
6 575,780,564 0.003秒
7 789,360,053,252 4秒
8 3.266598486...×1015 4時間32分
9 4.104420870...×1019 6.5年
10 1.568758030...×1024 25万年
11 1.824132915...×1029 289億年 1981 John Van Rosendale
12 6.452803934...×1034 1京年 1995/12/07 Donald Knuth
13 6.945066476...×1040 110
14 2.274497146...×1047 3.6
15 2.266745568...×1054 3592
16 6.874544560...×1061 1089
17 6.344814611...×1069 1005
18 1.782112840...×1078 2824阿僧祇
19 1.523344971...×1087 2.4無量大数 2005/01/14 M. Bousquet-Mélou, A. J. Guttmann and I. Jensen[6]
20 3.962892199...×1096 6.28×1077
21 3.137475105...×10106 4.97×1087 2012/09/18 H. Iwashita, J. Kawahara, and S. Minato
22 7.559702866...×10116 1.2×1098
23 5.543542935...×10127 8.78×10108
24 1.237171223...×10139 1.96×10120 2013/02/22 Ruben Grønning Spaans
25 8.402974857...×10150 1.33×10132 2013/04/11 Hiroaki Iwashita
26 1.736993158...×10163 2.75×10144 2013/11/18 Hiroaki Iwashita

増加速度の評価

前述の通り、この関数は一般的に求める公式が確立されていない。しかしながら、これより増加速度が確実に上回り、かつ一般的な公式を立てることのできる命題を与えることはできる。例えば同じ場所を通らずワープする道順の数は、以下のように求められる。

スタートとゴールを除いた格子上の座標の総数は、\((n+1)^2-2\)個と求められる。このスタート~ゴール間にある座標の総数を\(N\)と置いた時、N個以内で考えられる全ての順列の並びを挙げれば良いので、

\(\sum^N_{k=1} {}_N\text{P}_k = {}_N\text{P}_1+{}_N\text{P}_2+...+{}_N\text{P}_N \approx (e-1)\times N!\) (Nが大きいほどこれに近似)

ここでは\(N=(n+1)^2-2\)とnの2次関数に相当しており、その2次関数がさらに階乗されている形になるため、この関数の増加速度は\(n^{n^2}\)程度の増加オーダーとなり、フカシギの数え方の命題についても、これ以上の増加速度になることはないと言える。また、先述の数値一覧を見ると、指数部分の桁数が二次関数的に増大している様子が見受けられることから、こちらの命題もやはり\(n^{n^2}\)の増加オーダーに近似すると予測される。

動画

『フカシギの数え方』_おねえさんといっしょ!_みんなで数えてみよう! 「フカシギの数え方」_同じところを2度通らない道順の数

出典

特に記載のない限り、コミュニティのコンテンツはCC-BY-SAライセンスの下で利用可能です。