前日記の回答をここで書いておきます。
あと1～3月にやった大会のritさん製作譜面のlord of warがまだ公開しておらず、先ほどtankentai2が譜面を追加したのでこれから公開作業に入ります。
誰も待ってないよね！(ぇ
そして難易度が-/5/6/9/8というね…正直楽と踊を分けた意味があるのかといわれると答えに詰まってしまいます＾＾；
さてとりあえず回答…
回答
問1
収束値は2。
A(n)＜2を示す。
A(1)＜2は明らか。
A(n)＜2ならばA(n+1)=√(2+A(n))＜√(2+2)=2よりA(n+1)＜2
よって数学的帰納法より上限2として収束する。
また数列自体は確かに両辺二乗するとA(n+1)^2-A(n)-2=0となり特性方程式がx^2-x-2=0となり-1か2で収束することが確かめられる。
実際この値は負になることはないのだから2で収束するのはここから明らかである。
問2
3番目の素数から発見できるようになった。
これは単純にプログラム終了条件がx=mとなること(70行目)なのでx≧3でないとプログラムが終了しないことが理由です。
そしてこの改良前のプログラムは各値nに対し2～√(n+1)の全ての自然数について割り切れるかを判別していたが改良後は奇数nに対し3～√(n+1)の全ての奇数について割り切れるかを判別している。
奇数nに対しn-1とnに対しての計算量を考える。
そうするとn-1は偶数なので改良前は2で割り切れることを確かめる演算だけを行う。
以下50行目の判別式を何回計算したかで考える。
nに対しては改良前は2,3,…,Nと計算していた。
N=奇数の場合改良後は改良前の半分の回数で判別していることになる。
N=偶数の場合は判別式に通すiは偶数のほうが多いのでこれも改良後は半分以下の回数で判別している。
よって全体で見て50行目の判別式を通す回数が半分未満になっているので計算時間は半分以下となる。
補足
最後のn=奇数でN=偶数というのはn=素数であった場合は実際にこのパターンがあるので見過ごすわけには行きません。
n≠素数なら偶数で割り切れないのでN=偶数というのは有り得ませんがn=素数ならN=偶数というのは可能性として有り得ます。
例：n=11、√(n+1)=4.…より2,3,4について判別式を使います。このとき末端の値は偶数(=4)ですね。
問3
補題1：割る数が素数で割られる数が自然数の割り算の結果がn桁の循環小数となるなら割る数pはA(n)の約数である
証明
割る数、割られる数をそれぞれi,aと置く。
このときa/p=bとしてbはn桁の循環小数であるのだから循環小数を分数で表すようにすると…
10^n×a/p=10^n×b
a/p=b
bはn桁の循環小数なのだから上から下を引くと右辺は自然数となる。
そこで10^n×b-b=cと置く。
(10^n-1)×a/p=c
⇔A(n)*a/p=c
cは自然数なのでpはaかA(n)の約数であるがpがaの約数ならa/p=自然数となり循環小数とならない。
よってpはA(n)の約数となる。
補題2：1/pが循環小数となる場合その桁数はp-1以下である。
証明
x≡i(mod p)とするときy≡10i(mod p)(0≦x,y≦p-1)とする写像f:x→yを考える。
割り算で小数点以下を計算する場合余りxに対し10倍してnp(0≦n≦9、0≦10x-np≦p)を引いて…という動作を繰り返すがこのときxに大して1回これを行った結果の余りがyである。
(これは計算方法より明らか)
よって1/pの循環する桁数と求めるということはx≡1(mod p)に対しfで何回動かしたら１に戻ってくるかという問題と同値となる。
またx=0とy=0はpが2,5を除く素数ならば1対1対応となる。
x=0→y=0は自明
またiがpで割り切れないなら10^n×iもpが2,5以外の素数なら10^nで割り切れないので10^n×iも割り切れない。つまりx≠0→y≠0も成立。
よってx=0とy=0は一対一対応となる。
これによりx=1,2,…p-1についてだけ考えればいいがもしこの循環回数がp回以上となるなら鳩の巣原理より1,2,…p-1のいずれかの数字が重複してることになる。
重複してる数をmと置くとfを作用させることで1→…→m→…→m→1と少なくともなっている。
このときm→…→mの部分だけで循環しているのでより少ない回数で循環することになる。
よって循環回数がp回以上ならばより少ない回数の循環を作ることが出来る。
これを帰納的に使うことでp-1回以下の循環を作ることが出来る。
補題2より1/pの循環桁数をmと置くと1≦m≦p-1が成立。
またこのとき補題1よりpはA(m)の約数となる。
またA(m)はB(p)の約数であるのは明らかなのでこれよりpはB(p)の約数であることが示された。
