If a problem is hard, try solving a simpler version. Here, how to build n from atoms '1', '+' and '*' with a minimal number of 1's.
Make one observation. Suppose an optimal expression for n contains an expression for some smaller number m. Then that expression for m is optimal. Why? If it weren't, we could replace it with a better one, and so improve the expression for n. Contradiction.
Aha! This means we can attack the problem with dynamic programming. Assuming we have optimal expressions for all numbers smaller than n, we can deduce an optimal expression for n. How? The expression for n must end either with addition (n-1) + 1 or with multiplication d * (n/d) where d divides n. Inserting optimal expressions for n-1 and n/d , we compute the cost of the expressions for n, and choose the cheapest.
In code
best = MinDict() # optimal expression by number
best[1] = (1, "1", False) # cost, expression, needs brackets
for n in range(2,21):
# (n-1) + 1
cost, expression, needs_brackets = best[n-1]
best[n] = (cost+1, "%s+1" % expression, True)
for d in divisors(n):
assert n == d * (n//d)
cost1, expression1, needs_brackets1 = best[d]
cost2, expression2, needs_brackets2 = best[n//d]
if needs_brackets1:
expression1 = "(%s)" % expression1
if needs_brackets2:
expression2 = "(%s)" % expression2
best[n] = (cost1+cost2, "%s*%s" % (expression1, expression2), False)
cost, expression, needs_brackets = best[n]
print "%-2s = %-30s (cost %d)" % (n, expression, cost)
With helpers
class MinDict(dict):
"""Dictionary that will only []-overwrite values with a smaller value."""
def __setitem__(self, key, value):
oldvalue = self.get(key, None)
if oldvalue == None or value < oldvalue:
dict.__setitem__(self, key, value)
from math import ceil, sqrt
def divisors(n):
"""Return proper divisors of n up to sqrt(n)"""
# obviously this can be optimised greatly
return [d for d in range(1, int(ceil(sqrt(n+1)))) if n % d == 0]
Running the algorithm for n up 20
2 = 1+1 (cost 2)
3 = 1+1+1 (cost 3)
4 = (1+1)*(1+1) (cost 4)
5 = (1+1)*(1+1)+1 (cost 5)
6 = (1+1)*(1+1+1) (cost 5)
7 = (1+1)*(1+1+1)+1 (cost 6)
8 = (1+1)*(1+1)*(1+1) (cost 6)
9 = (1+1+1)*(1+1+1) (cost 6)
10 = (1+1)*((1+1)*(1+1)+1) (cost 7)
11 = (1+1)*((1+1)*(1+1)+1)+1 (cost 8)
12 = (1+1)*(1+1)*(1+1+1) (cost 7)
13 = (1+1)*(1+1)*(1+1+1)+1 (cost 8)
14 = (1+1)*((1+1)*(1+1+1)+1) (cost 8)
15 = (1+1+1)*((1+1)*(1+1)+1) (cost 8)
16 = (1+1)*(1+1)*(1+1)*(1+1) (cost 8)
17 = (1+1)*(1+1)*(1+1)*(1+1)+1 (cost 9)
18 = (1+1)*(1+1+1)*(1+1+1) (cost 8)
19 = (1+1)*(1+1+1)*(1+1+1)+1 (cost 9)
20 = (1+1)*(1+1)*((1+1)*(1+1)+1) (cost 9)
Searching for the sequence of costs finds http://oeis.org/A005245
The complexity of an integer n is the least number of 1's needed to represent it using only additions, multiplications and parentheses. This does not allow juxtaposition of 1's to form larger integers, so for example, 2 = 1+1 has complexity 2, but 11 does not ("pasting together" two 1's is not an allowed operation).
If you define your original problem carefully, you can probably attack it using a similar algorithm.