😊出会いの泉😊

この粘菌コンピュータ、
以前から疑問だったのですが、識者に問いたいところです。
粘菌が解いたのは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未満となります。


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

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

「実際の入試の原文」通りなのですが、明らかに誤字ですよね。ＨＰでは「数式」に修正しておきます。

まあ、防衛医大だと数学の専門家はいないでしょうから、そこらへんの正確さは蔑ろにならざるを得ないんでしょうねえ。

素数を2から約1億個を求めるのに、25秒でできます。(CPU:i5-2500)
経過時間= 0 分 25 秒
素数個数=105080509
まあ、ここでは、ふさわしい話でもないし、膨大なので、Webにもあげられないし、意味がないですね。
求めた最後の5個は、
2147117417　2147117419　2147117507　2147117509　2147117519
でした。

DD++ さん、誤りをご指摘いただきありがとうございます。
計算を見直したら、はじいてはいけない解をはじいていました。
（解）は修正しました。