概要[]
フカシギの数え方(英: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\times N!\) (Nが大きいほどこれに近似)
ここでは\(N=(n+1)^2-2\)とnの2次関数に相当しており、その2次関数がさらに階乗されている形になるため、この関数の増加速度は\(n^{n^2}\)程度の増加オーダーとなり、フカシギの数え方の命題についても、これ以上の増加速度になることはないと言える。また、先述の数値一覧を見ると、指数部分の桁数が二次関数的に増大している様子が見受けられることから、こちらの命題もやはり\(n^{n^2}\)の増加オーダーに近似すると予測される。
動画[]
出典[]
- ↑ http://www-erato.ist.hokudai.ac.jp/html/php/sub_html.php?id=19
- ↑ メディアラボ第11期展示「フカシギの数え方」|日本科学未来館 常設展示
- ↑ [1]
- ↑ http://www.nii.ac.jp/userimg/openhouse/2013/lec_minato.pdf
- ↑ http://oeis.org/A007764
- ↑ M. Bousquet-Mélou, A. J. Guttmann and I. Jensen, Self-avoiding walks crossing a square, arXiv:cond-mat/0506341, 2005.