Return to Answer

import math

def maximum_product_with_sum(total, amount):
    if total < amount:
        return 0
    value, rem = divmod(total, amount)
    sums = [value] * amount
    for i in range(rem):
        sums[i] += 1
    return math.prod(sums)


print(maximum_product_with_sum(14, 7))
print(maximum_product_with_sum(302, 5))

def maximum_product_with_sum(total, count):
    q, r = divmod(total, count)
    return (q+1)**r * q**(count-r)


print(maximum_product_with_sum(14, 7))
print(maximum_product_with_sum(302, 5))

import math

def maximum_product_with_sum(total, amount):
    value, rem = divmod(total, amount)
    sums = [value] * amount
    for i in range(rem):
        sums[i] += 1
    return math.prod(sums)


print(maximum_product_with_sum(14, 7))
print(maximum_product_with_sum(302, 5))

import math

def maximum_product_with_sum(total, amount):
    if total < amount:
        return 0
    value, rem = divmod(total, amount)
    sums = [value] * amount
    for i in range(rem):
        sums[i] += 1
    return math.prod(sums)


print(maximum_product_with_sum(14, 7))
print(maximum_product_with_sum(302, 5))

The comments contain two proofs that a better solution exists.

1. Start with an array of all ones, then repeatedly add one to the smallest number (because that gives the largest percentual increase) until you reach the maximum allowed sum. This can be fomulated as a proof by induction. – Rainer P.

   This can be proven rather simply by using Python, but it can also be proven with a basic formula. If we start with the array \$y, y-1\$ and we have to increase one of the values by one then we can deduce adding one to the \$y-1\$ value results in a larger product.

   $$ yy \gt (y + 1)(y-1)\\ y^2 \gt y^2 - 1\\ $$

   This change works regardless of what the rest of the array is. And so we know adding one to the lowest value always nets the biggest increase.
   I used to not be very good with math, and so a more hands on proof using Python may be easier to follow and agree with.

   import math
   
   
   def inc_1(numbers, pos):
       nums = numbers[:]
       nums[pos] += 1
       return nums
   
   
   def proof(total, amount):
       if total < amount:
           return 0
       numbers = [1] * amount
       for i in range(total - amount):
           d = i % amount
           if d:
               larger = math.prod(inc_1(numbers, d - 1))
               smaller = math.prod(inc_1(numbers, d))
               if smaller > larger:
                   raise ValueError('proof does not hold')
           numbers[d] += 1
       return numbers, math.prod(numbers)
   
   
   print(proof(14, 7))
   print(proof(302, 5))
   

2. if the product contains two factors which differ by more than one, then it is not optimal: Say these are \$x\$ and \$y\$ with \$x < y\$, then replace them by \$x + 1\$ and \$y - 1\$. Now \$(x+1)(y-1) = xy + (y - x - 1) > xy\$. – Carsten S

   ^{Changed to use mathjax}

   With this description the factors are the array of numbers. With this we can start with a random assortment of numbers that total the desired number, and we can continuously improve the product.

   $$ 3, 8\\ 3 < 8\\ 4 \times 7 \gt 3 \times 8\\ 28 \gt 24\\ 5 \times 6 \gt 4 \times 7\\ 30 \gt 24 $$

In all the fastest solution is to just use divmod, and produce the product once.

import math
 

def maximum_product_with_sum(total, amount):
    value, rem = divmod(total, amount)
    sums = [value] * amount
    for i in range(rem):
        sums[i] += 1
    return math.prod(sums)


print(maximum_product_with_sum(14, 7))
print(maximum_product_with_sum(302, 5))

The comments contain two proofs that a better solution exists.

1. Start with an array of all ones, then repeatedly add one to the smallest number (because that gives the largest percentual increase) until you reach the maximum allowed sum. This can be fomulated as a proof by induction. – Rainer P.

   This can be proven rather simply by using Python, but it can also be proven with a basic formula. If we start with the array \$y, y-1\$ and we have to increase one of the values by one then we can deduce adding one to the \$y-1\$ value results in a larger product.

   $$ yy \gt (y + 1)(y-1)\\ y^2 \gt y^2 - 1\\ $$

   This change works regardless of what the rest of the array is. And so we know adding one to the lowest value always nets the biggest increase.
   I used to not be very good with math, and so a more hands on proof using Python may be easier to follow and agree with.

   import math
   
   
   def inc_1(numbers, pos):
       nums = numbers[:]
       nums[pos] += 1
       return nums
   
   
   def proof(total, amount):
       if total < amount:
           return 0
       numbers = [1] * amount
       for i in range(total - amount):
           d = i % amount
           if d:
               larger = math.prod(inc_1(numbers, d - 1))
               smaller = math.prod(inc_1(numbers, d))
               if smaller < larger:
                   raise ValueError('proof does not hold')
           numbers[d] += 1
       return numbers, math.prod(numbers)
   
   
   print(proof(14, 7))
   print(proof(302, 5))
   

2. if the product contains two factors which differ by more than one, then it is not optimal: Say these are \$x\$ and \$y\$ with \$x < y\$, then replace them by \$x + 1\$ and \$y - 1\$. Now \$(x+1)(y-1) = xy + (y - x - 1) > xy\$. – Carsten S

   ^{Changed to use mathjax}

   With this description the factors are the array of numbers. With this we can start with a random assortment of numbers that total the desired number, and we can continuously improve the product.

   $$ 3, 8\\ 3 < 8\\ 4 \times 7 \gt 3 \times 8\\ 28 \gt 24\\ 5 \times 6 \gt 4 \times 7\\ 30 \gt 24 $$

In all the fastest solution is to just use divmod, and produce the product once.

import math

def maximum_product_with_sum(total, amount):
    value, rem = divmod(total, amount)
    sums = [value] * amount
    for i in range(rem):
        sums[i] += 1
    return math.prod(sums)


print(maximum_product_with_sum(14, 7))
print(maximum_product_with_sum(302, 5))