Project Euler Problem 88 Solution

Project Euler Problem 88 Statement

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, \dots, a_k\}$ is called a product-sum number: $N = a_1 + a_2 + \cdots + a_k = a_1 \times a_2 \times \cdots \times a_k$.

For example, $6 = 1 + 2 + 3 = 1 \times 2 \times 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 \times 2 = 2 + 2$
$k=3$: $6 = 1 \times 2 \times 3 = 1 + 2 + 3$
$k=4$: $8 = 1 \times 1 \times 2 \times 4 = 1 + 1 + 2 + 4$
$k=5$: $8 = 1 \times 1 \times 2 \times 2 \times 2 = 1 + 1 + 2 + 2 + 2$
$k=6$: $12 = 1 \times 1 \times 1 \times 1 \times 2 \times 6 = 1 + 1 + 1 + 1 + 2 + 6$

Hence for $2 \le k \le 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 \le k \le 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 \le k \le 12000$?

Solution

1. Core Concept: Minimal Product-Sum Numbers

For a given set of factors (other than the 1’s that can be padded later), we define:

Product (prod): The multiplication of the factors.
Sum (total): The sum of the factors.
Count (count): The number of factors used.

Using these, we compute:

$$ k = prod - total + count $$

This tells us the effective number of factors (including extra 1’s) for the current combination. For example, if you have factors that multiply to 4 and add up to 3 (with count = 2), then:

$$ k = 4 - 3 + 2 = 3 $$

This means that by adding one more 1 (since 1 does not change the product but adds 1 to the sum) you can have a valid product-sum representation.

2. The Recursive Function: `find_product_sum`

Parameters:

prod: Current product of the selected factors.
total: Current sum of the selected factors.
count: Number of factors chosen so far.
start: The smallest factor that can be chosen next; this ensures factors are in non-decreasing order.

Steps within the function:

Calculate k:

$$ k = prod - total + count $$

This gives the effective number of factors including any additional 1’s needed.
Check and Update:

If k < k_max, update the global list min_prod:
```
min_prod[k] = min(min_prod[k], prod)
```
This records the smallest product (candidate minimal product-sum number) found for that particular k.
Recursive Exploration:

The loop:
```
for i in range(start, (k_max // prod) * 2 + 1):
```
iterates over possible factors. For each candidate factor i, the function recurses with updated values:
- New product: prod * i
- New sum: total + i
- New count: count + 1
- New starting factor: i (to maintain non-decreasing order)

3. Main Function and Initialization

Input and Global Setup:

In the main() function, the user is prompted to enter the maximum k value. For example, if the user enters 12, then internally:

$$ k\_max = 12 + 1 \quad (\text{so } k\_max \text{ becomes } 13) $$

A list min_prod is initialized with a high placeholder value (here, 2 * k_max) for every index.

Starting the Recursion:

The initial call:

find_product_sum(1, 1, 1, 2)

sets the starting values with a product and sum of 1 (representing neutral elements) and a count of 1. The starting factor is 2 because we begin considering factors from 2 upward.

Final Step:

After recursion completes, the script collects the minimal product-sum numbers for k values 2 through 12 (ignoring indices 0 and 1) using set(min_prod[2:]) to ensure uniqueness, and then sums and prints these values.

Walkthrough for K_max = 12

Let’s walk through part of the recursion when the user enters 12 (making k_max = 13):

Initial Call:
```
find_product_sum(1, 1, 1, 2)
```
Calculation: $ k = 1 - 1 + 1 = 1 $

Although $ k = 1 $ here, we are interested in $ k \geq 2 $.

The loop then runs for $ i $ from 2 to (13 // 1) * 2 + 1 = 27 (i.e., $ i $ from 2 to 26).
First Level – Choosing $ i = 2 $:
```
find_product_sum(2, 3, 2, 2)
```
Calculation: $ k = 2 - 3 + 2 = 1 $

The loop runs for $ i $ from 2 to (13 // 2) * 2 + 1 = 13.
Second Level – Continuing with $ i = 2 $ Again:
```
find_product_sum(4, 5, 3, 2)
```
Calculation: $ k = 4 - 5 + 3 = 2 $

Update: min_prod[2] = min(min_prod[2], 4) changes min_prod[2] from 26 to 4.

The loop here runs for $ i $ from 2 to (13 // 4) * 2 + 1 = 7.
Exploring Another Branch at Second Level:

Within the same call (find_product_sum(4, 5, 3, 2)), if we choose $ i = 3 $:
```
find_product_sum(12, 8, 4, 3)
```
Calculation: $ k = 12 - 8 + 4 = 8 $

Update: min_prod[8] = min(min_prod[8], 12) sets min_prod[8] to 12.
Other Branches:

The recursion continues exploring various combinations. For example:
- A branch using three factors of 2 (i.e. factors 2, 2, 2) might yield:
  Product = 8, Sum = 7 (considering the initial 1 and the three 2’s), Count = 4, so: $$ k = 8 - 7 + 4 = 5 $$ This updates min_prod[5] to 8 if it is the smallest found for $ k = 5 $.
- Another branch combining 2 and 3 in a different order will update a different $ k $ value accordingly.
After Recursion Completes:

The list min_prod now holds the smallest product-sum number for each $ k $ from 2 to 12. Although some minimal numbers may be shared between different $ k $ values, the final step uses a set to ensure uniqueness and sums these unique numbers.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 88

HackerRank Project Euler 88: What is the sum of all the minimal product-sum numbers for 2 ≤ k ≤ N (10 ≤ N ≤ 20,000)?

Python Source Code

def find_product_sum(prod, total, count, start):
    k = prod - total + count
    if k < k_max:
        min_prod[k] = min(min_prod[k], prod)
        for i in range(start, (k_max // prod) * 2 + 1):
            find_product_sum(prod * i, total + i, count + 1, i)
k_max = int(input())+1
min_prod = [2*k_max] * k_max
find_product_sum(1, 1, 1, 2)
print(sum(set(min_prod[2:])))