進捗は遅いが,多少は進んだ

進捗は遅いが,多少は進んだ.φとψを出力するようにしてみたが,出力との関わりが不明だ.Gをnとk-1の最大公約数,Mを異種文字数としたとき,縦数列ではG*M=k-1がつねに成立しているが,横数列では崩れているように思われる.周期とψには連関があるはずだが読み取れない.ψの取り方が間違っているのだろうか?つまり,横数列・縦数列の周期性と循環小数の周期性ないし,剰余数列の周期性との関係が見えない.ψを計算するためには,nとbを決める必要があるが,何がnに該当し,何をbとすればよいのかがいまいち釈然としない.

ψ値はφ値の約数である.今のところ,nのφ値を表示している.この値とψは,確かにψ|φの関係になっているが,これでよいのだろうか?φ(k)とすると,値は6になる.GとMの積はn=1, 6を除くとすべてこの値に一致する.ただし,この場合,たとえばn=5ではφ=6, ψ=4でψはφを割り切れなくなる.ψ(k, i)を取ると,n=1では0となるが,それ以外では3, 6, 3, 6, 2となり,φの約数が出てくる.特に,n=3, 5 などの尽数列になるところで,ψ=6となっている点が興味深い.また,この数字はn=1の場合を除いて,Mと完全に一致している.確かにこの数値の方が正しいように思われる.

Mとψが(ほぼ)完全に一致するというのは重要なポイントではあるが,ここではちょっと置いて,もう少し先に進んでおくことにしよう.べき剰余マトリックスではテーブルの出力をもう少し充実させるという課題が残っているが,そこに進む前に,べき乗剰余との関係をもう少し明らかにしておきたい.循環小数との関係についてはまだかなり不明な点が多いのでしばらく置くとして,べき乗剰余とべき剰余マトリックスは地続きであるのだから,その関係をもっとはっきりさせる必要がある.このためには,べき乗剰余とべき剰余マトリックスを一体化させるというのが一番近道なのではないかと思う.

べき乗剰余数列には3機能ある.①n^p mod k を計算する,②n^p mod k の剰余数列周期を計算する,③これらの包括テスト.3機能の中心が②の剰余数列周期の計算にあることは確かだ.べき乗剰余周期はψに関わりがあるはずだから,いま興味を持っている点にもっとも近いはずだ.この機能のコアはResidueFuncという関数だ.この関数は「’対象数nのべき乗の k による剰余を計算し,剰余列の周期を返す」というもので,nとkは画面上の入力から取り出している.ModPowでべき剰余を計算しているが,その範囲を1~2kとしている.kはBigIntegerではあるが,およそ整数範囲内であることが予定されている.

R()という配列にはべき剰余の計算値が格納され,それを上から走査して繰り返しの開始点を見つけるというやり方だ.原理的にはべき乗マトリックスで実施していることと大差ないものと思われる.マトリックスでは剰余をRというハッシュテーブルに格納する代わりに,直接マトリックスとして構成している.つまり,マトリックスの一行がほぼべき乗剰余の1回分に相当する.マトリックスのkがべき乗剰余のnに相当しているという点がやや混乱を招き易いところだ.

べき乗剰余では一行分の計算しか実施していないので,そこそこの時間で計算完了しているが,マトリックスではk^2の計算を行っているので,数字が大きくなるとやや実際的なものではなくなってしまうという点が致命的なところだ.逆にべき乗剰余の計算法を使ってマトリックスを構成することは可能だろうか?いや,べき乗剰余にはPというパラメータが関わっている.ここで計算しているのはn^p mod kという計算だ.いや,pは可変で1~2kまでというのはこの値のことだ.従って,マトリックスのkと剰余数列のkは一致している.

マトリックスでも n^p mod k を計算しているが,マトリックスではn≦kの範囲しか扱わない.循環しているからそれ以上は不要という立場だ.従って,剰余数列でもkの剰余を取っているのだから,kより大きい数字は数列には現れない.であるとすれば,べき乗剰余数列で計算するときでも最初に n=N mod k から始めてよいのではないか?これができれば計算は相当縮小され,高速化するものと思われる.ResidueFuncにはResidueFunc2というバリエーションがあり,並列実行して値が一致していることを確認しているが,どこが違うのか?⇒多分この違いはスキャンする範囲が違うだけではないかと思う.つまり,ResidueFunc2では2kではなく,kまでの範囲しか検定していない.

周期の開始点を見つけるだけなら,おそらくこれで十分と思われるが,周期そのものはkの範囲を超えないと出て来ないのではないだろうか?もう一つ不審な点は,ResidueFuncにはドロップという概念があるのに,マトリックスではそのような概念が存在していないように見える点だ.ドロップは循環小数の固定部に関係しているような気がするが,ドロップが出てこないのは,マトリックスの対象をいまのところ素数に限定しているためかもしれない.

ResidueFuncのバリエーションをもうひとつ作って,N mod k をnとして与えた場合にどうなるかを見てみるというのがよいのではないか?ResidueFuncをマトリックスに移植してテストするより,剰余数列側で試した方が早い.ちゃんぽんになってしまうが,やってみることにしよう.ResidueFuncとResidueFunc2の比較ではおそらくcycleしか見ていないのだろう.⇒いや,「N mod k をnとして与えた場合」というのはすでにGoButtonでやっていることだ.冒頭でa=ModPow(n, p, k)を実行し,その値を使って,ResidueFunc(a, k, True)を実行している.つまり,ResidueFuncの対象値aはすでに剰余を取った値だ.

確かに,マトリックスの計算と剰余数列の計算は一致している.この計算にはBは関わっていないので,ψ値も計算されていない.また,循環小数とは異なり,「固定部」というのは出て来ない.k=24でドロップが発生した.N=2,i=48, cycle=2, x=2だ.どういう現象が起きているのか?Kを1から25まで変えてテストしてみた.K=9で発生する.開始番号Nを1~に変更したら,K-4で発生した.i=8, cycle=1, x=2だ.ドロップというのは,かなり限られた条件でしか起きていないようだ.

包括テストではGoButtonでやっているようなa=ModPow(n, p, k)の操作は行わず,直接numを対象にべき乗剰余を取っている.また,PsiFunctionでは(nとbが互いに素でない場合には)内部でResidueFuncを使って循環周期を求めている.ただし,ここではResidueFuncを呼び出しているだけで,その結果は反映されていない.つまり,未完ということのようだ.

ドロップが発生するのはkが合成数の場合に限られているというのは間違いない.k=1~25の範囲では,k=4, 8, 9, 12, 16, 18, 20, 24, 25で起きている.ドロップが起きていない数として,6, 10, 14, 15, 21, 22がある.おそらくドロップが起きる条件は素因数の積に指数が2以上のものが含まれるという点にあるように推定される.どこかでこのような条件を見たことがあるような気がするのだが,思い出せない.⇒以下の「ひとつ,おもしろいことを発見した」でそのことを述べている.

https://www.facebook.com/groups/2354748741306929/posts/6031847776930322/?comment_id=6046762375438862

引用しておこう.「べき乗の剰余数列は一般に周期性を持っているが,べき乗の剰余数列の初項とそれに続く項は周期数列から漏れ落ちる場合がある.このような項をドロップアウト項ないし落伍項と呼ぶことにする.①nとkが互いに素の場合には,落伍項は生じない.②kが素数の単純な積である場合にも落伍項は生じない,③kの素因数がべきになっている場合には落伍項が生じる.」

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA