Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

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.

import math
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[0] < oldvalue[0]:
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]
best = MinDict() # cost, expression, needs brackets
best[1] = (1, "1", False)
for n in range(2,31):
# f(n-1) + 1
cost, expression, needs_brackets = best[n-1]
best[n] = (cost+1, "%s+1" % expression, True)
for d in divisors(n):
# f(d) * f(n//d)
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.