text: # minSumProduct[k] is the smallest positive integers that can be written as both a sum and a product of the same collection of k positive integers.
  # For example, minSumProduct[3] = 6 because 6 = 1 + 2 + 3 = 1 * 2 * 3, and this is the minimum possible number for 3 terms.
  #
  # For all k >= 2:
  # - minSumProduct[k] > k because 1 + ... + 1 (with k terms) = k, which is the minimum sum of k positive integers,
  #   but the product is 1 which is unequal to k, so k is not a valid solution.
  # - minSumProduct[k] <= 2k because 1 + ... + 1 + 2 + k (with k terms in total) = (k - 2) + 2 + k = 2k. The product is 2k, which equals the sum.
  #   Since this is one achievable solution, the minimum solution must be no larger than this.
  # - Aside: minSumProduct[k] is not a prime number. Suppose minSumProduct[k] = p, where p is prime. Then p can only be factorized as p, p * 1, p * 1 * 1, etc.
  #   So whenever the factorization has more than one term, the sum exceeds p, which makes it unequal to the product.
  #
  # Therefore we need to consider all numbers from 2 to LIMIT*2 and factorize them in all possible ways to find all the relevant solutions.
  def problem088():
      """
  
  
      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], ... , a[k]} is called a
         product-sum number: N = a[1] + a[2] + ... + a[k] = a[1] × a[2] × ... ×
         a[k].
  
         For example, 6 = 1 + 2 + 3 = 1 × 2 × 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 × 2 = 2 + 2
         k=3: 6 = 1 × 2 × 3 = 1 + 2 + 3
         k=4: 8 = 1 × 1 × 2 × 4 = 1 + 1 + 2 + 4
         k=5: 8 = 1 × 1 × 2 × 2 × 2 = 1 + 1 + 2 + 2 + 2
         k=6: 12 = 1 × 1 × 1 × 1 × 2 × 6 = 1 + 1 + 1 + 1 + 2 + 6
  
         Hence for 2≤k≤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≤k≤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≤k≤12000?
      """
      LIMIT = 12000
      minsumproduct = [None] * (LIMIT + 1)
  
      # Calculates all factorizations of the integer n >= 2 and updates smaller solutions into minSumProduct.
      # For example, 12 can be factorized as follows - and duplicates are eliminated by finding only non-increasing sequences of factors:
      # - 12 = 12. (1 term)
      # - 12 = 6 * 2 * 1 * 1 * 1 * 1 = 6 + 2 + 1 + 1 + 1 + 1. (6 terms)
      # - 12 = 4 * 3 * 1 * 1 * 1 * 1 * 1 = 4 + 3 + 1 + 1 + 1 + 1 + 1. (7 terms)
      # - 12 = 3 * 2 * 2 * 1 * 1 * 1 * 1 * 1 = 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1. (8 terms)
      def factorize(n, remain, maxfactor, sum, terms):
          if remain == 1:
              if sum > n:  # Without using factors of 1, the sum never exceeds the product
                  raise AssertionError()
              terms += n - sum
              if terms <= LIMIT and (
                      minsumproduct[terms] is None or n < minsumproduct[terms]
              ):
                  minsumproduct[terms] = n
          else:
              # Note: maxfactor <= remain
              for i in range(2, maxfactor + 1):
                  if remain % i == 0:
                      factor = i
                      factorize(
                          n,
                          remain // factor,
                          min(factor, maxfactor),
                          sum + factor,
                          terms + 1,
                      )
  
      for i in range(2, LIMIT * 2 + 1):
          factorize(i, i, i, 0, 0)
  
      # Eliminate duplicates and compute sum
      ans = sum(set(minsumproduct[2:]))
      return ans
  
  
  if __name__ == "__main__":
      print(problem088())
  