数学夏祭りに挑戦 4日目

数学夏祭りが始まりました。今回を入れてあと7問の予定です。

公式サイト

今回の問題はこちら。

https://twitter.com/mathmatsuri/status/1301429725416488960


順番に計算すればいけそうですが、候補を絞り込みたいところ。

ということで絞り込みをしたいのでこの準備をします。
偶数nに対し、
(n-3)以下の奇数素数の個数をan
n/2bが整数になる最大の整数bをbn
n/2n=cn(この値は奇数になる)
pとn-pがいずれも素数になるn以下の正の奇数の個数をA(n)
とします。(P(n)=2A(n)/nが成り立ちます。)

すると、
nによらずP(n)≧2an-2/n+2
cnが合成数ならP(n) ≧ 2an-2/n+2bn-1+2
cnが素数かつbn≧3なら2an-2/n+2bn-1
が成り立ちます。これを示しましょう。

まずはとりうる(p,n-p)の組を取り出すと、
(1,n-1),(3,n-3),…,(n-1,1)の計(n/2)組となります。
しかし(1,n-1)と(n-1,1)は1が素数でないので考えません。
すなわち残りの(n/2-2)組の中に3以上(n-3)以下の素数が2回ずつ、計2an回出現します。((n-3)以下で考えたのはこのため)
かりに全てに1回ずつ素数が登場したとしてもまだ(2an-(n/2-2))個素数が残りますのでつまり少なくともこの数だけ素数の組ができることになります。
さらにcnが合成数ならば(cn,(2 bn-1) cn), (3cn,(2 bn-3) cn),…, (2 bn-1) cn,cn)の2bn-1組も素数を含みませんのでさらに絞り込めます。
cnが素数でもbn≧2であれば上記の両端2組以外は素数を含みませんので似たような式になります。

これによって示された値で絞り込みをしましょう。

n 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42
A(n)見込み 1 2 3 2 3 4 4 4 5 6 5 4 4 4 5 6 3 4 4
n 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80
A(n)見込み 4 5 10 6 4 4 7 3 4 3 4 4 4 4 8 3 4 4 8

となりました。あとは順に検証しましょう。最小の候補はn=74です。
このとき(3,71)(7,67)(13,61)(31,43)(37,37)…の9組となります。
n=62のときは(3,59)(19,43)(31,31)(43,19)(59,3)の5組となります。
n=58のときは(5,53)(11,47)(17,41)(29,29)…の7組です。
うまくいかなそうなので次は見込みが4のものをみてみます。
n=78のとき(5,73)(7,71)(11,67)(17,61)(19,59)(31,47)(37,41)…の14組です。
n=76のとき(3,73)(5,71)(17,59)(23,53)(29,47)…の10組です。
n=70のとき(3,67)(11,59)(17,53)(23,47)(29,41)…の10組です。
n=68のとき(7,59)(31,37)(37,31)(59,7)の4組です。

すなわち2/12,3/38より4/68が小さいことから、
最小はP(68)=1/17です。

…と長々と計算したはいいものの、表計算ソフトを使ったほうが速かった…

シェアする

  • このエントリーをはてなブックマークに追加

フォローする