[過去ﾛｸﾞ] 高木くんがアクセプトされるまで見守るスレ ★4 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
896(14): １３２人目の素数さん [sage] 2023/08/06(日)21:44 ID:TaIrWkZJ(1)
5の倍数とrの対応で、nが大きくなると破綻が生じる。
pの中の5の倍数を、rの中の全ての2,3の倍数に対応付けたとして、その残りを5以上の素数とその冪に対応付けていくのだが、nが大きくなるとrの中の素数が不足してくる。
これを示すためには素数定理を使うが、目途は大体n=10^30くらいかな。
899(1): 896 [sage] 2023/08/07(月)16:16 ID:W4kfDz0Z(1)
エクセルに計算させてみたが、
概ね nが10^14を超えると対応付けが破綻するようだ。
901(1): ◆pObFevaelafK [sage] 2023/08/08(火)06:00 ID:RqEEqfe+(1/4)
>>896,900
バグがありましたので修正を行い、n=10^5で正常動作しました。
飛ばすpを偶数(偶数または3の倍数)に限定すべきでした。
以下が修正箇所です。
' For l = 0 To n - 2
' p = n ^ 2 + 1 + l
' If p = Int(p / lPrimes(l1)) * lPrimes(l1) Then
' If pFlags(l) Then
' a = a + 1
' If p = Int(p / 2) * 2 Then
' For l2 = l1 - 1 To 1 Step -1
' If bCombinations(l, l2) Then
' If lSkip = -1 Then
' lSkip = l
' lMax = l2
' Exit For
' ElseIf l2 > lMax Then
' lSkip = l
' lMax = l2
' Exit For
' End If
' End If
' Next
' End If
' End If
' End If
' Next
905(3): 896 [sage] 2023/08/08(火)13:18 ID:vMegdO9X(1/2)
>>896,899
一応、真面目な反例のつもりなんだが、スルーされてっぽくて哀しい。スルーならそれでもいいけど、何かしらコメントをくれ。
少し補足。数値の根拠は、n/log n = n/30 となるようなn。
左辺は、素数定理によるnまでの素数の個数の近似値。
右辺は、nに対して高木対応を成立させるために必要な素数の個数。
n/log n < n/30 となるようなnでは高木対応は成立しない。
素数定理の含む誤差を考慮して、n=10^14 以上であれば、不成立としてよいかと思う。素数の冪の個数は、このあたりのnに対しては、素数の個数の1/100程度なので、素数定理の誤差と一緒に丸めた。
906: 896 [sage] 2023/08/08(火)13:22 ID:vMegdO9X(2/2)
>>905
単に素数って書いちゃったけど、5以上の素数のことです。
908(1): 896 [sage] 2023/08/08(火)14:09 ID:10s3E0nZ(1/2)
>>907
うん、ソフトのバグとかじゃなくて、理論的に不成立の反例。
910(2): 896 [sage] 2023/08/08(火)14:51 ID:o7462/Hs(1)
>>909
2,3,5の最小公倍数です。
任意の長さ30の連続した整数列の中で、5の倍数は6個あります。その6個のうち、2の倍数は3個で、3の倍数は2個です。うち、1個は2と3の公倍数ですが、それを気にせず、別々のものとして対応付けが可能です。(＊)
つまり、5の倍数6個に対して、5個は2と3の倍数として対応付け可能となります。これは、残りの1個は5以上の素数の倍数に対応付けなければならないことを意味します。つまり、nが30個ごとに1個の素数が必要になるということです。
(＊)については長くなるので、必要なら説明します。高木君はわかっていると思いますが。
914(1): ◆pObFevaelafK [sage] 2023/08/08(火)16:24 ID:RqEEqfe+(3/4)
>>896
rが5以上の場合には、n^2<p<n(n+1)でrの倍数になるものの個数を
a(n,r)、1<r<nでrの倍数になるもの個数をb(n,r)とすると
a(n,r)≦b(n,r)+1
という関係があります。そうなので、r≧5の場合にa(n,r)>b(n,r)となる場合には
pのうち2か3の倍数であるものに対して関係を設定せずに飛ばします。
>>912
そういうつもりはありません。
915: 896 [sage] 2023/08/08(火)16:43 ID:10s3E0nZ(2/2)
>>914
回答ありがとうございます。
r=5で、a(n,r)>b(n,r)の場合に限定していただいて構いません。
> pのうち2か3の倍数であるものに対して関係を設定せずに飛ばします。
「関係を設定しない」という意味と、「飛ばす」という意味がわかりません。
pと、2あるいは3の倍数との関係を設定せずに、r=7の場合等の次の処理へ移るということでしょうか？
916(1): ◆pObFevaelafK [sage] 2023/08/08(火)17:10 ID:RqEEqfe+(4/4)
>>896
まず、関係を設定する場合には、素数rの降順でグループにして設定を行います。
例えば>>414でr=11のとき、p=330と341が11の倍数になりますが、rは11しか
設定することができないので、偶数である330を飛ばして[341,11]という関係を設定します。
330は5の倍数なので、r=5で関係を設定することになります。
917(1): 896 [sage] 2023/08/08(火)17:26 ID:Odlzrmr0(1)
>>916
見直したら、対応付けのアルゴリズムが、自分の思ってたのと全然違った。
提示した反例は全部撤回します。
お騒がせしました。ごめんなさい。
928: 896 [sage] 2023/08/14(月)20:41 ID:aFnOLwly(1/4)
>>925
最初の30個のnについては、その通り5に対応させます。次の30個については、5×2、5×3に対応させるわけにはいかないので、（2、3の倍数として既に使用済みなので）5×5に対応させることになります。その次の30個については、5×7となり、以降、5×素数（未使用の）という対応付けが必要になります。つまり、nが30増えるごとに新しい素数が1つづつ必要になっていくという具合です。
932(1): 896 [sage] 2023/08/14(月)21:36 ID:aFnOLwly(2/4)
>>931
>>905 を読んでね。
n>10^14くらいで破綻するはず。
934(1): 896 [sage] 2023/08/14(月)21:47 ID:aFnOLwly(3/4)
>>929
>つぎに
>8,10,12と15,18
>20といれていけば
ここで、20は2の倍数で使用済みなので、入れられるのは25になります。その次は、35、55、65、85、95、•••となります。
937: 896 [sage] 2023/08/14(月)22:08 ID:aFnOLwly(4/4)
>>933
了解
>>934は>>933を見ないで投稿したのでご容赦を。「どうでもよい」というレスを見ていたら反応はしませんでした。
対応付けはオリジナルとは違います。なので、>>917 で撤回しています。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.033s