概要
フカシギの数え方は、JST ERATO 湊離散構造処理系プロジェクト[1]によって制作され、国立未来科学技術館にて展示されている作品群。中でもアニメーション作品の方はYouTubeやニコニコ動画にもアップロードされており、ネット上では主にこのアニメーション作品の事を差す場合が多い。一見ほのぼの教育アニメに見える序盤の展開からは想像も付かない内容の強烈さから、一躍話題となった。
テーマは後述する一見簡単な命題に見えて、数値が爆発する関数を取り扱っている。クッキークリッカーや寿司 虚空編と同様に、巨大数論的な内容が大衆の興味感心を惹きつけたものの一つである。
命題
n×nで区分された格子状の道を、左上から右下まで遠回りを許しつつ同じ場所を通らない道順の数。つまり経路問題の一種である。経路問題のうち最短距離を求めるものであれば、容易にこれを求めることができる公式が存在するが、遠回りを許す場合の場合の数を求める公式は現在のところ見つかっておらず、基本的には数えるしかないのが現状である。
しかしこの関数は後述するようにかなり大きな数に膨れ上がるため、単純な数え上げだけでは要する時間が指数関数的に増大し、いずれは限界が来てしまう。そのため、この数え上げの手続きを最適化するためのアルゴリズムが必要となり[2]、このアルゴリズムの必要性こそが、この作品における主題である。
数値一覧
ERATOは現在でもこの命題に取り組んでおり、数え上げ最適化のアルゴリズムによって、n=26までの数値が現在判明している。全ての桁はオンライン整数列データベースに記載されている[3]ため、ここでは指数表記を用いて記述する。
| n | 値 |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 2 | 12 |
| 3 | 184 |
| 4 | 8,512 |
| 5 | 1,262,816 |
| 6 | 575,780,564 |
| 7 | 789,360,053,252 |
| 8 | 3.266598486...×1015 |
| 9 | 4.104420870...×1019 |
| 10 | 1.568758030...×1024 |
| 11 | 1.824132915...×1029 |
| 12 | 6.452803934...×1034 |
| 13 | 6.945066476...×1040 |
| 14 | 2.274497146...×1047 |
| 15 | 2.266745568...×1054 |
| 16 | 6.874544560...×1061 |
| 17 | 6.344814611...×1069 |
| 18 | 1.782112840...×1078 |
| 19 | 1.523344971...×1087 |
| 20 | 3.962892199...×1096 |
| 21 | 3.137475105...×10106 |
| 22 | 7.559702866...×10116 |
| 23 | 5.543542935...×10127 |
| 24 | 1.237171223...×10139 |
| 25 | 8.402974857...×10150 |
| 26 | 1.736993158...×10163 |
関数の増加速度の評価
前述の通り、この関数は一般的に求める公式が確立されていない。しかしながら、これより増加速度が大きく、かつ一般的な公式を立てることのできる命題を与えることはできる。例えば同じ場所を通らずワープする道順の数は、以下のように求められる。
（ただし、n＞0の場合）
この関数はnが大きくなるほど実質的に\(((n+1)^2-2)!\)に近似し、急増加関数で\(f_2 (n^2)\)程度の増加オーダーとなるため、フカシギの数え方の命題についても、これ以上の増加速度になることはないと考えられる。また、先述の数値一覧を見ると、指数部分（桁の数）が二次関数的に増大している様子が見受けられることから、こちらの命題もやはり\(f_2 (n^2)\)の増加オーダーに近似すると予測される。
