Fandom

巨大数研究 Wiki

フカシギの数え方

548このwikiaの
ページ数
新しいページをつくる
コメント3 シェアする

概要編集

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

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

命題編集

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

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

数値一覧編集

ERATOは現在でもこの命題に取り組んでおり、数え上げ最適化のアルゴリズムによって、n=26までの数値が現在判明している。全ての桁はオンライン整数列データベースに記載されている[4]ため、ここでは指数表記を用いて記述する。

n 全探索に要する時間(2000億通り/秒) 発見年月日
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
12 6.452803934...×1034 1京年
13 6.945066476...×1040 110
14 2.274497146...×1047 3.6
15 2.266745568...×1054 35921995/12/07
16 6.874544560...×1061 1089
17 6.344814611...×1069 1005
18 1.782112840...×1078 2824阿僧祇
19 1.523344971...×1087 2.4無量大数
20 3.962892199...×1096 6.28×1077
21 3.137475105...×10106 4.97×10872012/09/18
22 7.559702866...×10116 1.2×1098
23 5.543542935...×10127 8.78×10108
24 1.237171223...×10139 1.96×101202013/02/22
25 8.402974857...×10150 1.33×101322013/04/11
26 1.736993158...×10163 2.75×101442013/11/18

増加速度の評価編集

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

スタートとゴールを除いた格子上の座標の総数は、\((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}\)の増加オーダーに近似すると予測される。

動画編集

『フカシギの数え方』 おねえさんといっしょ! みんなで数えてみよう!08:11

『フカシギの数え方』 おねえさんといっしょ! みんなで数えてみよう!

「フカシギの数え方」 同じところを2度通らない道順の数04:20

「フカシギの数え方」 同じところを2度通らない道順の数

出典編集

  1. http://www-erato.ist.hokudai.ac.jp/html/php/sub_html.php?id=19
  2. [1]
  3. http://www.nii.ac.jp/userimg/openhouse/2013/lec_minato.pdf
  4. http://oeis.org/A007764

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

Fandomでも見てみる

おまかせWikia