Problem #88 concerns numbers which can be expressed as both the sum and the product of the numbers in the same set of numbers. The question reads:
Project Euler Problem 88: Product-sum numbers
A natural number, N, that can be written as the sum and product of a given set of at least two natural numbers, {a1, a2, ... , ak} is called a product-sum number: N = a1 + a2 + ... + ak = a1 × a2 × ... × ak.
For example, 6 = 1 + 2 + 3 = 1 × 2 × 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 × 2 = 2 + 2
k=3: 6 = 1 × 2 × 3 = 1 + 2 + 3
k=4: 8 = 1 × 1 × 2 × 4 = 1 + 1 + 2 + 4
k=5: 8 = 1 × 1 × 2 × 2 × 2 = 1 + 1 + 2 + 2 + 2
k=6: 12 = 1 × 1 × 1 × 1 × 2 × 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?
My solution involves investigating the factorizations of numbers and relating them to this property. Here is my solution:
Solution #1: Brute Force Approach
We can observe that for a given number product-sum number n, the product is formed by some factorization of n and enough 1’s that the sum of the numbers in the factorization and the 1’s is equal to n. Thus, to find all product-sum numbers, it suffices to investigate all factorizations of different numbers. Specifically, we can guarantee that for sets of size k, the minimum sum-product number is less than or equal to 2*k because the set k, 2, 1, 1, . . . 1 with k-2 1’s has both a sum and a product of 2*k. Thus, it suffices to check every factorization of every number less than 2*12,000 = 24,000.
We can dynamically get every factorization for every number up to 24,000 by appending each factor to each factorization of smaller numbers. Next, it suffices to check each factorization and store the minimum sum-product number for each possible size of the set. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #88
'''
import time
from math import sqrt
def projectEulerProblemEightyEight(n):
answers = [0]*(n+1)
factorizations = [[],[],[[2]],[[3]],[[2,2],[4]]]
for c in range(5,2*n+1):
factors = []
for x in range(2,int(sqrt(c))+1):
if(c%x==0):
a = factorizations[c/x]
for p in a:
possible = True
for z in p:
if z<x:
possible = False
break
if possible:
t = p[:]
t.append(x)
factors.append(sorted(t))
factors.append([c])
factorizations.append(factors)
for x in range(4,2*n+1):
factors = factorizations[x]
for p in factors:
t = 0
for y in p:
t+=y
if(len(p)>1 and t<=x):
i = len(p)+x-t
if(i<=n):
v = answers[i]
if(v==0):
answers[i] = x
found = []
total = 0
for x in answers:
if x not in found:
total+=x
found.append(x)
return total
start = time.time()
print projectEulerProblemEightyEight(12000)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
7587457
--- 0.840548992157 seconds ---
for input of n = 12000
'''
And with that, we’re done. That approach ran in under a second. There is probably a cleaner way to implement this approach, but I’m satisfied with the results. I may come back to this problem eventually to search for a better solution.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 