Factorization

Project Euler 88: Exploring minimal product-sum numbers for sets of different sizes.

Project Euler 88: Exploring minimal product-sum numbers for sets of different sizes.

Based on the number of people who have solved Problem 88 of Project Euler it seems to be a rather difficult problem. At the time of writing 2661 people have solved this problem. This post should show you that in reality the problem is not that difficult. That being said I spent the majority of a week before I got the right insights to solve it. The problem reads

A natural number, N, that can be written as the sum and product of a given set of at least two natural numbers, {a1a2, … , ak} is called a product-sum number: N = a1 + a2 + … + ak = a1 x a2 x … x ak.

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

Okay, that doesn’t sound too easy does it? Well I guess you wouldn’t be here if it was too easy. If you don’t want the full solution but just some insights into the maths you need to solve it, just read the first part. Continue reading →

Posted by Kristian in Project Euler, 18 comments