Thought Process

My 200th problem!! Anyways onto the problem

Let a(k) denote the smallest the minimal product-sum number for a set of size k

We can see that a(k) ≤ 2k since 1^(k-2) * 2 * k = (k-2)*1 + 2 + k = 2k

This gives us an upper bound for which numbers we actually need to check.

From here I had a simple plan:

1. Initialise an array on length 24,001 to store the minimal product-sum numbers (array[2] = 4, array[3] = 6, etc ...) 

2. Go through the range 4 to 24001, and find all possible factorisation lengths of each number. Therefore I want to make a function PossFact(n) which takes a number n and returns the lengths of all its possible factorisations for example:

   • PossFact(8) = [4, 5] because we can create a ProdSum of length 4 and 5 as shown below
     8 = 4 * 2 * 1 * 1 = 4 + 2 + 1 + 1
     8 = 2 * 2 * 2 * 1 * 1 = 2 + 2 + 2 + 1 + 1

3. Then for each number, we look through its possible factorisation lengths and assign it to the corresponding array value if the number is less than the previous number

4. Return sum(set(array[2:12001]))

Now all that needs to be done is make the PossFact(n) function. I did this using recursion.

My final function was PossFact(og_n, n, Prod, Sum, count)

1. It goes through all the divisors of n, called div, and recursively calls PossFact(og_n, n//div, Prod*div, Sum + div, count + 1)

2. If Prod or Sum is greater than og_n (Original n) then return nothing

3. If Prod = Sum = og_n we have found a Product-Sum number of length count

4. If n = 1, then this means Prod = og_n, which means we have found a Product-Sum number of length (count + (og_n - Sum)) because we can constantly multiply by 1

Not the most efficient algorithm by a long shot but it gets the job done! I once again used the @cache decorator from functools for memoization.

The sequence can be found on OEIS: https://oeis.org/A104173