素数

質問

互いに異なる10個の自然数があり、任意の9個を選んで和をとると
素数になる。
こんな、10個の自然数の組で10個の数の和がもっとも小さくなるものを
探すプログラムを作成する。

2週間ほど考えているんですがわかりません。
よろしくお願いします。

回答No.2

Werner

> S-j = a+b+c+d+e+f+g+h+i+0 = p0
> →　j = S-p0
訂正。分かると思いますが
S/9-j = a+b+c+d+e+f+g+h+i+0 = p0
→　j = S/9-p0
です。

回答No.1

Werner

ちょっと今時間がないので今思いついた考え方だけをそのまま書きます。
（なので、もしかしたら間違っているかもしれません。）

> 互いに異なる10個の自然数があり、任意の9個を選んで和をとると素数になる。
この条件より以下の10個の等式が成立する。
(a～jは互いに異なる10個の自然数、p0～p9は素数)
a+b+c+d+e+f+g+h+i+0 = p0
a+b+c+d+e+f+g+h+0+j = p1
a+b+c+d+e+f+g+0+i+j = p2
a+b+c+d+e+f+0+h+i+j = p3
a+b+c+d+e+0+g+h+i+j = p4
a+b+c+d+0+f+g+h+i+j = p5
a+b+c+0+e+f+g+h+i+j = p6
a+b+0+d+e+f+g+h+i+j = p7
a+0+c+d+e+f+g+h+i+j = p8
0+b+c+d+e+f+g+h+i+j = p9

以上の等式について両辺の和を取ると、
9*(a+b+c+d+e+f+g+h+i+j) = p0+p1+p2+p3+p4+p5+p6+p7+p8+p9 = S
(便宜上、和をSとおく)

9*(a+b+c+d+e+f+g+h+i+j)は9の倍数であるからSも9の倍数である。

ここで、仮に
> p0+p1+p2+p3+p4+p5+p6+p7+p8+p9 = S(9の倍数)
を満たすSと素数p0～p9の組が見つかったとしよう。
すると、自然数jは以下のようにして求められる。
S-j = a+b+c+d+e+f+g+h+i+0 = p0
→　j = S-p0
同様に、他の自然数a～iも求められる。

よって、この問題を解くには、
> p0+p1+p2+p3+p4+p5+p6+p7+p8+p9 = S(9の倍数)
を満たす素数の組を見つければよい。

この素数の組を見つけるのは、
素数の集合から和がSになるように部分集合を選ぶという
部分和問題(SUBSET SUM Problem)として解けるのではないかと思います。
（Sを9,18,27と増やしつつ、部分集合が9個の素数になるような解が存在するか確かめていく。）

お礼

回答ありがとうございました。
これを元に一度自分でかみくだきながらプログラム化してみます。
ありがとうございました。