0%

Problem 88


Problem 88


Product-sum numbers

A natural number, $N$, that can be written as the sum and product of a given set of at least two natural numbers, $\{a_1,a_2,\ldots,a_k\}$ is called a product-sum number: $N = a_1 + a_2 + \ldots + a_k = a_1 \times a_2 \times \ldots \times a_k$.

For example, $6 = 1 + 2 + 3 = 1 \times 2 \times 3$.

For a given set of size, $k$, we shall call the smallest $N$ with this property a minimal product-sum number. The minimal product-sum numbers for sets of size, $k = 2$, $3$, $4$, $5$, and $6$ are as follows.

$$
\begin{aligned}
k=2&: 4 = 2 \times 2 = 2 + 2 \\
k=3&: 6 = 1 \times 2 \times 3 = 1 + 2 + 3 \\
k=4&: 8 = 1 \times 1 \times 2 \times 4 = 1 + 1 + 2 + 4 \\
k=5&: 8 = 1 \times 1 \times 2 \times 2 \times 2 = 1 + 1 + 2 + 2 + 2 \\
k=6&: 12 = 1 \times 1 \times 1 \times 1 \times 2 \times 6 = 1 + 1 + 1 + 1 + 2 + 6
\end{aligned}
$$

Hence for $2\le k\le 6$, the sum of all the minimal product-sum numbers is $4+6+8+12 = 30$; note that $8$ is only counted once in the sum.

In fact, as the complete set of minimal product-sum numbers for $2 \le k\le 12$ is $\{4, 6, 8, 12, 15, 16\}$, the sum is $61$.

What is the sum of all the minimal product-sum numbers for $2 \le k \le 12000$?


积和数

若自然数$N$能够同时表示成一组至少两个自然数$\{a_1,a_2,\ldots,a_k\}$的积与和,也即$N = a_1 + a_2 + \ldots + a_k = a_1 \times a_2 \times \ldots \times a_k$,则称之为积和数。

例如,$6$是积和数,因为$6 = 1 + 2 + 3 = 1 \times 2 \times 3$。

给定这一组自然数的数目$k$,满足上述性质的最小$N$值被称为最小积和数。当$k = 2$、$3$、$4$、$5$、$6$时,最小积和数如下所示:

$$
\begin{aligned}
k=2&: 4 = 2 \times 2 = 2 + 2 \\
k=3&: 6 = 1 \times 2 \times 3 = 1 + 2 + 3 \\
k=4&: 8 = 1 \times 1 \times 2 \times 4 = 1 + 1 + 2 + 4 \\
k=5&: 8 = 1 \times 1 \times 2 \times 2 \times 2 = 1 + 1 + 2 + 2 + 2 \\
k=6&: 12 = 1 \times 1 \times 1 \times 1 \times 2 \times 6 = 1 + 1 + 1 + 1 + 2 + 6
\end{aligned}
$$

因此,对于$2 \le k\le 6$,所有的最小积和数之和为$4+6+8+12 = 30$;注意$8$只被计算了一次。

已知对于$2 \le k\le 12$,所有最小积和数构成的集合是$\{4, 6, 8, 12, 15, 16\}$,这些数之和是$61$。

对于$2 \le k \le 12000$,所有最小积和数之和是多少?