😊出会いの泉😊

GAIさん。
2, 7, 61 の三組の底では
4759123141 までの数について
確定的に素数判定ができるとのことです。
このミツグミは優秀なんですね……

上は、
http://miller-rabin.appspot.com/
をみてたら気がついたことです。

ええそうなんですよ。
だからもう一つ追加して
[2,7,61,211]の４つの素数を底に指定して、全部の底でミラー・ラビン方式(もはや確率的ではないのでこの名は使えないか？）
がクリアーできれば、
莫大な奇数nでも合成数か素数かが正しく判定できるような気がしているんですが、その限界も
数値的確認もしてないので何とももどかしい所なんですが･･･

確か、有限個の底の組では
確率100%のミラーラビン判定ができないことが、既に証明されていると思います。
昔、調べたことがあるのですがそのことが書いてあるページがありました。
今、そのページのブクマでURLに飛んだら、
サイトが消失していました。
残念………
どこか探せばあるはずですが……

もちろん素数はそれこそ無限個あるので、全部の奇数に対して合成数か素数かを有限個の調査で調べ尽くすことは
不可能であろうことは想像できますが、ある有限の範囲以内においては、そのような判定できる組合わせはあっても
いいと思われますし、また確かにいろいろな調査で存在しています。
この組[2,7,61,211]がどこまでの範囲で大丈夫なのかは自分もわからないのですが、感じとしては相当莫大な有限の範囲を
保証できるのではないかという意味です。

GAIさん。了解いたしました。

以下のNは、ミラーラビン法により200未満の全ての素数を底にして検査した結果として
強擬素数と判定されたものです。変なところに改行がはいっていて申し訳ありませんが、
コピペミスを怖れた次第です。

N=
80383745745363949125707961434194210813883768828755
81458374889175222974273765333652186502336163960045
45791504202360320876656996676098728404396540823292
87387918508691668573282677617710293896977394701670
82304286871099974399765441448453411558724506334092
79022275296229414984230688168540432645753401832978
6111298960644845216191652872597534901

底を 211 で検査すると、ようやく合成数と判定できるようです。

Nはかなり大きな数ですね。

https://mathcrypto.wordpress.com/2014/11/23/large-examples-of-strong-pseudoprimes-to-several-bases/
を参考にいたしました。

上記のNが合成数であることを見るために、素因数分解を見つけようと試みているんですが
未だに発見できないでいます。
色々な方法の素因数分解でのアルゴリズムがあるようなんで、この方面に精通されている方で
上記を試みるとどんな因数を持っているか分かる方、お教え願います。

GAIさん。
次のふたつの素数の積なのだそうです。

2004791083197498027091532260422734265025940830205662543872531023690016085350598121358111595798609866791081582542679083484572616906958584643763990222898400226296015918301

4009582166394996054183064520845468530051881660411325087745062047380032170701196242716223191597219733582163165085358166969145233813917169287527980445796800452592031836601

（恥ずかしながら…汗…）検算はしておりません。いつもの知人に問い合わせたら、調べてくれて、結果を教わりました。

この2つの数は k と 2k-1 という関係にあるように見えます（目視確認）。
ミラーラビンテストって実は k(2k-1) という形の半素数と相性が悪かったりするんでしょうか？

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のプログラムを利用して調べています。）

GAI さん。

文脈を追えないのでお教えいただきたいのですが……

>base を211単独でやればN;337桁で初めて擬素数を返す。

336桁以下の数ならば
確定的に素数判定ができるとのおかんがえでしょうか？

勘違いしてました。
例のNは211をbaseにしてチェックすれば擬素数と返すが、それより小さいものでも擬素数の判定を出すものはあるわけですね。
あくまで[2,3,5,7,･･･,197,199]のすべての素数をbaseにチェックをかけて出てくる擬素数がこれだ。
ということでいいでしょうか？

> "GAI"さんが書かれました:
> あくまで[2,3,5,7,･･･,197,199]のすべての素数をbaseにチェックをかけて出てくる擬素数がこれだ。
> ということでいいでしょうか？

15070413782971 は底を 11 のみで判定すると合成数と判定されるようです。従いまして
[2,3,5,7,･･･,197,199]のすべての素数をbaseにチェックをかけても合成数と判定されると思います。何個か底を選んだときに、そのうちひとつでも合成数判定されると、底全体のテストで、合成数判定の結果を出すと思います。

また、底として、 197 または 199 のどちらかをひとつ指定しても、やはり合成数判定されます。

15070413782971 は
底として、2, 7, 61, 211 のどれかひとつを
指定すると、いずれにせよ
合成数判定されません。
2, 7, 61, 211 から何個か選んで判定しても
合成数判定されません。
今回は、2, 7, 61, 211 を底にしたときの強擬素数を探してみたのです。

とはいえ、依然として合成数である可能性は残されていますね。そこで、実際に因数分解してみたのでした。

私の解釈が間違っていなければ
C(3,m)はm=0～100に対して
1,1,2,5,5,7,12,12,15,22,
22,26,35,35,40,51,51,57,70,70,
77,92,92,100,117,117,126,145,145,155,
176,176,187,210,210,222,247,247,260,287,
287,301,330,330,345,376,376,392,425,425,
442,477,477,495,532,532,551,590,590,610,
651,651,672,715,715,737,782,782,805,852,
852,876,925,925,950,1001,1001,1027,1080,1080,
1107,1162,1162,1190,1247,1247,1276,1335,1335,1365,
1426,1426,1457,1520,1520,1552,1617,1617,1650,1717,
1717
C(4,m)はm=0～100に対して
1,1,3,5,14,14,23,30,55,55,
76,91,140,140,178,204,285,285,345,385,
506,506,593,650,819,819,938,1015,1240,1240,
1396,1496,1785,1785,1983,2109,2470,2470,2715,2870,
3311,3311,3608,3795,4324,4324,4678,4900,5525,5525,
5941,6201,6930,6930,7413,7714,8555,8555,9110,9455,
10416,10416,11048,11440,12529,12529,13243,13685,14910,14910,
15711,16206,17575,17575,18468,19019,20540,20540,21530,22140,
23821,23821,24913,25585,27434,27434,28633,29370,31395,31395,
32706,33511,35720,35720,37148,38024,40425,40425,41975,42925,
45526
のようになり、この値から式を作ると
C(3,m)=[(m+3)/3]^2+[(m+1)/3][(m+4)/3]/2
C(4,m)=[(m+4)/4](4[(m+4)/4]^2-1)/3+[(m+1)/4][(m+5)/4]^2/2+[(m+2)/4][(m+6)/4](5[(m+2)/4]+1)/6
という式で表されそうです。

投稿ありがとうございます。

自分ではこの求めるべき経路数を一つずつ作図しながら求めていたものですから
mが100までのデータは考えられもしませんでした。

nが3の時の数の並びの変化の状態から
k=m\3 (mを3で割ったときの商をk)
L=3*k+1
として置けば、通常の3×mの格子路での全経路数S=(3+m)!/(3!*m!)に対する比率が
m%3の値に依存していることが起こりそうだと思われた。
つまり
m%3==0 ==>C(3,m)=S/L
m%3==1 ==>C(3,m)=S/(L+3)
m%3==2 ==>C(3,m)=S/(L+4)

これに従いプログラムを組んで並べて行き、m=20　位までぐらいを確認していました。
（なにせ手作業で図を描いてやっと経路数を見つけていたものですから）


これで上手く行きそうだと思ってしまったので
n=4も
k=m\4 (mを4で割ったときの商をk)
L=4*k+1
として置けば、通常の4×mの格子路での全経路数S=(4+m)!/(4!*m!)に対する比率が
m%4の値に依存していることが起こりそうだと思われた。
つまり
m%4==0 ==>C(4,m)=S/L
m%4==1 ==>C(4,m)=S/(L+4)
m%4==2 ==>C(4,m)=S/(L+5)
m%4==3 ==>C(4,m)=S/(L+6)

ところがどっこい実際に起こる経路数が
m%4==2　の場合分数の値を返してきて反映してくれない。
何とかSの値は利用したかったので、実際に起こる経路数と一致させるための調整が
m%4==2 ==>C(4,m)=(S-k*(k+1)*(4*k+5)/6)/(L+4)
へ辿り着きました。
Sから除くパターンの部分がなぜかA016061に繋がっているのが不思議でした。

これを元にプログラムを組んでやはりm=20辺り位までしか確認していませんでした。
それでらすかるさんの値と比較しm=98==2(mod 4)
でも一致できていたので安心しました。

しかしこれを一つの式で表せられるなんて思ってもいませんでした。
感じとしてはnが素数である時は、例の規則で行けそうですが、nが合成数になると
途端に厄介になりそうです。

今n=6に挑戦していますが、図を描いて正解数を求めるしか手がないので
らすかるさん、前もってその配列数をm=100までを教えて貰えませんか？

C(6,m)ならm=0～100に対して
1,1,4,12,23,42,132,132,227,377,
525,728,1428,1428,2010,2803,3504,4389,7084,7084,
9097,11654,13793,16380,23751,23751,28931,35246,40356,46376,
62832,62832,73950,87143,97584,109668,141778,141778,162883,187453,
206591,228459,285384,285384,322046,364124,396510,433160,527085,527085,
586638,654240,705789,763686,910252,910252,1002037,1105317,1183487,1270752,
1489488,1489488,1625096,1776599,1890570,2017169,2331924,2331924,2525439,2740354,
2901207,3079140,3518515,3518515,3786757,4083170,4304066,4547556,5145336,5145336,
5508104,5907251,6203610,6529292,7324878,7324878,7805193,8331713,8721393,9148503,
10187344,10187344,10811692,11493880,11997356,12547920,13881945,13881945,14680520,15550580,
16191123
のようになると思います。

（追記）
https://manabitimes.jp/math/962
↑ここの「書き込み方式」に従ってプログラミングすると簡単ですよ。
対角線を越える点をカウントしないようにするだけですから、
・(幅+1)×(長さ以上)の配列を作る(幅は3,4,6など、100まで出すなら「長さ以上」は101以上)
・配列全体を0にして(0,0)要素だけ1にする
・y=0～(長さ)まで以下の処理を行う
・x=0～(幅)まで以下の処理を行う（ただしy=0のときのみx=1から）
・(長さ)×x＞(幅)×yのときxのループを抜ける（対角線を越える格子点）
・配列の(x-1,y)要素と(x,y-1)要素の和を(x,y)要素の値とする（ただしx-1やy-1が負のとき0）
これで最終的に(幅,長さ)要素に格納された値が答えです。

ヒントをもらったのでPARIのソフトで挑戦してみました。
配列がmatrixの道具しかなく、成分は[1,1]から取ってあるので
微妙に取り方をずらしながら組んでみました。

F(n,m)={M=matrix(n+1,m+1,i,j,if(j==1,1,i==1&&j>1,0))};\
for(x=2,n+1,for(y=2,m+1,if(m*(x-1)<n*(y-1),next,\
M[x,y]=M[x-1,y]+M[x,y-1])));M

これより
gp > F(6,10)
%813 =
[1 0 0 0 0 0 0 0 0 0 0]

[1 1 0 0 0 0 0 0 0 0 0]

[1 2 2 2 0 0 0 0 0 0 0]

[1 3 5 7 7 7 0 0 0 0 0]

[1 4 9 16 23 30 30 0 0 0 0]

[1 5 14 30 53 83 113 113 113 0 0]

[1 6 20 50 103 186 299 412 525 525 525]



gp > F(6,18)
%818 =
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

[1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

[1 2 3 4 4 4 4 0 0 0 0 0 0 0 0 0 0 0 0]

[1 3 6 10 14 18 22 22 22 22 0 0 0 0 0 0 0 0 0]

[1 4 10 20 34 52 74 96 118 140 140 140 140 0 0 0 0 0 0]

[1 5 15 35 69 121 195 291 409 549 689 829 969 969 969 969 0 0 0]

[1 6 21 56 125 246 441 732 1141 1690 2379 3208 4177 5146 6115 7084 7084 7084 7084]

あの手作業が夢のようです。


またnが素数の場合は予想が当たるか確認してみた。
n=7でやってみると
F7(m)={k=m\7;L=7*k+1;S=(7+m)!/(m!*7!);}\
if(m%7==0,print(m";"S/L),m%7==1,print(m";"S/(L+7)),\
m%7==2,print(m";"S/(L+8)),m%7==3,print(m";"S/(L+9)),\
m%7==4,print(m";"S/(L+10)),m%7==5,print(m";"S/(L+11)),\
m%7==6,print(m";"S/(L+12)))
と組んで走らせると
gp > for(m=1,50,F7(m))
1;1
2;4
3;12
4;30
5;66
6;132
7;429
8;429
9;715
10;1144
11;1768
12;2652
13;3876
14;7752
15;7752
16;10659
17;14421
18;19228
19;25300
20;32890
21;53820
22;53820
23;67860
24;84825
25;105183
26;129456
27;158224
28;231880
29;231880
30;278256
31;332112
32;394383
33;466089
34;548340
35;749398
36;749398
37;870922
38;1008436
39;1163580
40;1338117
41;1533939
42;1997688
43;1997688
44;2270100
45;2572780
46;2908360
47;3279640
48;3689595
49;4638348
50;4638348

一方
G(n,m)={M=matrix(n+1,m+1,i,j,if(j==1,1,i==1&&j>1,0))};\
for(x=2,n+1,for(y=2,m+1,if(m*(x-1)<n*(y-1),next,\
M[x,y]=M[x-1,y]+M[x,y-1])));M[n+1,m+1]
から
gp > for(m=1,50,print(m";"G(7,m)))
1;1
2;4
3;12
4;30
5;66
6;132
7;429
8;429
9;715
10;1144
11;1768
12;2652
13;3876
14;7752
15;7752
16;10659
17;14421
18;19228
19;25300
20;32890
21;53820
22;53820
23;67860
24;84825
25;105183
26;129456
27;158224
28;231880
29;231880
30;278256
31;332112
32;394383
33;466089
34;548340
35;749398
36;749398
37;870922
38;1008436
39;1163580
40;1338117
41;1533939
42;1997688
43;1997688
44;2270100
45;2572780
46;2908360
47;3279640
48;3689595
49;4638348
50;4638348

予想大当たり！！！

しかしn=6の場合はS=(6+m)!/(6!*m!)
の数値から導くのは困難でした。（未だに解決できずです。）

この粘菌コンピュータ、
以前から疑問だったのですが、識者に問いたいところです。
粘菌が解いたのはNP問題ではなく、多項式時間で解ける「中国人郵便配達問題」ではなかったかと思うのですよね。そんな気がするというだけで根拠はありません。間違っていたらごめんなさい。

四色定理の五辺国の話が NP だったというのは初めて聞きますが、本当ですか？
何か参考になる文献ありますか？

念のためですが、「実際に与えられた地図をどう 4 色で塗るか」という問題ではなく、「五辺国の塗り足しのためにどのような場合分けをすればいいか」の話であってますよね。
前者の話なら NP なのは明らかですし、四色定理の証明方針を考えればおそらく P なんだろうと思います。
が、後者の話だとそもそも何を問題サイズ n とすればいいかもよくわからないので、P とか NP とかを判定する対象にそもそもできないんじゃないかと思います。

https://ja.wikipedia.org/wiki/%E5%9B%9B%E8%89%B2%E5%AE%9A%E7%90%86
の四色定理にこう書いてあります。ケンプの証明後11年して、5辺国に誤りが見つかって、それで、これは五色定理と呼ばれていたそうです。四色で十分かは、グラフ理論の未解決問題として残ったと書いてあります。

その後コンピュータを利用して、四色問題を「証明」したとあります。

ですからDD++様の認識でよいと思います。

そこで、五色定理はPですが、グラフ理論の未解決問題をコンピュータでしらみつぶしで「証明」したから、Pではなく、Non-Pつまり、NPじゃないかと私は、思いました。

NP 問題の NP って Non-P じゃないですよ？

はちべえさん。

話のスジがずれていたら申し訳ないですけれども。

巡回セールスマン問題において、
セールスマンが訪問すべき拠点が50箇所程度であったとして、
コンピュータがしらみつぶしに厳密解を求めるために要するに時間は、
宇宙開闢以来現在までの時間でも、とてとても足りない、お話にならないくらい桁違い、
そういうオハナシなのですよね？
くだんのNHKの番組で紹介されていた筈です。

ではひるがえって、
四色問題における不可避集合を、事実上、しらみつぶしに調べることは人間の手には余る、だからコンピューターを使った、
でもこれ、そんなに時間がかかるものだったのてをしょうか？
不可避集合の個数は2000弱。
巡回セールスマンの訪問先の50よりも遥かに多いです。
にもかかわらず、放電手続きは無事に完了しています。論文の付録に全パターンを書き下すことができました。
これ、ほんとに巡回セールスマン問題と同じくらい難しい問題なのですか？

日本語で「しらみつぶし」というイメージは私も共有しています。
しかしながら、数学における、NPは、単なるしらみつぶしではないことも、頭にいれて議論したいものです。

おまけ。
NPとは、非決定性多項式時間（Non-deterministic Polynomial time）であり、Not Pではない。 定義は、「非決定性チューリングマシンによって多項式時間で解くことができる問題」かつ、「yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式時間で判定できる問題」

ええ、正確には、Non-d.... Pですよ。d....は忘れましたが・・・

Dengan kesaktian Indukmu様、こんばんは。

>NPとは、非決定性多項式時間（Non-deterministic Polynomial time）であり、

そうです。それです。

コンピュータの計算に4年かかったそうです。充分、長い時間だと思いますけれどね。
コンピュータの出力は、高さ1.2mあったそうです。つまり、論文はとてもエレファントな証明だったそうです。

たぶん、終わりがあるんだろうかという不安にさいなまれたと思いますが・・・

一晩考えてみました。
問題の大きさ n を、「n 個の領域がある任意の地図を 4 色で塗り分けるアルゴリズムは存在するか」という形で定義すれば、四色定理の証明方法が NP かどうかの議論を始められることに気付きました。
そして、コンピュータでのしらみつぶしは全体の国の数に影響されない方法での検索だったので、解の発見にかかる時間は明らかに O(n^0) です。
だから、四色定理の証明は P 問題ってことになる……で、あってますかね？

DD++様、こんばんは。

ケンプは、数学的帰納法を使っていました。n国の地図は、4色で塗れるとします。

そこで、色が塗られてないn+1国の地図を持ってきて、
１）2辺国を探します。まず、2辺国を消すと、n国の地図ですから、4色で塗れるはずですから、塗ります。
そして、2辺国を復活します。2辺国は2つの国に挟まれているので、あと2色ありますから塗れることができます。
n+1国の地図が4色で塗れました。

また、色が塗られてないn+1国の地図を持ってきて、
２）3辺国を探します。消します。すると、地図は4色で塗れます。そして、3辺国を復活します。３辺国は３つの国に挟まれているので、あと１色ありますから塗れることができます。
n+1国の地図が4色で塗れました。

また、色が塗られてないn+1国の地図を持ってきて、
３）４辺国を探します。消します。すると、地図は4色で塗れます。そして、４辺国を復活します。４辺国は４つの国に挟まれているので、もう色はありません。そこで、トリッキーなことをして、４色でぬれました。
n+1国の地図が4色で塗れました。

また、色が塗られてないn+1国の地図を持ってきて、
４）５辺国を探します。消します。すると、地図は4色で塗れます。そして、５辺国を復活します。５辺国は５つの国に挟まれているので、もう色はありません。

つまり、５辺国問題が復活するのです。P問題では、解けません。

＞問題の大きさ n を、「n 個の領域がある任意の地図を 4 色で塗り分けるアルゴリズムは存在するか」という形で定義すれば、四色定理の証明方法が NP かどうかの議論を始められることに気付きました。
そして、コンピュータでのしらみつぶしは全体の国の数に影響されない方法での検索だったので、解の発見にかかる時間は明らかに O(n^0) です。

数学的帰納法で、n国まで成り立つとしてますから、これは、問題ないでしょう？
では、n+1国のときに成り立つ証明がいるのではないでしょうか？
そうでないと、数学的帰納法が完成しません。

いやいや、数学的帰納法で簡単（P≠NP 問題の意味では）に証明できるから P 問題だという話です。

ケンプ、アッペル、ハーケンによる証明は、
「100 ヶ国の地図が全て塗り分けられることの証明」でもコンピュータで 4 年、
「1000 ヶ国の地図が全て塗り分けられることの証明」でもコンピュータで 4 年、
「10000 ヶ国の地図が全て塗り分けられることの証明」でもコンピュータで 4 年、
「100000000 ヶ国の地図が全て塗り分けられることの証明」でもコンピュータで 4 年、
でしょう？

今日、NHKのEテレで、午後9:30~より、「笑わない数学　ポアンカレ予想」が放送されます。

Wikipediaのポアンカレ予想より引用すると、
＊＊＊＊＊引用開始＊＊＊＊＊＊
ペレルマンは解法の説明を求められて多くの数学者達の前で壇上に立った。しかし、ほとんどの数学者がトポロジーを使ってポアンカレ予想を解こうとしており、聴講した数学者たちもほとんどがトポロジーの専門家であったため、微分幾何学を使ったペレルマンの解説を聞いた時、「まず、ポアンカレ予想を解かれたことに落胆し、それがトポロジーではなく（トポロジーの研究者にとっては古い数学と思われていた）微分幾何学を使って解かれたことに落胆し、そして、その解説がまったく理解できないことに落胆した」という。
＊＊＊＊＊引用終了＊＊＊＊＊

トポロジーとは、位相幾何学だそうです。

ポアンカレ予想は、宇宙がおおよそ丸くない場合はどういう場合があるかというサーストンの研究から、これを証明することになったと言ってました。現在の物理学の世界観では宇宙はトーラス構造だそうです。

つまり、宇宙がおおよそ丸いというのは、直接的には証明されてないようですね。

４色問題もケンプの証明後11年後間違いが発見され、チューリングのオートマトン研究から、ノイマン型コンピュータができる訳ですが、チューリングがオートマトンを研究しなければ、コンピュータもできず、ハーケンらのコンピュータを使った解決はなかったでしょうし、後100年くらいかかったかもしれませんし、永遠に未解決のだったかもしれません。

このように、未解決の問題もコンピュータというタイミングで、解決されたことからも、いつか準備が整うまで、待たされ、それから解決されるのでしょう。

また、ペレリマンの証明も、後何年かして、間違いが発見されるかもしれません。絶対はないのでしょう。

さて、来週の「笑わない数学」は、虚数だそうです。虚数の歴史ですね。

今日、NHKのEテレで午後9:30から「笑わない数学　フェルマーの最終定理」が放送されます。

フェルマーの最終定理は、早々に未解決問題になって、数学者から、見放されたのでしょう。皆、忙しいですからね。

それをひっくり返したのが、全く関係のないと思われていた谷山ー志村予想が、フライ・セールのイプシロン予想で、フェルマーの最終定理を解決するとなったのです。
wikipedia 「フェルマーの最終定理」より
＊＊＊引用開始
つまり、谷山–志村予想が証明されたならば、それはフェルマーの最終定理が証明されたことをも意味するのである(=完全証明への道がつながった)。
＊＊＊引用終了
となったのです。

今日、NHKのEテレで午後9:30から「笑わない数学　カオス理論」が放送されます。

ニューロ人工知能は、一つ一つの原子を扱う統計力学的発想ですが、この前、NHKのEテレの心の時代で、脳はカオスであるという話がありました。まあ、マクロな経験則からできた熱力学みたいなものですね。現実は、統計力学より、熱力学のほうがよく使われているようです。ニューロ人工知能もカオス理論で、大きく進展するかもしれませんね。ニューロの人工知能で、うまく行っているのはカブトガニの視覚の研究の応用である画像認識だけらしいですから・・・・

今日、NHKのEテレで午後9:30から「笑わない数学　暗号理論」が放送されます。

暗号理論は巨大な数の素因数分解が困難であることを元にしています。
そこで、素数生成式を探していると、
https://enpedia.rxy.jp/wiki/%E7%B4%A0%E6%95%B0
にたどり着きました。素数生成多項式は存在しないことが証明されているそうです。
でも、そこには、マチャセビッチの多項式が、存在しているという話です。
でも、実用性は全くないそうです。
しかし、マチャセビッチの多項式は、証明されているそうです。
矛盾してますが、・・・・・

マチャセビッチの多項式について調べてみましたが、何も矛盾しているとは思いませんでした。
はちべえさん、そろそろ「正しい」「間違っている」を自分勝手に決めつけて話すのをやめませんか。

DD++様、こんばんは。
＞はちべえさん、そろそろ「正しい」「間違っている」を自分勝手に決めつけて話すのをやめませんか。
わたしは、そんなことを言ってません。
＞素数生成多項式は存在しないことが証明されているそうです。
＞しかし、マチャセビッチの多項式は、証明されているそうです。
なので、
＞矛盾してますが、・・・・・
と感想を書いただけです・・・・・

さて、来週は、ABC予想です。これは、大変面白いので、期待してます。

余談です。

《暗号理論は巨大な数の素因数分解が困難であることを元にしています。》

んー。
「笑わない数学」では
RSA暗号しか説明しなかったのでしょうか？
公開鍵暗号は、他にもいくつかやりかたがあってですね、最近ではRSAには未来がないという考えを持つ人も増えつつあります。量子コンピュータが素因数分解を得意とするかもという懸念があるためです。その実装はまだまだ先ですが。

《暗号理論は巨大な数の素因数分解が困難であることを元にしています。》については
もうちょつと複眼的に興味を持っていただければ幸いです。

Dengan kesaktian Indukmu様、こんばんは。
ありがとうございます。

来週のABC予想は面白いですよ。
ちょっと、参考までに、
数学者は宇宙をつなげるか？ａｂｃ予想証明をめぐる数奇な物語
https://www.nhk.jp/p/special/ts/2NY2QQLPM3/blog/bl/pneAjJR3gn/bp/pzwyDRbMwp/

かけ算は簡単であるが、足し算はむつかしいということで、フェルマーの最終定理も足し算でなくて掛け算だったらたちどころに解決できるそうです。数学にはそういう問題がたくさんあって、望月さんによって、ABC予想が証明されたので、数学は大きく変わるとか・・・

あっそうだ、思い出しました。

RSA暗号で。
秘密鍵を p, q のふたつの素数とし、
公開鍵を N=p*q としたときに。
Nの素因数分解をせずに暗号文を復号し平文を求める方法がいくつか知られています。
ただし、p,q の取り方が下手くその場合にですが。

ビックリするのですが。
平文 X を暗号化したものを
此の投稿に限り、
X ^a
としましょう。
で、こうしてできた暗号文を、
さらに、公開鍵で繰り返し暗号化していきます。
(((……(X^a) ^a) ^a) ^a) ……^a
そうすると、それが
Xと等しくなってしまうことがあるそうです。
これを、繰り返し暗号化攻撃といいます。

回避するためには
秘密鍵 p,q の作り方を工夫する必要があります。特許もあるようです。

繰り返し暗号化攻撃の他にも
アタックのしかたが少なくないようで
RSAでの安全な 秘密鍵の作り方が工夫されているようです。

このリストは、
底として、2 およびに 3 だけを取ったときのものと同じになるようですね………

それはそうと、
p*(t*p-t+1)
のかたちになっているのですね。

DD++さんから、ミラーラビンは今話題にしている形での半素数に弱いのかというテーマが挙げられています。

必ずしも半素数にはならないようでしたので
以下にメモをあげます。

3215031751 は、
2, 3 をともに底としたときに
強擬素数です。
この数は
28351 * 113401
に等しく、また
113401 = 28351 * 4 -3
となっています。

私達がいま興味をもっていた形ですね。

さて、
113401 = 151*751
と素因数分解可能です。

このことから
3215031751 は半素数ではありません。

個人的には、半素数であるかどうかよりも、k と 2k-1 という値の大きさの関係を気にしていました。
その後、
・どうやら k+1 と 2k+1 という形に書いた方がよいこと
・2k+1 だけでなく mk+1 という形であれば m=2 という形かどうかはあまり重要でなさそうなこと
が見えてきていますね。

751 と 151 も、
151 = 150 + 1
751 = 5*150 + 1
ですから、同様の性質は持っていると言ってよさそうに思います。

2 と 3 とをともに含む
複数の底でミラー・ラビン判定を行い
結果が強擬素数であったとします。

この強擬素数が素数であるのか合成数であるかについてを更に調べたいと思ったとします。

この強擬素数を S とします。
まだ未証明ですが、次のような予想が成り立つとしましょう。すなわち。

S が合成数であるならば
自然数 k と m とがあって
S = (k +1)*(m*k +1) ………①
となる。

S が素数であるか合成数であるかを知りたいときに ① をあてにしてよいとするならば
単に、√S までの素数を列挙して
S をそれらで割ってみる素因数分解方法よりも速く素因数分解の結果が得られることがあるのでしょうか？

GAI さんによる 10^8 までの
強擬素数の素因数分解のリストを見るかぎり
どうやら m はかなり小さめです。

m について小さい順に調べると良いのではと思います。

①を、k についての２次方程式とみて
判別式が平方数になるかどうか検査すると
よいのではないかと山勘を働かせてみました。

さて、この方法は、本当に速く処理できるものなのでしょうか？

素因数分解できるまでの「平均時間」は圧倒的に速いと思います。
素因数分解ができるまでの「最悪の時間」はむしろ悪化すると思いますが。

つまり、最悪試さなきゃいけない候補の数は増えますが、当たりになる可能性が高いところだけを最初にピックアップして試せる感じになります。
たぶん。

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 でも強擬素数なのに。

k が負の整数の場合、狙っていた形とは合致しませんが S の因数分解には成功します。
ですから、排除する必要はないのではないかと思います。

また、k が整数にならない場合の心配ですが、仮にそうなっても 4mS を 2 つの因数にわけることは成功します。
m が S よりずっと小さい場合は、その場合でも（目的の式の形にはなりませんが）S の因数分解には成功するんじゃないかと思うのですが、どうなのでしょう。

> DD++さんが書かれました:
> また、k が整数にならない場合の心配ですが、仮にそうなっても 4mS を 2 つの因数にわけることは成功します。
> m が S よりずっと小さい場合は、その場合でも（目的の式の形にはなりませんが）S の因数分解には成功するんじゃないかと思うのですが、どうなのでしょう。

アドバイスを有難うございます。
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
4*m*S = (T +(m -1))*(T -(m -1))
となります。
仰るとおりに、
《4mS を 2 つの因数にわけることは成功します。》
とわかりました。
実用の範囲内で m が十分に小さいことがわかれば、
k を求めることを行わなくても
S の合成数判定ができるのですね、
おどろきです。


> DD++さんが書かれました:
> 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
となっています。

k が負の整数だと
S = (-101)*(-103)
みたいな形になるので、自然数の積にはなりません。
でも、これを見て自然数の積に書き直すのは容易ですよね、という話です。

> 反例

薄々そんな予感はしていましたが、やっぱり (mk+1)*(nk+1) の形も出てきましたか。
まあ、m も n も小さいという条件でなら、該当する数を探す労力はそんなに変わらないと思いますが。

その数S以前には
190131062354461,190847302523971,191212468762741,･･･
その数以降も
197201702068963,197867738963563,198675496474963,198888784469461,200262009366409,
200271411485473,200669198495977,201324851364883,･･･
等次々と見つかりますね。

その数S周辺しか調査しなかったのでもっと小さい数でも例外が見つかるような雰囲気ですね。

1150 の DD++ さん。

お返事をありがとうございます。
S = (k +1)*(m*k +1) ………①
ではなく、
S = (k -1)*(m*k -1)
の解を求められた、ということになるのですね、なるほど。


1153 の　GAI さん。
(m*k+1)*(n*k+1)
のかたちでもよいとして
m や n が大きめのものってありますかね。

最初に GAI さんにご提示いただいた
10^8 までのリストでのトップは
m = 18 , n = 1でした。

実はさきの反例
S = 6602377*29710693
は、大きな m をひたすら電卓で
さがしていてみつけたのです。
m 捜し、こちらに興味があったものですから。

(1)だと思います。
平面と垂直な直線が「法線」と定義されていますので、法線と平面のなす角は90°であり、
それから考えるとlとPのなす角は60°と考えないと矛盾が生じてしまうと思います。
（これ以外の定義は見たことがありません）
30°は「平面Pの法線と直線lのなす角度」のように言うと思います。

ありがとうございます。
やっぱり (1) でいいですよね。

ところが、先日ある場所で出会った問題に、以下のように書いてあったんです。
「ただし直線が平面に含まれるとき、両者のなす角は π/2 とします。」
実際に解く上では無関係な注釈だったので、誤植かと思って (1) の定義に従って私は解きました。
が、模範解答もどうやら (2) の方を採用している様子。

私が定義を勘違いしているのか、それとも「0 を自然数に含むか問題」のように定義が何種類かあるのか、と思って質問した次第でした。
しかし、うーん、結局どういうことだったんだろう。

> 「ただし直線が平面に含まれるとき、両者のなす角は π/2 とします。」
この文だけだと何とも言えないですね。例えば
平面Pの法線nと平面Pとの交点をOとし、Oを通るある直線と法線のなす角度をθとします。
「ただし直線が平面に含まれるとき、両者のなす角は π/2 とします。」
だとしたら「両者」が「直線と法線」を指している可能性が高いです。
もしそうであれば(1)と矛盾しませんね。

管理人さんも、調べてくださってありがとうございます。

問題文全体がないと判断しかねる感じのようなので、議論の資料とする目的で、著作権法第32条に基づいて公表された著作物の引用をします。
記事の方に転載するかどうかは管理人さんの判断に委ねます。
なお、掲示板に書く都合上、
・分数の表記方法
・全角と半角（印刷では区別がつかないため）
・アルファベットの書体
がやむを得ず変更されています。

-----引用ここから-----

問題3. xyz 空間において 2 点 ( 3, -6, 2 ), ( -11, -4, 6 ) を通る直線を l, 方程式 5x-3y+4z-11=0 で表される平面を P とします。
l と P のなす角をθ ( 0≦θ≦π/2 ) とするとき, cosθ の値を求めなさい。ただし, 直線が平面に含まれるとき, 両者のなす角は π/2 とします。

-----引用ここまで-----
（第406回 実用数学技能検定 1級 1次:計算技能検定 (c) 日本数学検定協会 より引用）

模範解答は 1/√3 だそうです。

答えが間違っているとしか言いようがないですね！

どちらかというと「問題が間違っている」ような気がします。
「直線が平面に含まれるとき, 両者のなす角は π/2 」って、どこの角度のことを言っているのか意味不明です。
（直線と「平面の法線」の角度のことを言っているのかな？と予想はできますが。）
「平面とその法線のなす角度がπ/2」が多くの人の共通認識だと思います。

問題も答えもおかしいと思うのが私だけでなくてよかったです。
数検ってこういう場合採点どうなるんだろう。

数検の結果の詳細が届きました。
√6/3 は不正解になっていました。
合格者正答率がこの問題だけ異様に低いので、私と同じように戸惑いながらも通常の定義に従って解いた人が多かったんでしょうね。

これのせいで 1 点とか 0.5 点足らなかった人がいたらかわいそう……。

A>B>C,三つの抵抗の接続の場合、
A＋B＋C＞A＋B×C＞B＋A×C＞C＋A×B＞
A×（B＋C）＞B×（A＋C）＞C×（A＋B）＞A×B×C
８個の絶対不等式が生まれます。
４個の抵抗では、何個の不等式ができるか、興味ないですか？

> 同様に、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になるタイミングが異なる素因数の積を
底にした判定は確率の向上になりませんので、同じ素因数は避けた方がいい、
ということを言いたかったのです。

> 少なくとも-1になるタイミングが異なる素因数の積を底にした判定は確率の向上になりませんので、同じ素因数は避けた方がいい、

これ、実は少し考えなければいけないところではないかと思います。

例えば 13 をミラーラビンテストにかけるとします。
このとき、a = 3, 7, 11 という 3 つの素数で判定を行うことは有効でしょうか？

普通の自然数の世界では、7 は素数です。
しかし、13 をミラーラビンテストにかける場合、行う計算は全て mod 13 の世界です。
その世界では、3*11=7 ですから、7 はらすかるさんが仰るところの避けた方がいい数に該当します。

こう考えてみると、確率向上に貢献する a と貢献しない a の判別は「通常の自然数の世界で合成数だから」という単純な話ではない気がしています。

らすかるさん、DD++ さん。

「ミラーラビンの底には素数をとるのが良いのでしょうか？　確率の評価に影響をあたえますか？」という私の疑問にお答えくださってありがとうございます。

私のほうでも調べてみたことがあります。

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の https://oeis.org/A014233 によります。

一定の範囲の数について素数判定を確率100%で判定するには
底としては素数の組を使うのがよいのかと
思ったところですが、一方において、これに反するような、
次のようなサイトがありました。


Deterministic variants of the Miller-Rabin primality test
http://miller-rabin.appspot.com/

上のサイトによれば7つの底を使って
2^64 までの数を確定的に素数判定できる底の例として
2, 325, 9375, 28178, 450775, 9780504, 1795265022
が挙げられています。
偶数か5の倍数かが、底になっていて
唖然としました。

悩みは続きます。

7と61かな？

(追記)
プログラムを作って調べたら、211も該当していました。

GAI様、らすかる様、こんにちは。

＞P=p+k*(k+1)/2

というと
P=p+(1+2+3+・・・+k)
ということですか？

この3個以外に見当たらないのが面白かったです。
Pが大きくなっていくと、構成できる場合の可能性が圧倒的に増大していくのでこれ以上は見つからないのでしょうね。

ミラー・ラビン法の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]　が出現してしまう。

これと何かしら関係しているかもと思われました。

正の整数 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で割り切れる
そして13は分母の9と互いに素だから与式も13で割り切れる

n=6m-5のとき
分子は3339,3339999999,3339999999999999,…のようになり
3339÷7=477、999999÷7=142857だから
分子÷7は477,477142857,477142857142857,…となり分子は7で割り切れる
そして7は分母の9と互いに素だから与式も7で割り切れる

まとめ
n=3mのとき37で割り切れ、
n=3m-1のとき3で割り切れ、
n=6m-2のとき13で割り切れ、
n=6m-5のとき7で割り切れるから
常に合成数。

[後者]
n=136のとき素数という反例があるから合成数とは限らない。

素晴らしいです。

なおネタ元は以下です。
https://oeis.org/A112386

追伸：
https://oeis.org/A107612
こちらも、参考にしました。

A112386はなぜこんなにちょっとしかデータがないんでしょうね。
せっかく37の例を載せているんだから
251,26111,271,281,29111111,3011,311,3211111111111111111111111111111111111,34111111,3511,361111,-1
ぐらい載せればいいのに。
（先頭の3行のところではなくLINKSにある表のことです）
ちょっと調べてたくさん追加してみようかな。

正攻法で真面目に素因数分解をしていくと
56111…11
(505*10^n -1)/9
での素数探しで計算量が爆発するのではと
危惧いたします。

以前あった 381111…… の話かと思ったら、今回は 371111…… なのですね。

http://shochandas.xsrv.jp/mathbun/mathbun1315.html

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)
のときには
どうしたものでしょうか？

あっそうですね。

（３）n ≡ 2 (mod 3)
ということは

3811, 3811111, 3811111111
ですが、
3811 は　37 の倍数、
111 は　37 の倍数ですね。

(a10^n-1)/9とかa10^n-1にしたらどうでしょう。

aは2m,2m+1とか、3m,3m+1,3m+2とか、10m,10m+1,10m+2,10m+3,10m+4,10m+5,10m+6,10m+7,10m+8,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の倍数。
以下省略

> "Dengan kesaktian Indukmu"さんが書かれました:
> 正攻法で真面目に素因数分解をしていくと
> 56111…11
> (505*10^n -1)/9
> での素数探しで計算量が爆発するのではと
> 危惧いたします。

A069568;
によりますと５６の後に1が18470個も続くようです。

"GAI"さんが書かれました:

> A069568;
> によりますと５６の後に1が18470個も続くようです。

わあっ！！
A069568
にはちやんと 38111…111
について も 触れてあるのですね！！
見落とし、恥ずかしいです。

私は次に挙げる「模範解答」をみていて
意味がわからずに難儀していたのでした。

http://bxmo.org/problems/bxmo-problems-2015-zz.pdf

3乗マイナス3乗だと気がつくことで
個人的には納得したのですが
いまだにこの模範解答の筋立ての意味を
つかみかねています。

４．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は、３の倍数。

> Dengan さん

まさしく No.1089 と No.1090 で述べられている通りの記述に見えますが、疑問点はどこなのでしょう？

DD++ さん。
ご指摘をありがとうございました。
仰る通りです。

慎重に読み直したところ、私の誤読とわかりました。

正しくは模範解答の PDF にありますとおり、
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.　

こんな読み方をしていてはダメダメに決まっています。[ pdf を読みながらノートに写経したときの転記ミスが最初のきっかけです。いったん思い込むと沼にはまる悪い癖が今回も発生しましました。]

DD++ さん、ご教示をありがとうございました。
また、みなさまにつきましては
私からのわけの分からない投稿で
御迷惑をおかけしましたこと、
お詫び申し上げます。

> "らすかる"さんが書かれました:
> A112386はなぜこんなにちょっとしかデータがないんでしょうね。

1331,　13311,　133111,　1331..1
がヤバそうです。
これは
(1198*10^n -1)/9
ですが、任意の正の整数 n について
合成数のような！？
なかなか素数がみつからず
さりとてなぜ合成数になるのか
見通しもつけられず、、、

間違っておりました。よくよく考えると、これでいいと思います。

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)となる。

> 1331,　13311,　133111,　1331..1
> がヤバそうです。
> これは
> (1198*10^n -1)/9
> ですが、任意の正の整数 n について
> 合成数のような！？

おそらく
(1198*10^2890-1)/9　（133の後に1が2890個）
が素数だと思います。

しかし、GAIさんが書かれたA069568に118までのデータが載っていますので、
A112386は56で巨大な数になることを考えてもせめて55までは載っていても
いいのに、とは思います。

(追記)
「(1198*10^2890-1)/9は多分素数」の理由
ミラーラビン法で15000以下の素数1754個をそれぞれ底にしてテストしたところ、
すべてパスしましたので、「合成数である確率」は1/10^1000未満となります。

昨日はとんちんかんなことを書いてしまいました。毎度のことですみません。

根本的に、間違いであることを指摘しました。

緑色のうんざりはちべえをクリックしてください。

> "らすかる"さんが書かれました:
> おそらく
> (1198*10^2890-1)/9　（133の後に1が2890個）
> が素数だと思います。

> 「(1198*10^2890-1)/9は多分素数」の理由
> ミラーラビン法で15000以下の素数1754個をそれぞれ底にしてテストしたところ、
> すべてパスしましたので、「合成数である確率」は1/10^1000未満となります。


らすかるさん。検証をありがとうございました。
確率的素数ということですね。

一点、質問をさせていただきたく思います。
ミラーラビンの底には素数をとるのが良いのでしょうか？　確率の評価に影響をあたえますか？

(1) a=40 (3が483個)
(2) b=95 (7が2904個)
(3) c=97 (9が90個)

(2)はちょっと時間がかかりました。

明らかにA112394やA113076でのデータは不足していますね。
(2)bがいくつまで7を並べるといいのかは、自分のプログラムとスペックでは手に入れることはできませんでした。
(862*10^2904-7)/9での素数判定だけでも一夜の時間が必要でした。
可能な限りらすかるさんに補充してもらえると有難いです。

それでは、
1234567890123456789012345678901・・・8901
1234567890123456789012345678901・・・567
はどうなんでしょう？素数にはならないのでしょうか？ただし、
1234567890123456789012345678901・・・890123は3の倍数
1234567890123456789012345678901・・・012345は5の倍数
1234567890123456789012345678901・・・456789は3の倍数
です。
(%i32) factor(12345678901234567890123456789012345678901234567890123456789012345678901234567);
(%o32) 7　8447　15511　 13460916961858847299449477233189774374173209263392110114539531835993
と結構大きな素数が見つかりました。

πは、何億桁も求められていると思います。その一部分を切り出したら、長大な素数になるのではないでしょうか？
また、√2、√3も同じくその一部を切り出したら、長大な素数になるのではないでしょうか？

小数点を頭とし、頭から、いくつか行ったところから始めてそこから、何千桁の素数になるとかという発見も可能ではないでしょうか？

そういう話は、ないのでしょうか？

あります。https://oeis.org/A005042
3,31,314159,31415926535897932384626433832795028841,
これ以上はhttps://oeis.org/A060421を参照のこと
なお
√2==>A115377
√3==>A119344
何でも調査済みです。

GAI様、おはようございます。

ありがとうございます、調査中ですか。

そこで、こんなくだらないことを考えました。
πの何億桁を暗号文として見れば、何語かしれませんが、ある文章が発見されるかもしれませんね。
また、πの何億桁をさがすと、小数点を除いた何桁かのπとか、小数点を除いた何桁かの√２とか√３が見つかるかもしれませんね。
あるいは、πの何億桁をさがすと、ほとんどの素数が含まれているかもしれませんね。すると、あなた方は、素数を発生する式を見つけようと奮闘されていると思いますが、それは、πの何桁目にあるという関数なのかもしれませんね。あるいは√３かもしれません。