[math][Python]自然数の和と積が等しいのはどんなときか？

自然数の和と積が等しいとき
制約
簡単に見つかる解
解の作成方法（$n$が定まってない場合）
$1$が$n-2$個の場合
値の範囲を求める
その他で非典型解を有するケース
最も小さいProduct Sum Numberの求め方
関連記事
関連リンク

自然数の和と積が等しいとき

自然数の和と積が等しい場合、すなわち$$x_1+x_2 + \cdots + x_n = x_1x_2\cdot x_n \tag{*}\label{*}$$について面白い記事を見つけたので、考察してみる。

制約

\eqref{*}において、一般性を失わずに$x_1\leq x_2\leq \cdots \leq x_n$としておく。$n = 1$はtrivialなので、今後は$n\geq 2$としておく。また、\eqref{*}の値を$v$とする。例えば、$n = 3$で$(1, 2, 3)$の場合、$v = 6$となる。

簡単に見つかる解

$x_1=x_2 = \cdots = x_{n-2} = 1, x_{n-1} = 2, x_{n} = n$（以降これを$(1, 1, \cdots, 2, n-2)$と表記する）が\eqref{*}を満たすことはすぐに分かる。これを「基本解」とする。例えば、$n = 5$のとき$(1, 1, 1, 2, 5)$とすると、$v = 10$でこれは\eqref{*}を満たす。しかし、$n = 5$の場合、$(1, 1, 2, 2, 2)$（$v = 8$）および$(1, 1, 1, 3, 3)$（$v = 9$）も\eqref{*}を満たす。これらを「非典型解」としておく。

解の作成方法（$n$が定まってない場合）

例えば、$(1, 2, 2, 4)$を考える。この和は$9$で、積は$16$である。$16-9 = 7$なので、$7$個の$1$を追加して、$(1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 4)$を作ると、この和は$16$で、積も$16$になるので、$$x_1+x_2 + \cdots + x_{11} = x_1x_2\cdots x_{11}$$の解を見つけることができる。

$1$が$n-2$個の場合

$(1, 1, \cdots, 1, a, b)$としておく。ただし、$2\leq a\leq b$である。ここで、以下を示す。

$n-1$が合成数のときのみ、$(1, 1, \cdots, 1, a, b)$は$v < 2n$である非典型解を有する。

証明：\eqref{*}に$(1, 1, \cdots, a, b)$を代入すると、$n-2+a+b =ab$となる。変形して、$(a-1)(b-1) = n-1$である。$2\leq a\leq b$であるから、$a = 2, b = n$のときのみ$n-1$は素数になりうる。$n > 2$のときは基本解を有するし、$n = 2$のときも基本解$(2, 2)$を有する。$n-1$が合成数のとき、$(a-1)(b-1) = n-1$において、$a-1 > 1$かつ$b-1 < n-1$であるような$(a, b)$を選択できる。このとき、$a-1\geq 2$かつ$b-1 = (n-1)/(a-1)\leq (n-1)/2$であるから、$b\leq (n+1)/2 < n$である。したがって、$$\begin{eqnarray}ab & = & (n-2) + a + b \\ & \leq & n-2+2b \\ & \leq & n-2+n+1 \\ & = & 2n-1 \\ & < & 2n\end{eqnarray}$$となる。

値の範囲を求める

例えばコンピュータで\eqref{*}のすべての解を求める場合、範囲を絞り込むことは有用である。$m = x_1+x_2+\cdots + x_n = x_1x_2\cdots x_n$とすると、まず$v\leq 2n$が成り立つ。また、等号が成り立つのは解のうち$1$の個数が$2$個の時のみである。

また、$x_1\leq x_2\leq \cdots \leq x_n$のとき、$x_n\leq n$である。これも、上と同様に解の中の$1$の個数が$2$個の時のみ等号が成り立つ。

これらを示してみる。以下の補題を考える。また、解のうち$1$の個数を$k$、$1$以外の個数を$m$としておく。すなわち、$k + m = n$である。

補題：$m\geq 2, a_j\geq 1$のときのとき、$$(a_1+1)(a_2+1)\cdots (a_m+1)\geq 2(a_1+a_2+\cdots + a_m)$$が成り立つ。

証明は帰納法による（省略）。これを用いると、まず、$x_1=x_2 = \cdots = x_k = 1$なので、$$\begin{eqnarray}\prod_{i=1}^{n}{x_i} & = & \prod_{i=k+1}^{n}{x_i} \\ & = & \prod_{i=k+1}^{n}{((x_i-1)+1)} \\ & = & \prod_{j=1}^{m}{((x_{k+j}-1)+1)}\end{eqnarray}$$である。$j = 1, 2, \cdots, m$に対して、$a_{j} = x_{k+j}-1\geq 1$と置くと、補題により$$\prod_{j=1}^{m}{((x_{k+j}-1)+1)}\geq 2\sum_{j=1}^{m}{(x_{k+j}-1)}$$である。したがって、$$\begin{eqnarray}v & \geq & 2\sum_{j=1}^{m}{(x_{k+j}-1)} \\ & = & 2\sum_{i=1}^{n}{x_i}-2k-2m = 2v-2n\end{eqnarray}$$であり、変形して$v\leq 2n$となる。また、補題で等号が成り立つのは$m = 2$のときのみであるから、基本解でのみ$v = 2n$となることがわかる。

後半の証明は、$m > 2$のとき少なくとも$2$個$1$でない解の要素が存在するので、それを$x_{k+1}, x_n$とすると、$$2x_n\leq \prod_{i=1}^{n}{x_i} = v\leq 2n$$から、$x_n\leq n$を得る。これも、等号が成り立つのは$m = 2$の基本解の時のみである。

その他で非典型解を有するケース

今までの議論から、$n-1$が合成数のときは非典型解を有することがわかるので、$n-1$が素数で、基本解以外の解を有するケースを考察する。簡単なケースとして、$n-3$個が$1$で、$x_{n-2}, x_{n-1}, x_n$が$1$ではないケースを考える。添字が面倒なので、$p, q, r$としておく。\eqref{*}は$$n-3 + p+q+r = pqr$$である。変形して、$$n-1 = pqr-(p+q+r) + 2$$である。ここで、$n-1$は奇数の素数であるから、少なくとも$p, q, r$の内の一つは奇数でなくてはならない。簡単な例として、$(1, 1, \cdots, 2, 2, 2j+1)$を考える。

すなわち、$n-1 = 2\cdot 2\cdot (2j+1)-(2+2+2j+1)+2 = 6j+1$が素数のとき、少なくとも1つの非典型解が存在する。この場合、$v = 8j+4$となる。また、$1$の個数は$k = n-3 = 6j-1$である。

$5$以上の素数はいずれも$6j+1$あるいは$6j+5$の形になるので、さらに探求するには、$n-1$が素数で$6j+5$の形のときを考えれば良い。言い換えれば、まだ見つかっていない唯一の例外的な値は、$6$の整数倍、特に素数より$1$多い倍数の中に隠れているに違いない。

実は、以下の予想が知られている。

典型解のみを有する$n$は、$n = 2, 3, 4, 6, 24, 114, 174, 444$のみである。

2000年半ばの時点で、コンピュータシミュレーションによって$n=316,200,000$までこの予想が正しいことが確認されており、その後さらに、$10,000,000,000$まで確認されている。

最も小さいProduct Sum Numberの求め方

上記の解の作成方法が参考になる。$n$が大きいとき、ほとんどが$1$になる筈。

def prodsum(p, s, c, start):
    k = p - s + c     # product - sum + number of factors
    if k < kmax:
        if p < n[k]: n[k] = p
        for i in range(start, kmax//p*2 + 1):
            prodsum(p*i, s+i, c+1, i)

kmax = 12001
n = [2*kmax] * kmax
prodsum(1, 1, 1, 2)

print(sum(set(n[2:])))

積引く和足す要素数を$k$とすると、$k$個$1$を足したものは\eqref{*}を満たすので、これを基に再帰で探していく。つまり、$p-s$を作っておいて、それが必要な$1$の数。必要な$1$の数に対して、現在の要素数を合計すると、$p-s = 0$になるセットを作ることができる。

探す範囲をstartから始めることで、探索の範囲を狭め、すでに探索した組み合わせを再度探索するのを防いでいる。kmaxは上限の設定。$p$が大きくなると、kmaxの範囲内で有効な数のセットが減少するので、こちらも探索の範囲を狭めることができる。

具体的には、$kmax = 12$で$p = 4$の例を考えてみる。