Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# hickford/build-numbers-from-atoms.md

Created Aug 18, 2014

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", 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 < 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] best = MinDict() # cost, expression, needs brackets best = (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)
to join this conversation on GitHub. Already have an account? Sign in to comment