Product-sum Numbers¶

For any set size $k$, we can always construct a product-sum number as $1+1+1+\cdots+1+2+k = 2k$, where there are $k-2$ 1s in the sum and product. $2k$ is not necessarily the minimal product-sum number for $k$ - nevertheless, it serves as an upper bound.

In [1]:
limit = 12000
mins = {k: 2*k for k in range(2, limit + 1)}
mins[1] = 1

If we have a set of numbers with product $p$ and sum $s$, we can construct a product-sum number by simply adding 1s to the set until $p = s$. With this fact, we can simply run a search over all the sets of factors and compute the product and sum of each, stopping if either exceeds 24000. Instead of tracking each set, we only need to keep track of the product, sum, and number of non-one elements in each set.

In [2]:
from itertools import count

visited = set()
stack = [(n, n, 1) for n in range(2, limit + 1)]
while stack != []:
    # m: number of non-one elements
    p, s, m = stack.pop()
    if (p, s, m) in visited:
        continue
    visited.add((p, s, m))
    
    m += 1
    for x in count(2):
        product = p * x
        if product > 2 * limit:
            break
            
        total = s + x
        if total > 2 * limit:
            break
            
        k = product - total
        if k + m > limit:
            break

        mins[k + m] = min(mins[k + m], product)
        
        stack.append((product, total, m))

After the search ends, the dictionary will hold the minimal product-sum number for each value of $k$.

In [3]:
del mins[1]
sum(set(mins.values()))
Out[3]:
7587457

Relevant sequences¶

  • Minimal product-sum numbers: A104173
  • Set sizes $k$ with a minimal product-sum number of $2k$: A033179

Copyright (C) 2025 filifa¶

This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license and the BSD Zero Clause license.