以前書いた方法の補足。
あれは、3^(2^k)ならば、それ同士をｋ回掛け合わせることで求まる（つまり3*3=9,9*9=81,81*81=...とやる）、ということの応用です。ｎを２進数で表して、右からｋ番目が１だったら3^(2^k)をｂに掛けていって、一番左の桁までこの作業をやったらｂには3^nが出来上がるという寸法。右からｋ番目の数字を調べるのに、ビットシフトを使っています。

今気づいたのですが、前回の方法だと最後にa^2を無駄に１回計算してしまいますね。
1. a=3^(2^0) (=3), b=1
2. もし n が奇数なら、b=b*a
3. n<=1 なら、5. に飛ぶ
4. a=a^2, n>>1, 2. に戻る
5. 最後に b=b-1 で b=3^n-1 になるはず。
この方が良さそうです。この方法で、例えば65535(２進数：1111111111111111)乗する場合で、乗算はb*aが16回とa^2が16回の合計32回で済みます。

ちなみに、このアルゴリズムの場合で3^cを配布する場合は、ｃは2の乗数が良さそうです。いまならc=32768でしょうか。これで最後に(a^16384)^2をする手間が省けます。

2^n-1 からコラッツ算の結果 3^n-1 になることを数式で証明。読みにくいですが。

2^n-1は奇数なので、３倍＋１をして、その結果は偶数なので２で割ると、
　 (3*(2^n-1)+1)/2 = (3*2^n-2)/2 = 3*2^(n-1)-1
となり、結果は奇数となる。よって以降同様に計算を行うと、
　 (3*(3*2^(n-1)-1)+1)/2 = 3^2*2^(n-2)-1
　 (3*(3^2*2^(n-2)-1)+1)/2 = 3^3*2^(n-3)-1
　 ・・・
となり、ｋ回「３倍＋１して２で割る」計算をした後の計算結果は 3^k*2^(n-k)-1 となる。すると、k=n のとき以下のようになる。
　 3^n*2^(n-n)-1 = 3^n-1
よって、ｋ回「３倍＋１して２で割る」、つまり総計算回数２ｋの時に計算結果は3^n-1となることが証明された。//

> Inf3
無限大の奇数にはコラッツ算を適用しても解けないということでしょうか？

> 3^n-1の求め方
sk_3141592さんの方法にシフト演算を併用すればさらに早くなると思います。
問題は b=b*a の部分ですが、３のべき乗である a を２進数に変換すればなんとかなるかもしれません。
例：a=3^2 のとき、3^2 は２進数で 1001（2^3 + 1）と表せます。
　　よって b=b*a は b = b<<3 + b とできます。
それに加えて、あらかじめサーバ側が計算しておいた 3^c （現在ならば c=44000 くらい）の数値をユーザー側に配布することで計算を省略するのはどうでしょうか？
sk_3141592さんの方法において、n = n-c, b = 3^c からスタートできます。

> turboさんは、書かれている事を自分で発見したのですか？
そうです。サイトで解説されていた、2^n -1 が２進数で１の連続になることから発想を得て、コラッツ算によって１の連続がどう変化していくのか見てみました。
すると１の連続に規則性が見られました。
これを元にして k * 2^n -1 → k * 3^n -1 を導出しました。

> 「メルセンヌ素数候補における」という部分は、どうなってしまうのでしょう？
私はそのままでいいと思います。序盤の計算が省略できるようになるとしても、プロジェクトの目的は変わらないからです。
どういう理論を使って計算のどの部分を省略しているか、を明記しておけば問題ないと思います。
厳密にやるなら、どの区間をどんなアルゴリズムで検証したか記録しておくほうがいいかもしれません。
仮に理論に穴が見つかった場合に１からやり直さなくても済む上、学術的な有効性が増します（論文が書けるかも！？）。

長文、失礼しました。

　下のほうに3^n-1からはじめれば早い、とありますが3^n-1の求め方と言えば、こういうのがありますね。

1. a=3^(2^0) (=3), b=1
2. もし n が奇数なら、b=b*a
3. a=a^2, n>>1
4. n>0 なら、2. に戻る
5. 最後に b=b-1 で b=3^n-1 になるはず。

例えば 3^25 なら、
3^25 = 3^16 * 3^8 * 3^1
　　 = 3^(2^4) * 3^(2^3) * 3^(2^0)
　　 = (((3^2)^2)^2)^2 * ((3^2)^2)^2 * 3
として求める方法で、たぶん３をｎ回掛けるよりは早いと思います。

　問題は、巨大数同士の掛け算にどれくらいの時間がかかるのか、ということ。

BACK TOP