  |
https://twitter.com/mathmatsuri
問4
n=6, 8, 10, …, 78, 80の38通りなのですべて書き出せば解けるんだろうが、いかに省エネできるか考えながら進めていきたい。まずは実験しないと始まらない。
小さいnから考えるとパターンが少なすぎるので、大きいnから考えてみる。
n=80のとき(3, 77) (5, 75) (7, 73) (9, 71) (11, 69)…の中から素数のペアを探していけばよい。
nによらず同じように書き出していくことを考えると、まずは素数のリストがあった方がいい。77まででよい。また2は不要。
3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73
n/2よりも小さい素数より、n/2よりも大きい素数の方が多い。計算の回数を減らすために上から順番にnから引き算して素数が残るかどうか判定する。
素数が残る: 73, 67, 61, 43
合成数が残る: 71, 59, 53, 47, 41
pとqがともに素数となる組は(73, 7) (67, 13) (61, 19) (43, 37)とこれらを逆にした8通り。
よってP(80)=8/40=1/5
次、n=78に対して素数リストの上から順番に引き算していく。n/2=39まで。
素数が残る：73, 71, 67, 61, 59, 47, 41
合成数が残る: 53, 43
pとqがともに素数となる組は(73, 5) (71, 7) (67, 11) (61, 17) (59, 19) (47, 31) (41, 37)とこれらを逆にした14通り。よってP(78)=14/39
素数が残るパターンがずいぶん多かった。ところで求めるのはP(n)の最小値。今後分母は減っていくので、組み合わせの数が今のところの最小値の8以上になることが分かった時点でそれ以上計算する意味はなくなる。つまりn/2より大きいpが4つ見つかったらその時点で終了してよい。n/2が素数の時は別で考える必要があるので出てきたら考える。あと合成数が残るパターンは書き残さなくてもよい。
n=76で同様の操作を。
素数が残る：73, 71, 59, 53 ここで終了
n=74
71, 67, 61, 43 ここで終了
n=72
67, 61, 59, 53 終了
n=70のとき67, 59, 53, 47 終了
n=68のとき61, 37の2つだけ。つまりp, qが両方とも素数になるのは(61, 7) (37, 31)とその逆の4通り。
以後はn/2より大きいpが2つ見つかったらその時点で終了してよい。
n=66のとき61, 59 終了
n=62のとき59, 43 終了
n=60のとき53, 47 終了
n=58のとき53, 47 終了
n=56のとき53, 43 終了
n=54のとき47, 43 終了
n=52のとき47, 41 終了
n=50のとき47, 43 終了
n=48のとき41, 37 終了
n=46のとき43, 41 終了
n=44のとき41, 37 終了
n=40のとき37, 29 終了
n=38のとき31, 19(=n/2) p, qが両方とも素数になるのは(31, 7) (19, 19) (7, 31)の3通りなのでP(38)=3/19
P(68)=2/17=3/25.5なのでP(38)>P(68)
n=32のとき29, 19 終了
ここから先はn/2より大きいpが1つ見つかった時点でP(n)=2/(16以下)がP(68)=2/17を超える。
n=22のとき19 終了
n=18のとき13 終了
n=16のとき13 終了
n=8のとき5 終了
n=6のとき(p,q)=(3,3)のみ P(6)=1/3=2/6>2/17=P(68)
-----------------------------------------------------------------
12
