ナベアツ数考(4)
またしょーもないこと考えてみた．
定義：
k番目のナベアツ数N_inv(k)を第k項とする数列をナベアツ数列(nn)とする．
定理：
ナベアツ数列 (nn) = 3,6,9,12,13,15,... には無限に素数が存在する．
こんなもんいつ使うんだって話はとりあえず保留．
ナベアツ数には3の倍数と3のつく数があるが，3の倍数のほうは「3」以外素数になり得ない．
しかも，「3」は3のつく数でもあるから，これは実質的に「3のつく数からなる数列には無限に素数が存在する」といっているのと同じである．
この時点でもうほとんど答えをいってしまっている気もするが，話を続けよう．
ディリクレ(Johann Peter Gustav Lejeune Dirichlet, 1805-1859)が1837年に証明した次の超有名な定理がある．
いま，初項が3で公差が10である等差数列(an)を考えると，3と10は互いに素であるからこの数列には無限の素数が存在することが算術級数定理からいえる．
この数列は 3,13,23,33,43,53,63,... と必ず3のつく数であるから，ナベアツ数列(nn)は(an)を内包しており，故にナベアツ数列には無限に素数が存在する．
そういえばいつ使うんだって話が保留だった．
系：
世界のナベアツが，3の倍数と3が付く数字だけアホになり，5の倍数だけ犬っぽくなり，8の倍数だけ人探しをしてる感じになり，9の倍数で正気に戻り，．．．と「□の倍数のときに○○になる」を付け加えていくら拡張しても，単純にアホになるだけの数がなくなってしまうことはない．
前回，N_inv(n)を求めるまでのループの繰り返し回数がnが大きくなるにつれて非常に高い確率で圧倒的に少なくなることについて言い逃げだったので，nが10kの形で表わされる場合についてk=1000まで検証してみた*1．
求値までのN()の呼び出し回数．
alg.1：ナイーブな二分探索法
alg.3：N_inv(n)を下から抑えるアルゴリズム
やっぱalg.3のほうが劇的に速かった．
