😊出会いの泉😊

このリストは、
底として、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++ さん、誤りをご指摘いただきありがとうございます。
計算を見直したら、はじいてはいけない解をはじいていました。
（解）は修正しました。

n本の場合に刺し方がF(n)通りあるとする。
ただし、n=0の場合はF(0)=1とする。

まち針がn+1本ある時を考える。
特定の1本のまち針[赤]に着目し、その先端側にあるまち針の本数をi本、頭側にあるまち針の本数をn-i本とする(0≦i≦n)。
n本のまち針をこの2グループに分ける方法はCombination(n,i)通り。
先端側にあるi本のまち針の刺し方はF(i)通りで、その各々に対しまち針[赤]を刺す場所がi+1通り(針山とi本のまち針の頭)。
頭側にあるn-i本のまち針の刺し方はF(n-i)通り(まち針[赤]の頭を針山とみなせばよいため)。
よって漸化式は、
F(n+1) = Σ[i=0...n] Combination(n,i) * F(i) * (i+1) * F(n-i)
となる。

F(n)の式の形は予想できているので数学的帰納法で示せばよい。

……のですが、式変形できずに詰まっています。

そうなんですよ。

Σ[k=0...n] nCk * (k+1)^k * (n-k+1)^(n-k-1) = (n+2)^n

Σ[k=0...n] nCk * (k+1)^(k-1) * (n-k+1)^(n-k-1) = 2*(n+2)^(n-1)

このどっちかが成り立ってくれれば話は終わりなんですけど、
「私の備忘録」->「代数学分野」->「二項係数の性質」
にもそれっぽい式はないんですよね。
二項係数関係の総和は、底か指数かどちらか固定されていたら「よくある問題」なんですが、両方変わっていくのはほとんど見たことがありません。

どれが積でどれが添字か全くわからないので、添字は [ ] で書くなど区別しやすい表記にしてもらうことはできますか？

やっと情報を見つけました。
https://en.m.wikipedia.org/wiki/Cayley%27s_formula

こっちにある証明法がわかりやすかったので、この問題の用語や数値に合わせながら翻訳します。
https://en.m.wikipedia.org/wiki/Double_counting_(proof_technique)


まず、針山もまち針とみなします。
つまり「針山をまち針の頭に刺す」が、なぜかできそうな気分になっておきます。

以下の操作を行います。

(1) n+1 本のまち針（本当は針山であるものも含む）を机上に並べます。

(2) n+1 個の頭から 1 つを選びます。そして、その頭とつながっておらず、かつどこにも刺していない針先 n 個のうち 1 つを選びます。選んだ針先を選んだ頭に刺します。

(3) n+1 個の頭から 1 つを選びます。そして、その頭とつながっておらず、かつどこにも刺していない針先 n-1 個のうち 1 つを選びます。選んだ針先を選んだ頭に刺します。

(4) さらに繰り返し、合計 n 回行います。選べる針先の選択肢が 1 つずつ減っていき、n 回目では 1 個のうち 1 個を選んで刺すことになります。

(5) ある 1 本のまち針の頭に他の n 本が全部刺さっているオブジェ（木と呼びたいが根っこが刺さってない……）ができたら操作終了です。

各選択肢の個数を考えると、この操作の方法は全部で (n+1)^n * n! 通りあります。
ただし、同じ形のオブジェがまち針を刺す順番違いで n! 個ずつできるので、オブジェの種類は (n+1)^n 通りです。

そして、このオブジェには n+1 本の各まち針が一番下になるパターンが (n+1)^(n-1) 通りずつ含まれます。
つまり、まち針とみなしていた針山の上に本物のまち針 n 本が全部刺さって、きちんと題意通りの形になっているパターンは (n+1)^(n-1) 通りとなります。


これで「最長数列の総数」も解決したことになります。
あるいは、考え方を流用すれば「まち針の木」の問題に帰着させるまでもなくあっちを解けるかも。
上手い説明ができるかどうか考えてみます。

そして残った No.1051 の恒等式の謎。
組み合わせを用いて証明できたことになりますが、式変形で示せるのかどうか。

DD++さん
> そして残った No.1051 の恒等式の謎。
> 組み合わせを用いて証明できたことになりますが、式変形で示せるのかどうか。

式変形できました。
nCk を C[n,k] と書くことにします。

事前準備その１
C[n,i] * C[n-i,j] = C[n,j] * C[n-j,i]
（証明略）

事前準備その２
f(k)をkのn-1次以下の多項式として、
Σ[k=0...n] C[n,k] * (-1)^k * f(k) = 0
（証明は、「私の備忘録」->「代数学分野」->「二項係数の性質」の中の性質(5)と(28)、あるいは
　平成２３年１１月１９日から２６日にかけてのらいさん・攻略法さん・ａｔ さん・ＦＮさんのやりとり を参照）


それでは本番 (2行目から3行目の置き換えはh=n-k)
Σ[h=0...n] C[n,h] * (h+1)^h * (n-h+1)^(n-h-1)
= Σ[h=0...n] C[n,n-h] * (n-h+1)^(n-h-1) * (h+1)^h
= Σ[k=0...n] C[n,k] * (k+1)^(k-1) * (n-k+1)^(n-k)
= Σ[k=0...n] C[n,k] * (k+1)^(k-1) * ((n+2)-(k+1))^(n-k)
= Σ[k=0...n] C[n,k] * (k+1)^(k-1) * { Σ[m=0...n-k] C[n-k,m] * (n+2)^m * (-1)^(n-k-m) * (k+1)^(n-k-m) }
= Σ[k=0...n] Σ[m=0...n-k] C[n,k] * C[n-k,m] * (n+2)^m * (-1)^(n-k-m) * (k+1)^(n-m-1)
= Σ[m=0...n] Σ[k=0...n-m] C[n,k] * C[n-k,m] * (n+2)^m * (-1)^(n-k-m) * (k+1)^(n-m-1)
= (n+2)^n + Σ[m=0...n-1] Σ[k=0...n-m] C[n,k] * C[n-k,m] * (n+2)^m * (-1)^(n-k-m) * (k+1)^(n-m-1)
= (n+2)^n + Σ[m=0...n-1] Σ[k=0...n-m] C[n,m] * C[n-m,k] * (n+2)^m * (-1)^(n-m) * (-1)^k * (k+1)^(n-m-1)
= (n+2)^n + Σ[m=0...n-1] C[n,m] * (n+2)^m * (-1)^(n-m) * { Σ[k=0...n-m] C[n-m,k] * (-1)^k * (k+1)^(n-m-1) }
= (n+2)^n + Σ[m=0...n-1] C[n,m] * (n+2)^m * (-1)^(n-m) * 0
= (n+2)^n

おお、なるほど、そんな方法で k+1 の指数から k を消せるとは。
これで

> Σ[k=0...n] nCk * (k+1)^k * (n-k+1)^(n-k-1) = (n+2)^n
>
> Σ[k=0...n] nCk * (k+1)^(k-1) * (n-k+1)^(n-k-1) = 2*(n+2)^(n-1)

の上の式は示されましたね。
下の式はりらひいさんの証明の 1 行目（ h をそのまま k に書き換え）と 3 行目を足したものが最終結果の 2 倍になることから得られます。

これらの総和、いつかどこかでまた使うことがあるかもしれないので、証明方法ともども覚えておきたいと思います。
ありがとうございます。

先日の式変形（No.1068）をもう一度眺めていて思ったのですが、次の式

(a+b)^n / a = Σ[k=0...n] C[n,k] * (a+k)^(k-1) * (b-k)^(n-k)

が成り立つんですね。
ただし、 a≠0とします。
計算は先日の3行目～最終行とまったく同様です。
先日の式は、 a=1, b=n+1 の場合にあたります。

a,bは整数に限らず実数でいけるのが面白いところですね。