Project Euler 88 - Product-sum numbers

Official link:

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:

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)

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:

Interactive Code

Input an integer (yourinput)

Code will output the sum of all minimal product-sum numbers for 2 ≤ k ≤ yourinput