正の整数 n について、(109*10^n -1)/9 は、かならずしも合成数とはかぎりません。
さて、どうしてでしょうか？
らすかるさんからのコメントです。（令和５年５月１４日付け）
[前者]・・・分子が、3339、33399、333999、3339999、… のようになる．．．。
n=3m のとき、分子が 333999、333999999、333999999999、… のように 3m+3 桁だから
333で割り切れ、333÷9=37 なので、与式は、37 で割り切れる。
n=3m-1 のとき、分子は、33399、33399999、33399999999、… だから
与式は、3711、3711111、3711111111、… のようになり、全桁の合計が 3 の倍数だから、
3 で割り切れる。
n=6m-2 のとき、分子は、3339999、3339999999999、3339999999999999999、… のように
なり、3339999÷13=256923、999999÷13=76923 だから、分子÷13 は、
256923、256923076923、256923076923076923、… となり、分子は、13 で割り切れ、かつ、
全桁の合計が 9 の倍数だから、9 で割り切れる。
そして、13 は、分母の 9 と互いに素だから、与式も 13 で割り切れる。
n=6m-5 のとき、分子は、3339、3339999999、3339999999999999、… のようになり
3339÷7=477、999999÷7=142857 だから、分子÷7 は、
477、477142857、477142857142857、… となり、分子は、7 で割り切れ、かつ、全桁の合計
が 9 の倍数だから、9 で割り切れる。
そして、7 は分母の 9 と互いに素だから、与式も 7 で割り切れる。
まとめると、
n=3m のとき、37 で割り切れ、
n=3m-1 のとき、3 で割り切れ、
n=6m-2 のとき、13 で割り切れ、
n=6m-5 のとき、7 で割り切れる
から、常に合成数。
[後者]・・・ n=136 のとき素数という反例があるから、合成数とは限らない。
Dengan kesaktian Indukmu さんからのコメントです。（令和５年５月１４日付け）
素晴らしいです。なお、ネタ元は、「A112386」です。なお、「A107612」によれば、らすかる
さんにみつけて頂いた n = 136 の次は、184、そのまた次は、623 とのことです。
らすかるさんからのコメントです。（令和５年５月１４日付け）
「A112386」は、なぜこんなにちょっとしかデータがないんでしょうかね。せっかく 37 の例を
載せているんだから、
251、26111、271、281、29111111、3011、311、3211111111111111111111111111111111111、
34111111、3511、361111、-1
ぐらい載せればいいのに．．．。（先頭の3行のところではなくLINKSにある表のことです）
ちょっと調べて、たくさん追加してみようかな。
Dengan kesaktian Indukmu さんからのコメントです。（令和５年５月１４日付け）
正攻法で真面目に素因数分解をしていくと、
56111…11 （(505*10^n -1)/9）での素数探しで、計算量が爆発するのではと危惧いたします。
うんざりはちべえさんからのコメントです。（令和５年５月１５日付け）
(a10^n-1)/9 とか a10^n-1 にしたらどうでしょう。
a は、2m、2m+1 とか、3m、3m+1、3m+2 とか、10m、10m+1、・・・、10m+9 なんかどうでしょ
う・・・・・。
１．a=10m (mは自然数） とすると、 a10^n-1=10m10^n-1=(m-1)10^(n+1)+10^(n+1)-1
ここで、10^(n+1)-1=99・・99=(11・・11)x9
11・・11を考えると、1がn+1個並んだ数なので、n+1が合成数なら、かならず割れる。
n+1=6=2x3 なので、
111111=11x(10101)=111x(1001)=11x3x7x13x37=(111)x(1001)=(3x37)x(7x11x13)
これより、n+1が偶数なら、11の倍数。
n+1が3の倍数なら、111(=3x37)の倍数。
n+1が5の倍数なら、11111(=41x271)の倍数。
n+1が7の倍数なら、1111111(=239x4649)の倍数。
n+1が11の倍数なら、11111111111(=21649x513239)の倍数。
n+1が13の倍数なら、1111111111111(=53x79x265371653)の倍数。
以下省略
また、(m-1)10^(n+1)は、(m-1)x2^(n+1)x5^(n+1)
したがって、
n+1が偶数なら、m-1は11の倍数なら、a10^n-1は11の倍数。
n+1が3の倍数なら、m-1は3か37の倍数なら、a10^n-1は3か37の倍数。
n+1が5の倍数なら、m-1は41か271の倍数なら、a10^n-1は41か271の倍数。
以下省略
２．a=10m+1 (mは自然数） とすると、a10^n-1=(10m+1)10^n-1=m10^(n+1)+10^n-1
ここで、10^n-1=99・・99=(11・・11)x9
11・・11を考えると、1がn個並んだ数なので、nが合成数なら、かならず割れる。
n=6=2x3 なので、
111111=11x(10101)=111x(1001)=11x3x7x13x37=(111)x(1001)=(3x37)x(7x11x13)
これより、nが偶数なら、11の倍数。
nが3の倍数なら、111(=3x37)の倍数。
nが5の倍数なら、11111(=41x271)の倍数。
nが7の倍数なら、1111111(=239x4649)の倍数。
nが11の倍数なら、11111111111(=21649x513239)の倍数。
nが13の倍数なら、1111111111111(=53x79x265371653)の倍数。
以下省略
また、m10^(n+1)は、mx2^(n+1)x5^(n+1)
したがって、
nが偶数なら、mは11の倍数なら、a10^n-1は11の倍数。
nが3の倍数なら、mは3か37の倍数なら、a10^n-1は3か37の倍数。
nが5の倍数なら、mは41か271の倍数なら、a10^n-1は41か271の倍数。
以下省略
３．a=10m+2 (mは自然数） とすると、a10^n-1=(10m+2)10^n-1=(m+1)10^(n+1)+10^n-1
ここで、10^n-1=99・・99=(11・・11)x9
11・・11を考えると、1がn個並んだ数なので、nが合成数なら、かならず割れる。
n=6=2x3なので、
111111=11x(10101)=111x(1001)=11x3x7x13x37=(111)x(1001)=(3x37)x(7x11x13)
これより、nが偶数なら、11の倍数。
nが3の倍数なら、111(=3x37)の倍数。
nが5の倍数なら、11111(=41x271)の倍数。
nが7の倍数なら、1111111(=239x4649)の倍数。
nが11の倍数なら、11111111111(=21649x513239)の倍数。
nが13の倍数なら、1111111111111(=53x79x265371653)の倍数。
以下省略
また、(m+1)10^(n+1)は、(m+1)x2^(n+1)x5^(n+1)
したがって、
nが偶数なら、(m+1)は11の倍数なら、a10^n-1は11の倍数。
nが3の倍数なら、(m+1)mは3か37の倍数なら、a10^n-1は3か37の倍数。
nが5の倍数なら、(m+1)mは41か271の倍数なら、a10^n-1は41か271の倍数。
以下省略
うんざりはちべえさんからのコメントです。（令和５年５月１６日付け）
４．a=10m+r (mは自然数、rは3,4,5,6,7,8,9のいずれか） とすると、
a10^n-1=(10m+r)10^n-1=(m+r-1)10^(n+1)+10^n-1
ここで、10^n-1=99・・99=(11・・11)x9
11・・11を考えると、1がn個並んだ数なので、nが合成数なら、かならず割れる。
n=6=2x3 なので、
111111=11x(10101)=111x(1001)=11x3x7x13x37=(111)x(1001)=(3x37)x(7x11x13)
これより、nが偶数なら、11の倍数。
nが3の倍数なら、111(=3x37)の倍数。
nが5の倍数なら、11111(=41x271)の倍数。
nが7の倍数なら、1111111(=239x4649)の倍数。
nが11の倍数なら、11111111111(=21649x513239)の倍数。
nが13の倍数なら、1111111111111(=53x79x265371653)の倍数。
以下省略
また、(m+r-1)10^(n+1)は、(m+r-1)x2^(n+1)x5^(n+1)
したがって、
nが偶数なら、(m+r-1)は11の倍数なら、a10^n-1は11の倍数。
nが3の倍数なら、(m+r-1)mは3か37の倍数なら、a10^n-1は3か37の倍数。
nが5の倍数なら、(m+r-1)mは41か271の倍数なら、a10^n-1は41か271の倍数。
以下省略
５．a=10m+s (mは自然数、sは1,2,3,4,5,6,7,8,9のいずれか） とすると、
a10^n-1=(10m+s)10^n-1=(m+s-1)10^(n+1)+10^n-1
ここで、10^n-1=99・・99=(11・・11)x9 より、10^n-1は、３の倍数。
また、(m+s-1)10^(n+1)は、(m+s-1)x2^(n+1)x5^(n+1) より、m+s-1が３の倍数なら、
a10^n-1は、３の倍数。
６．a=10m (mは自然数） とすると、a10^n-1=(10m)10^n-1=(m-1)10^(n+1)+10^(n+1)-1
ここで、10^(n+1)-1=99・・99=(11・・11)x9 より、10^(n+1)-1は、３の倍数。
また、(m-1)10^(n+1) は、(m-1)x2^(n+1)x5^(n+1) より、m-1が３の倍数なら、a10^n-1は、
３の倍数。
うんざりはちべえさんからのコメントです。（令和５年５月１７日付け）
間違っておりました。よくよく考えると、これでいいと思います。
a10^n-1=(a-1)10^n+10^n-1
ここで、10^n-1=99・・99=(11・・11)x9
11・・11を考えると、1がn個並んだ数なので、nが合成数なら、かならず割れる。
n=6=2x3 なので、
111111=11x(10101)=111x(1001)=11x3x7x13x37=(111)x(1001)=(3x37)x(7x11x13)
これより、nが偶数なら、11の倍数。
nが3の倍数なら、111(=3x37)の倍数。
nが5の倍数なら、11111(=41x271)の倍数。
nが7の倍数なら、1111111(=239x4649)の倍数。
nが11の倍数なら、11111111111(=21649x513239)の倍数。
nが13の倍数なら、1111111111111(=53x79x265371653)の倍数。
以下省略
また、(a-1)10^nは、(a-1)x2^nx5^n
したがって、
nが偶数なら、(a-1)は11の倍数なら、a10^n-1は11の倍数。
nが3の倍数なら、(a-1)は3か37の倍数なら、a10^n-1は3か37の倍数。
nが5の倍数なら、(a-1)は41か271の倍数なら、a10^n-1は41か271の倍数。
以下省略
また、a-1が３の倍数なら、a10^n-1は、３の倍数。
特に、a-1が9の倍数なら、a10^n-1は、9で割れて、{(a-1)/9}x10^n+(11・・11)となる。
うんざりはちべえさんからのコメントです。（令和５年５月１８日付け）
昨日はとんちんかんなことを書いてしまいました。毎度のことですみません。根本的に、間
違いでした。（→ 参考）
ＧＡＩ さんからのコメントです。（令和５年５月１６日付け）
「A069568」によりますと、「56」の後に1が18470個も続くようです。
Dengan kesaktian Indukmu さんからのコメントです。（令和５年５月１６日付け）
わあっ！！「A069568」にはちゃんと 38111…111 について も 触れてあるのですね！！
見落とし、恥ずかしいです。
私は、「模範解答」をみていて、意味がわからずに難儀していたのでした。
「3乗マイナス3乗」だと気がつくことで個人的には納得したのですが、いまだにこの模範解
答の筋立ての意味をつかみかねています。
DD++ さんからのコメントです。（令和５年５月１４日付け）
以前あった 381111…… の話かと思ったら、今回は 371111…… なのですね。（→ 参考）
Dengan kesaktian Indukmu さんからのコメントです。（令和５年５月１４日付け）
381…1 は個人的は未解決だったのでした。これは、(343*10^n -1)/9 ですが
（1）n ≡ 0 (mod 3) のときには、n = 3*k とおいて、343 = 7^3 に留意すると、
((7*10^k)^3 -1^3)/9 ですから、分子は、（3乗－3乗）の形となり因数分解できることから、
合成数でありそうです。
（２）n ≡ 1 (mod 3) のときには、381、381111、381111111、… などですから、３の倍数です。
（３）n ≡ 2 (mod 3) のときには、どうしたものでしょうか？
3811、3811111、3811111111、・・・ ですが、3811 は 37 の倍数、111 は 37 の倍数ですね。
DD++ さんからのコメントです。（令和５年５月１６日付け）
Dengan kesaktian Indukmu さん、まさしく上記で述べられている通りの記述に見えますが、
疑問点はどこなのでしょう？
Dengan kesaktian Indukmu さんからのコメントです。（令和５年５月１６日付け）
DD++ さん、ご指摘をありがとうございました。仰る通りです。慎重に読み直したところ、私
の誤読とわかりました。正しくは「模範解答」にありますとおり、
If n = 3*k ≡ 0 (mod 3), observe that
9*a*(3*k) = 34299 ・ ・ ・ 99
= (7*10^k)^3 - 1
which is properly divisible by 7*10^k - 1,
a number that is larger than 9.
Hence a(3k) admits a non-trivial factor and so is not prime.
なのですが、私はとんでもない読み間違いをしておりました。すなわち、
If n = 3*k ≡ 0 (mod 3), observe that
9*a*(3*k) = 34299 ・ ・ ・ 99
= (7*10^k)^3 - 1
which is properly divisible by (7*10^k)^3 - 1,
a number that is larger than 9.
Hence a(3k) admits a non-trivial factor and so is not prime.
こんな読み方をしていてはダメダメに決まっています。[ 「模範解答」を読みながらノートに
写経したときの転記ミスが最初のきっかけです。いったん思い込むと沼にはまる悪い癖が今
回も発生しましました。]
DD++ さん、ご教示をありがとうございました。また、みなさまにつきましては私からのわけ
の分からない投稿で御迷惑をおかけしましたこと、お詫び申し上げます。
らすかるさんの
「A112386」は、なぜこんなにちょっとしかデータがないんでしょうかね。
1331, 13311, 133111, 1331..1 がヤバそうです。
これは、(1198*10^n -1)/9 ですが、任意の正の整数 n について、合成数のような！？
なかなか素数がみつからず、さりとてなぜ合成数になるのか、見通しもつけられず．．．。
ＧＡＩ さんからのコメントです。（令和５年５月１８日付け）
面白素数を探すテーマで、ある数 a の後に 1 が連続して続くものが話題に挙がっていた
ので、では、数 a の後に、3、7、9 が続くタイプについて調べて貰います。
(1) a を 3 では割れない100までの整数とし、その後に連続して 3 を並べて行くとき、初めて
素数になるものを探す。
a3
a33
a333
a3333
･････
このとき、最も 3 が並ぶ a は何？
(2) ｂ を 7 では割れない100までの整数とし、その後に連続して 7 を並べて行くとき、初めて
素数になるものを探す。
b7
b77
b777
b7777
･････
このとき、最も 7 が並ぶ b は何？
(3) c を 3 では割れない100までの整数とし、その後に連続して 9 を並べて行くとき、初めて
素数になるものを探す。
c9
c99
c999
c9999
･････
このとき、最も 9 が並ぶ c は何？
らすかるさんからのコメントです。（令和５年５月１８日付け）
(1) a=40 (3が483個)
(2) b=95 (7が2904個)
(3) c=97 (9が90個)
#(2)はちょっと時間がかかりました。
ＧＡＩ さんからのコメントです。（令和５年５月１８日付け）
明らかに、「A112394」や「A113076」でのデータは不足していますね。
(2) b の次にいくつまで 7 を並べるといいのかは、自分のプログラムとスペックでは手に
入れることはできませんでした。可能な限り、らすかるさんに補充してもらえると有難いです。
らすかるさんからのコメントです。（令和５年９月２７日付け）
可能な限り、らすかるさんに補充してもらえると有難いです。
「7」だけですが、「可能な限り」調べましたので、長期間かかってしまいました。
（実際はずいぶん前にアップしていたのですが、なかなか登録されませんでした。）
「A113076」は、b-file(LINKSにある、数を羅列したファイル)の桁数制限(最大1000桁)で、
a(94)までしか追加できませんでしたが、「A090464」(追加桁数≧0)のb-fileは、a(4443)まで拡
充し、また、「A363922」(追加桁数＞0)のページを新規追加しました。
a(4444)が300000を超えることが判明して、これ以上はあまりにも時間がかかりますので、
4443までで終了としました。実際は未解決の9個を除き、10000まで調査済みです。
判明している最大桁数は、a(2174)の94146桁（2174を合わせて94150桁）です。
この後、「1」「3」「9」を順次調査して更新・追加する予定ですが、数ヶ月かかる(かける)と思
います。
ＧＡＩ さんからのコメントです。（令和５年９月３０日付け）
2038の後に76206個の、2174の後に94146個の7が連続して続いている整数が素数だなん
て「おったまげ～」です。
こんな判定ができるのは世界広しといえども、らすかるさんの根性と技術力が無ければ誰
も見つけられません。
これらを見つける(最初が4443までと、4444なら300000以上が判明する。)のに、どれほど
の時間が費やされたのか、想像するだけで恐れ入ります。
何気なくお願いしていたことに、ここまでの結果を出されていることに驚きと感謝しかありま
せん。お疲れ様でした。
らすかるさんからのコメントです。（令和５年９月３０日付け）
これを計算するにあたって、
・多倍長整数演算ライブラリを新規に作成（今までは多倍長浮動小数点ライブラリしかなかっ
たので整数専用を作り高速化）
・今までの多倍長乗算では面倒で導入していなかったFFT（高速フーリエ変換）を組み込み
（1万桁程度までなら不要）
・1千万以下の素数で割り切れるものは予め除外して、多倍長演算そのものを極力削減（mod
値を順次更新していくだけなので、実際に素数で割る必要はありません）
のように高速化しましたが、それだけでは限界がありますので、さらに、
・今回これの計算のために新規に計算専用のPCを３台購入（計算のためだけにPCを買った
のは初めてです）
・各PCでプログラムを10個ずつ走らせて並列処理（計30個; 最近のCPUはマルチコアなので
10個程度までは速度を落とさずに実行できます。ただし結構個体差あり）
ここまでやって、a(4444)＞300000が判明するまでの時間は約40日でした（もちろん4444だ
けで）。100000ぐらいまでなら確か1日程度なので、1～4443ではそこまで長くはかかっていま
せん。
現在は、603111111…111について探索していますが、もし300000までに見つからなければ
来月中旬頃には、「1」関連のページが更新できると思います。
（もし見つかった場合は、次に不明な1244111111…111の計算になりますので、もっと長くか
かります。）「3」と「9」は今のところ手つかずです。
うんざりはちべえさんからのコメントです。（令和５年５月１９日付け）
それでは、
1234567890123456789012345678901・・・8901
1234567890123456789012345678901・・・567
はどうなんでしょう？素数にはならないのでしょうか？ただし、
1234567890123456789012345678901・・・890123は、3の倍数
1234567890123456789012345678901・・・012345は、5の倍数
1234567890123456789012345678901・・・456789は、3の倍数
です。
(%i32) factor(12345678901234567890123456789012345678901234567890123456789
012345678901234567);
(%o32) 7 8447 15511
13460916961858847299449477233189774374173209263392110114539531835993
と結構大きな素数が見つかりました。
πは、何億桁も求められていると思います。その一部分を切り出したら、長大な素数にな
るのではないでしょうか？また、
、
も同じくその一部を切り出したら、長大な素数になるのではないでしょうか？
小数点を頭とし、頭から、いくつか行ったところから始めてそこから、何千桁の素数になる
とかという発見も可能ではないでしょうか？
そういう話は、ないのでしょうか？
ＧＡＩ さんからのコメントです。（令和５年５月２０日付け）
あります。（→ 参考：「A005042」）
3、31、314159、31415926535897932384626433832795028841、・・・
これ以上は、「A060421」を参照のこと
なお、
==>「A115377」 、==>「A119344」何でも調査済みです。
うんざりはちべえさんからのコメントです。（令和５年５月２０日付け）
ＧＡＩ さん、ありがとうございます。調査中ですか。
そこで、こんなくだらないことを考えました。
πの何億桁を暗号文として見れば、何語かしれませんが、ある文章が発見されるかもしれ
ませんね。また、πの何億桁をさがすと、小数点を除いた何桁かのπとか、小数点を除いた
何桁かの
とかが見つかるかもしれませんね。あるいは、πの何億桁をさがすと、ほとんどの素数が含まれているかもしれませんね。すると、あなた方は、素数を発生する式を見
つけようと奮闘されていると思いますが、それは、πの何桁目にあるという関数なのかもしれ
ませんね。あるいは
かもしれません。らすかるさんからのコメントです。（令和５年５月１７日付け）
おそらく (1198*10^2890-1)/9 （133の後に1が2890個） が素数だと思います。しかし、
GAIさんが書かれた「A069568」に、118までのデータが載っていますので、「A112386」は、
「56」で巨大な数になることを考えても、せめて「55」までは載っていてもいいのに、とは思い
ます。
「(1198*10^2890-1)/9は多分素数」の理由
ミラーラビン素数判定法で15000以下の素数1754個をそれぞれ底にしてテストしたところ、
すべてパスしましたので、「合成数である確率」は、1/10^1000未満となります。
うんざりはちべえさんからのコメントです。（令和５年５月１７日付け）
私も合成数でないと思います。（→ 参考）
Ｈ．Nakao さんからのコメントです。（令和５年６月１日付け）
らすかるさんのコメント：
おそらく (1198*10^2890-1)/9 （133の後に1が2890個） が素数だと思います。
について、らすかるさんの予想通り、2893桁の整数 (1198*10^2890-1)/9が素数であること
を、Pari/GPのECPPによって確認できました。
[Pari/GPによる計算結果]
gp > a=(1198*10^2890-1)/9;
gp > log(a)/log(10)
%2 = 2892.1242143086139677004518556573160092
gp > isprime(a,3)
time = 3h, 33min, 36,267 ms.
%3 = 1
gp > a
%4 =
13311111111111111111111111・・・・・・・・（途中省略）・・・・・・・・111111111111111111111111
Dengan kesaktian Indukmu さんからのコメントです。（令和５年５月２０日付け）
らすかるさん、検証をありがとうございました。確率的素数ということですね。
一点、質問をさせていただきたく思います。
ミラーラビンの底には素数をとるのが良いのでしょうか？
確率の評価に影響をあたえますか？
らすかるさんからのコメントです。（令和５年５月２０日付け）
影響は大いにあると思います。例えば、2で確率的素数と判定されたら、4や8でも（多分）
確率的素数と判定されますが、確率が上がるわけではないですね。
同様に、2と3で確率的素数となれば、6でも（多分）確率的素数と判定されると思います。
「多分」としているのは場合によるかも知れないからですが、影響する可能性があるのは
間違いないですから、同じ素因数を持つ数は避けた方が良いかと思います。
DD++ さんからのコメントです。（令和５年５月２１日付け）
同様に、2と3で確率的素数となれば、6でも（多分）確率的素数と判定されると思います。
私はこれはなんとなく偽ではないかと思います。反例はまだ見つけられていませんが．．．。
らすかるさんからのコメントです。（令和５年５月２１日付け）
2と3で確率的素数となれば、6でも（多分）確率的素数
例えば、nが素数で、n-1=16m（mは奇数）だとすると、mod nで
(a^m,a^(2m),a^(4m),a^(8m),a^(16m))
≡(1,1,1,1,1)、(-1,1,1,1,1)、(A,-1,1,1,1)、(B,C,-1,1,1)、(D,E,F,-1,1)
(A,B,C,D,E,Fは-1,0,1以外の数)
のいずれかになるわけですが、a=2で、(A,-1,1,1,1) 、a=3で、(D,E,F,-1,1) のようになったと
すると、a=6では、(A*D,-E,F,-1,1) （A*Dも-EもFも-1,0,1以外） のようになり、やはり確率的
素数と判定されます。
問題は、底2で (A,B,C,-1,1) 、底3で (D,E,F,-1,1) のように同じタイミングで-1になった場合
で、このような場合は、C*F≡-1になるとは限りませんので、底6で確率的素数と判定される
かどうかわかりません。
（これの反例があるのかどうかもわかりません。ありそうな気はしますが）
というわけで、少なくとも-1になるタイミングが異なる素因数の積を底にした判定は確率の
向上になりませんので、同じ素因数は避けた方がいい、ということを言いたかったのです。
DD++ さんからのコメントです。（令和５年５月２１日付け）
少なくとも-1になるタイミングが異なる素因数の積を底にした判定は確率の向上になりま
せんので、同じ素因数は避けた方がいい
これ、実は少し考えなければいけないところではないかと思います。
例えば、13 をミラーラビンテストにかけるとします。このとき、a = 3, 7, 11 という 3 つの素数
で判定を行うことは有効でしょうか？
普通の自然数の世界では、7 は素数です。しかし、13 をミラーラビンテストにかける場合、
行う計算は全て mod 13 の世界です。
その世界では、3*11=7 ですから、7 はらすかるさんが仰るところの避けた方がいい数に該
当します。
こう考えてみると、確率向上に貢献する a と貢献しない a の判別は「通常の自然数の世界
で合成数だから」という単純な話ではない気がしています。
Dengan kesaktian Indukmu さんからのコメントです。（令和５年５月２４日付け）
「ミラーラビンの底には素数をとるのが良いのでしょうか？ 確率の評価に影響をあたえま
すか？」という私の疑問にお答えくださってありがとうございます。
私のほうでも調べてみたことがあります。
Miller-Rabin 素数判定法は確率的に素数らしい数かどうかを判定するのに有用ですが、底
のとりかたによっては、限定的な範囲内にて、確率100％で判定できる場合があります。注目
点としては、この底の取り方です。
① a = {2, 3, 5, 7, 11, 13, 17} を試せば、341550071728321 以下の素数判定を確率100％で
できる。
② a = {2, 3, 5, 7, 11, 13, 17, 19, 23} を試せば、3825123056546413051 以下の素数判定を
確率100%でできる
上記の①、②では、底として素数のみの組を使っています。
なお、①、②はOEISの「A014233」 によります。
一定の範囲の数について、素数判定を確率100%で判定するには、底としては素数の組を
使うのがよいのかと思ったところですが、一方において、これに反するような、次のようなサ
イトがありました。（→ 「Deterministic variants of the Miller-Rabin primality test」）
このサイトによれば、7つの底を使って、2^64 までの数を確定的に素数判定できる底の例
として、 2、325、9375、28178、450775、9780504、1795265022 が挙げられています。
偶数とか、5の倍数とかが底になっていて唖然としました。悩みは続きます。
ＧＡＩ さんからのコメントです。（令和５年５月２３日付け）
ミラー・ラビン法のStorong pseudoprimeの発見において、底を 2、3、6 の３つで調査すれば
1～10^8までには、次の21個が発見でき、
1373653;[829, 1; 1657, 1]
1530787;[619, 1; 2473, 1]
1987021;[997, 1; 1993, 1]
2284453;[1069, 1; 2137, 1]
3116107;[883, 1; 3529, 1]
5173601;[929, 1; 5569, 1]
6787327;[1303, 1; 5209, 1]
11541307;[1699, 1; 6793, 1]
13694761;[2617, 1; 5233, 1]
15978007;[1999, 1; 7993, 1]
16070429;[1637, 1; 9817, 1]
16879501;[1453, 1; 11617, 1]
25326001;[2251, 1; 11251, 1]
27509653;[3709, 1; 7417, 1]
27664033;[3037, 1; 9109, 1]
28527049;[2389, 1; 11941, 1]
54029741;[1733, 1; 31177, 1]
61832377;[3517, 1; 17581, 1]
66096253;[5749, 1; 11497, 1]
74927161;[6121, 1; 12241, 1]
80375707;[4483, 1; 17929, 1]
同じく底を 2、3、7 で調査すると、次の1個が
2284453;[1069, 1; 2137, 1]
また、底を 2、3、11 でも、2284453 が発見される。
底を 2、3、13 なら、6787327;[1301,1;5209,1] が出現
ところで、P=p+k*(k+1)/2 と構成できなかったタイプ(2を含めて)、2、7、61を底にして調査
すれば、一つも擬素数は存在しないことが判明する。
ウィキペディアのミラー-ラビン素数判定法の記事によれば、
もし、n<4759123141 なら、底を 2、7、61 について調べればよい
とある。n=10^8～10^10では、4759123141;[48781, 1; 97561, 1] が出現してしまう。
これと何かしら関係しているかもと思われました。
以前、56の後に、1が18470個並ぶ莫大な数 n=(505*10^18470-1)/9 が素数であることを
らすかるさんがミラー・ラビンの素数判定法を使って、ほとんど素数であることは確かである
と示されていた。
そこで、この確率的底 a の選び方を a が、「奇素数の抜け穴(3、7、61、211）」を 2 と共に
指定して使えば、それでも素数の判定は可能であると思われた。
そこでWikipedia "ミラー・ラビン素数判定法"内のRubyによるコード：
class Integer
def prime?
n = self.abs()
return true if n == 2
return false if n == 1 || n & 1 == 0
d = n-1
d >>= 1 while d & 1 == 0
20.times do
a = rand(n-2) + 1
t = d
y = ModMath.pow(a,t,n)
while t != n-1 && y != 1 && y != n-1
y = (y * y) % n
t <<= 1
end
return false if y != n-1 && t & 1 == 0
end
return true
end
end
module ModMath
def ModMath.pow(base, power, mod)
result = 1
while power > 0
result = (result * base) % mod if power & 1 == 1
base = (base * base) % mod
power >>= 1;
end
result
end
end
において、20回繰り返す a の取り方(ランダムに選ばせる）
20.times do
a = rand(n-2) + 1
を base=[2,7,61,211]
base.each do |a|
へ変更してプログラムを走らせてみました。
元のままのものでは20分ほどで、
irb(main):033:0> n=(505*10**18470-1)/9;irb(main):034:0* n.prime?=> true
を返すが、変更したプログラムでは、3分ほどで同じく正しく判定してくれました。
Dengan kesaktian Indukmu さんからのコメントです。（令和５年５月２４日付け）
2、7、61 の三組の底では、4759123141 までの数について、確定的に素数判定ができると
のことです。このミツグミは優秀なんですね……。
このことは、「Deterministic variants of the Miller-Rabin primality test」をみてたら気がつ
いたことです。
ＧＡＩ さんからのコメントです。（令和５年５月２５日付け）
ええ、そうなんですよ。だから、もう一つ追加して、[2,7,61,211] の４つの素数を底に指定し
て、全部の底でミラー・ラビン方式(もはや確率的ではないのでこの名は使えないか？）が
クリアーできれば、莫大な奇数nでも合成数か素数かが正しく判定できるような気がしてい
るんですが、その限界も数値的確認もしてないので、何とももどかしい所なんですが･･･。
Dengan kesaktian Indukmu さんからのコメントです。（令和５年５月２５日付け）
確か、有限個の底の組では、確率100%のミラーラビン判定ができないことが、既に証明さ
れていると思います。昔、調べたことがあるのですが、そのことが書いてあるサイトが消失し
ていました。残念………、どこか探せばあるはずですが……。
ＧＡＩ さんからのコメントです。（令和５年５月２５日付け）
もちろん素数はそれこそ無限個あるので、全部の奇数に対して、合成数か素数かを有限
個の調査で調べ尽くすことは不可能であろうことは想像できますが、ある有限の範囲以内
においては、そのような判定ができる組合わせはあってもいいと思われますし、また、確か
にいろいろな調査で存在しています。この組[2,7,61,211]がどこまでの範囲で大丈夫なのか
は自分もわからないのですが、感じとしては相当莫大な有限の範囲を保証できるのではな
いかという意味です。
Dengan kesaktian Indukmu さんからのコメントです。（令和５年５月２５日付け）
GAIさん、了解いたしました。
以下のNは、ミラーラビン法により、200未満の全ての素数を底にして検査した結果として
強擬素数と判定されたものです。変なところに改行がはいっていて申し訳ありませんが、コ
ピペミスを怖れた次第です。
N=
8038374574536394912570796143419421081388376882875581458374889175222974273765
3336521865023361639600454579150420236032087665699667609872840439654082329287
3879185086916685732826776177102938969773947016708230428687109997439976544144
8453411558724506334092790222752962294149842306881685404326457534018329786111
298960644845216191652872597534901
底を 211 で検査すると、ようやく合成数と判定できるようです。Nはかなり大きな数ですね。
「Large examples of strong pseudoprimes to several bases」を参考にいたしました。
ＧＡＩ さんからのコメントです。（令和５年５月２７日付け）
上記のNが合成数であることを見るために、素因数分解を見つけようと試みているんです
が、未だに発見できないでいます。
色々な方法の素因数分解でのアルゴリズムがあるようなので、この方面に精通されてい
る方で、上記を試みるとどんな因数を持っているか分かる方、お教え願います。
Dengan kesaktian Indukmu さんからのコメントです。（令和５年５月２７日付け）
GAI さん、次のふたつの素数の積なのだそうです。
200479108319749802709153226042273426502594083020566254387253102369001608535
059812135811159579860986679108158254267908348457261690695858464376399022289
8400226296015918301
400958216639499605418306452084546853005188166041132508774506204738003217070
119624271622319159721973358216316508535816696914523381391716928752798044579
6800452592031836601
（恥ずかしながら…汗…）検算はしておりません。いつもの知人に問い合わせたら、調べてく
れて、結果を教わりました。
DD++ さんからのコメントです。（令和５年５月２７日付け）
この２つの数は k と 2k-1 という関係にあるように見えます（目視確認）。
ミラーラビンテストって、実は、 k(2k-1) という形の半素数と相性が悪かったりするんでしょう
か？
ＧＡＩ さんからのコメントです。（令和５年５月２７日付け）
以前投稿していたデータを使うと、ミラー・ラビン法のStrong pseudoprimeの発見において
底を2,3,6の３つで[全部の底を満たす]調査すれば、1～10^8 までには次の21個が発見でき
1373653;[829, 1; 1657, 1]=>p*(2*p-1)
1530787;[619, 1; 2473, 1]=>p*(4*p-3)
1987021;[997, 1; 1993, 1]=>p*(2*p-1)
2284453;[1069, 1; 2137, 1]=>p*(2*p-1)
3116107;[883, 1; 3529, 1]=>p*(4*p-3)
5173601;[929, 1; 5569, 1]=>p*(6*p-5)
6787327;[1303, 1; 5209, 1]=>p*(4*p-3)
11541307;[1699, 1; 6793, 1]=>p*(4*p-3)
13694761;[2617, 1; 5233, 1]=>p*(2*p-1)
15978007;[1999, 1; 7993, 1]=>p*(4*p-3)
16070429;[1637, 1; 9817, 1]=>p*(6*p-5)
16879501;[1453, 1; 11617, 1]=>p*(8*p-7)
25326001;[2251, 1; 11251, 1]=>p*(5*p-4)
27509653;[3709, 1; 7417, 1]=>p*(2*p-1)
27664033;[3037, 1; 9109, 1]=>p*(3*p-2)
28527049;[2389, 1; 11941, 1]=>p*(5*p-4)
54029741;[1733, 1; 31177, 1]=>p*(18*p-17)
61832377;[3517, 1; 17581, 1]=>p*(5*p-4)
66096253;[5749, 1; 11497, 1]=>p*(2*p-1)
74927161;[6121, 1; 12241, 1]=>p*(2*p-1)
80375707;[4483, 1; 17929, 1]=>p*(4*p-3)
の型で起こっている様です。
Dengan kesaktian Indukmu さんからのコメントです。（令和５年５月２７日付け）
このリストは、底として、2 およびに 3 だけを取ったときのものと同じになるようですね………
それはそうと、「p*(t*p-t+1)」の形になっているのですね。
Dengan kesaktian Indukmu さんからのコメントです。（令和５年５月２８日付け）
DD++ さんから、ミラーラビン法は今話題にしている形での半素数に弱いのかというテーマ
が挙げられています。必ずしも半素数にはならないようでしたので、以下にメモをあげます。
3215031751 は、2、3 をともに底としたときに強擬素数です。この数は、28351 * 113401 に
等しく、また、113401 = 28351 * 4 -3 となっています。私達がいま興味をもっていた形ですね。
さて、113401 = 151*751 と素因数分解可能です。このことから、3215031751 は半素数で
はありません。
DD++ さんからのコメントです。（令和５年５月２８日付け）
個人的には、半素数であるかどうかよりも、k と 2k-1 という値の大きさの関係を気にしてい
ました。その後、
・どうやら k+1 と 2k+1 という形に書いた方がよいこと
・2k+1 だけでなく mk+1 という形であれば m=2 という形かどうかはあまり重要でなさそうなこと
が見えてきていますね。
751 と 151 も、151 = 150 + 1 、751 = 5*150 + 1 ですから、同様の性質は持っていると
言ってよさそうに思います。
Dengan kesaktian Indukmu さんからのコメントです。（令和５年５月３０日付け）
2 と 3 とをともに含む複数の底でミラー・ラビン判定を行い、結果が強擬素数であったとしま
す。この強擬素数が素数であるのか合成数であるかについてを更に調べたいと思ったとしま
す。
この強擬素数を S とします。
まだ未証明ですが、次のような予想が成り立つとしましょう。すなわち、
S が合成数であるならば、自然数 k と m とがあって、S = (k +1)*(m*k +1) …① となる。
S が素数であるか合成数であるかを知りたいときに ① をあてにしてよいとするならば、単
に、√S までの素数を列挙して、S をそれらで割ってみる素因数分解方法よりも速く素因数
分解の結果が得られることがあるのでしょうか？
GAI さんによる 10^8 までの強擬素数の素因数分解のリストを見るかぎり、どうやら m は
かなり小さめです。m について小さい順に調べると良いのではと思います。
①を、k についての２次方程式とみて、判別式が平方数になるかどうか検査するとよいの
ではないかと山勘を働かせてみました。
さて、この方法は、本当に速く処理できるものなのでしょうか？
DD++ さんからのコメントです。（令和５年５月３０日付け）
素因数分解できるまでの「平均時間」は圧倒的に速いと思います。素因数分解ができるま
での「最悪の時間」はむしろ悪化すると思いますが．．．。つまり、最悪試さなきゃいけない候
補の数は増えますが、当たりになる可能性が高いところだけを最初にピックアップして試せる
感じになります。たぶん。
Dengan kesaktian Indukmu さんからのコメントです。（令和５年５月３０日付け）
DD++さん、御意見をありがとうございました。私の心象もそれに近いものがあります。
ここまでちょっと話を飛ばしすぎたきらいがありますので、以下では小まとめを。あとでログ
を見返したときにわかりやすいようにです。
2 およびに 3 を含む複数の底を使ってミラー・ラビン判定法を行います。その結果として合
成数として判定されなかったものは強擬素数ですが、依然として合成数である確率がわずか
ながら残っています。今回はこの数を S と書くことにします。
観察によれば、S が合成数であるならば、m k を自然数として、S = (k +1)*(m*k +1) とな
ることが期待されます。
なお、(k +1)、(m*k +1) については、素数であることを要請しません、念のため。
こうした m k を簡便に求められれば、強擬素数 S が合成数であることの判定が簡便にで
きることとなります。 m k がみつけられなかったとしても、それは、合成数であることをこの手
法では証明できなかっただけのことなので、強擬素数 S が素数であるとは限りません。
具体例をあげます。S = 16697267137953148781 とします。
なお、この S は、底として、2, 3, 5, 7 を使ったミラー・ラビン法で強擬素数となるものです。
S = (k +1)*(m*k +1) となる m k をみつけるために、k についての２次方程式とみたてて
これを解くことを考えます。すなわち、m*k^2 +(m +1)*k +(1 -S) = 0
D = (m +1)^2 -4*m*(1 -S) とおくと、この２次方程式の正の解は、
k = (-(m +1) +√D)/(2*m) となります。k が負の解は捨てます。
k が自然数であるための必要条件のひとつは、D が平方数であることです。本当は、
(2*m)で割っていますから、十分条件にはなっていません。
あとで確かめることにします。★★★
D = (m +1)^2 -4*m*(1 -S) なのでしたが、これが平方数になるような m がうまく見つかる
とありがたいわけです。これまでの観察によれば、m はさほど大きな数にはならないようで
すので、m について、1 からはじめて順次カウントアップして探すこととします。
実際にやってみると、(プログラムが組めないので電卓でしました) m = 6 で D が平方数と
なりました。このときの D は、D = 400734411310875570769 = 20018351863^2 です。早くみ
つかってラッキー。この m をもとの２次方程式にほうりこんでやると、
k = (-7 +√D)/(12)= (20018351863 -7)/12 となります。
ちゃんと 12 で割り切れればよいのですが……前に★★★で留意点としてあげていたことが
ここで確認されます。実際に計算してみると、k = 1668195988 となります。★★★はクリアさ
れました。
m = 6 でしたから、S は、S = (1668195988 +1)*(6*1668195988 +1) となります。
検算すると、確かに、S = 16697267137953148781 となり、S は合成数と判定されました。
以上のように、比較的に簡便に合成数判定ができるケースが多くみられるのではないか
との予想をたててみています。ミラー・ラビン判定法の補助手段として利用できたら嬉しい
です。
言い忘れました。16697267137953148781 は、底を 6 とすると合成数と判定されるそうです。
2 でも 3 でも強擬素数なのに。
DD++ さんからのコメントです。（令和５年５月３１日付け）
k が負の整数の場合、狙っていた形とは合致しませんが S の因数分解には成功します。
ですから、排除する必要はないのではないかと思います。
また、k が整数にならない場合の心配ですが、仮にそうなっても 4mS を 2 つの因数にわけ
ることは成功します。
m が S よりずっと小さい場合は、その場合でも（目的の式の形にはなりませんが）S の因
数分解には成功するんじゃないかと思うのですが、どうなのでしょう。
Dengan kesaktian Indukmu さんからのコメントです。（令和５年６月１日付け）
アドバイスを有難うございます。
D = (m +1)^2 -4*m*(1 -S) としていましたが、これを整理すると、D = (m -1)^2 +4*m*S
この D が、ある自然数 T の２乗になっていると、開平が出来て嬉しいのでした。
こうした T がみつかったときには、(m -1)^2 +4*m*S = T^2 となり、これを変形すれば、
4*m*S = T^2 -(m -1)^2 = (T +(m -1))*(T -(m -1))
となります。仰るとおりに、《4mS を 2 つの因数にわけることは成功します。》とわかりました。
実用の範囲内で m が十分に小さいことがわかれば、k を求めることを行わなくても、S の
合成数判定ができるのですね、おどろきです。
k が負の整数の場合、狙っていた形とは合致しませんが S の因数分解には成功します。
ですから、排除する必要はないのではないかと思います。
これ、意味をつかめませんでした。よろしければご教示を賜りたくお願いいたします。
観察によれば、S が合成数であるならば、m k を自然数として、S = (k +1)*(m*k +1) とな
ることが期待されます。
反例をようやくみつけました。
S = 196161196117261 は、底を 2, 3 としたミラー・ラビン判定法で強擬素数ですが、
S = 6602377*29710693 という半素数で、k = 6602376 、m = 29710692/6602376 = 9/2
となっています。
DD++ さんからのコメントです。（令和５年６月２日付け）
k が負の整数だと、S = (-101)*(-103) みたいな形になるので、自然数の積にはなりません。
でも、これを見て自然数の積に書き直すのは容易ですよね、という話です。
反例をようやくみつけました。
薄々そんな予感はしていましたが、やっぱり (mk+1)*(nk+1) の形も出てきましたか。まあ、
m も n も小さいという条件でなら、該当する数を探す労力はそんなに変わらないと思います
が。
ＧＡＩ さんからのコメントです。（令和５年６月２日付け）
その数S以前には、190131062354461 、190847302523971 、191212468762741 、･･･
その数以降も、
197201702068963 、197867738963563 、198675496474963 、198888784469461 、
200262009366409 、200271411485473 、200669198495977 、201324851364883 、･･･
等、次々と見つかりますね。その数S周辺しか調査しなかったのでもっと小さい数でも例外が
見つかるような雰囲気ですね。
Dengan kesaktian Indukmu さんからのコメントです。（令和５年６月３日付け）
DD++ さん、お返事をありがとうございます。
S = (k +1)*(m*k +1) ………① ではなく、S = (k -1)*(m*k -1) の解を求められた、という
ことになるのですね、なるほど。
GAI さん、(m*k+1)*(n*k+1) のかたちでもよいとして、m や n が大きめのものってあります
かね。
最初に GAI さんにご提示いただいた、10^8 までのリストでのトップは、m = 18 、n = 1でし
た。
実は、さきの反例 S = 6602377*29710693 は、大きな m をひたすら電卓でさがしていてみ
つけたのです。m 捜し、こちらに興味があったものですから。
Dengan kesaktian Indukmu さんからのコメントです。（令和５年６月４日付け）
GAI さんの
ええ、そうなんですよ。だから、もう一つ追加して、[2,7,61,211] の４つの素数を底に指定し
て、全部の底でミラー・ラビン方式(もはや確率的ではないのでこの名は使えないか？）が
クリアーできれば、莫大な奇数nでも合成数か素数かが正しく判定できるような気がしてい
るんですが、その限界も数値的確認もしてないので、何とももどかしい所なんですが･･･。
について調べてみました。
15070413782971 = 1171*19891*647011 で合成数です。
[2,7,61,211]の４つの素数を底にミラー・ラビン判定してみたところ、「Can be prime」となる
ようです。強擬素数判定ですね。
■確認方法
https://planetcalc.com/8995/ で、Miller-Rabin primality test が可能です。
integer number 欄に、「15070413782971」を入力します。前後に不可視なスペースが入る
と叱られます。コピペの際には気をつけましょう。
bases 欄は、「random」ではなく「list」にしましょう。
list としては、スペースで区切って底を入力します。既定値は、「3 5 7 11」となっていますの
でこれを、今回は、「2 7 61 211」と入れ直します。３箇所の区切り以外にスペースをいれると
叱られるようです。
Details はオンにしたほうが面白いです。
Calculate ボタンを押下で、判定結果が返ります。
上の操作は、スマホでのものです。パソコンだと違う？かもしれません。お許し下さい。
Miller-Rabin primality test について、上記のオンラインツールが正確なのか不安ですの
で、どなたか confirm をお願いいたします。
ＧＡＩ さんからのコメントです。（令和５年６月５日付け）
base を211単独でやれば、N;337桁で初めて擬素数を返す。
(2～199までの素数すべてをbase,または197,199の2つだけでbaseとしても同様な結果が起きる。)
これに対し、2,7,61,211の組合せでは以外に小さい14桁での
N=15070413782971(=1171*19891*64701)
を偽判定してしまうのですね。
確かに、1171=1170+1 、19891=17*1170+1 、64701=553*1170+1 と相性が悪いものの構
造になっているものなんですね。
全部をチェックしていませんが、この数値の周辺を観察してみたら判定は正しくされている
ことは確認できました。（但しRubyのプログラムを利用して調べています。）
Dengan kesaktian Indukmu さんからのコメントです。（令和５年６月６日付け）
GAI さん、文脈を追えないので、お教えいただきたいのですが……。
base を211単独でやればN;337桁で初めて擬素数を返す。
336桁以下の数ならば、確定的に素数判定ができるとのお考えでしょうか？
ＧＡＩ さんからのコメントです。（令和５年６月６日付け）
勘違いしてました。例のNは211をbaseにしてチェックすれば擬素数と返すが、それより小
さいものでも擬素数の判定を出すものはあるわけですね。
あくまで[2,3,5,7,･･･,197,199]のすべての素数をbaseにチェックをかけて出てくる擬素数がこ
れだ、ということでいいでしょうか？
Dengan kesaktian Indukmu さんからのコメントです。（令和５年６月７日付け）
15070413782971 は底を 11 のみで判定すると合成数と判定されるようです。従いまして、
[2,3,5,7,･･･,197,199]のすべての素数をbaseにチェックをかけても合成数と判定されると思い
ます。何個か底を選んだときに、そのうちひとつでも合成数判定されると、底全体のテストで、
合成数判定の結果を出すと思います。
また、底として、 197 または 199 のどちらかをひとつ指定しても、やはり合成数判定されます。
15070413782971 は、底として、2, 7, 61, 211 のどれかひとつを指定すると、何れにせよ、合
成数判定されません。2, 7, 61, 211 から何個か選んで判定しても、合成数判定されません。
今回は、2, 7, 61, 211 を底にしたときの強擬素数を探してみたのです。
とはいえ、依然として合成数である可能性は残されていますね。そこで、実際に因数分解して
みたのでした。
以下、工事中！
