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, \dots, a_k\}$ is called a product-sum number: $N = a_1 + a_2 + \cdots + a_k = a_1 \times a_2 \times \cdots \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.

$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$
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$?

The function $g(k)$ is defined to be the smallest number $n$ for which $k$ is a product sum number of $n$, i.e. minimum of such $n$ where there exist tags $t$ such that $n=\sum_ {i=1}^kt_i =\prod_ {i=1}^kt_i$.

Writing $n_=k$, we want $n=\sum_{i=1}^{n-k}t_i + k$.
The total number of numbers in $\{t_i\}$ is $k$, but the first few are all 1’s, and so we can write the number of non-1 numbers is $n – k$.
We need to find all possible sets of numbers that multiply to $n – k$ for each $n – k$ separately.
Going through each $n$ and each set for each $n – k$, we insert the potential $k$ if it is smaller than the current $g(k)$ if one exists.

In python:
“`python
def solve(limit):
# initialize g(k) for 2 <= k <= limit g = [0] * (limit + 1) max_k = 0 # n is the product/sum of the elements of the set for n in range(2, 2 * limit + 1): # try every partition of n for split in partition(n): # calculate k: add the number of 1's and the size of the split k = n - sum(split) + len(split) if k > limit: continue
# if g[k] has not been set yet, set it to n
# or if n is smaller than the current g[k], update it
if g[k] == 0 or g[k] > n:
g[k] = n
max_k = max(max_k, k)
return sum(set(g[2:max_k + 1]))

def partition(n):
# yields every partition of n
# a partition is represented as a non-increasing list of numbers that sum to n
partition_helper(n, n, [], yield)

def partition_helper(n, max_val, current, yield):
# yield the ‘current’ list, and every non-length-increasing list that can be appended to it
if n == 0:
yield current
for i in range(min(max_val, n), 0, -1):
partition_helper(n – i, i, current + [i], yield)
“`
Running `solve(12000)` will return the sum you are looking for.

Note: Since the brute force nature of these nested loops is very time-consuming, efficiency improvements can be made by minimizing the number of iterations. The partition function is key here, which makes a list of all ways to express an integer $n – k$ as the product of integers greater than 1 (since the 1’s are already accounted for). It starts by trying to make as many factors as possible be equal to 2, then gradually increases the smallest factor until it reaches $n – k$, while decreasing the number of times that factor appears. For instance, for $n – k = 20$, the sequence of tuples the function yields is: (2, 2, 2, 2, 2, 2, 2, 2, 2, 2), (2, 2, 2, 2, 2, 2, 2, 2, 3), …, (20). It stops as soon as it hits a tuple where the first element – the smallest factor – times the length of the tuple – the number of factors – exceeds $n$, because it wouldn’t be possible to add enough 1’s to the tuple to make the sum equal to $n$.

The implementation is designed to be easy to understand, and gives the correct result relatively quickly even with the relatively large input of 12000. However, it may be possible to improve the performance further with more advanced techniques, such as by generating the partitions in lexicographically descending order and skipping duplicate partitions.

More Answers: