Algorithm for solving the minimum integer addition chain problem.

intaddchain.py

#!/usr/bin/env python3

import itertools

# The input to the algorithm.
N = 11

def build_tree(n):
    # This should be `limit = O(log n)`...
    limit = (n // 2) + 1
    # Initialize empty sets for each level.
    V = [set() for i in range(limit)]
    E = [set() for i in range(limit)]
    # Add the root node.
    V[0].add((1, ))
    # Iterate over each level.
    #
    # There are O(log n) levels.
    for i in range(limit - 1):
        # Iterate over each node in the previous level.
        #
        # There are O(i^{i^2}) nodes at level i, or O((log n)^{log^2 n}), or
        # O(2^{log^2 n log log n}).
        for old_node in V[i]:
            # Iterate over each pair of previous values in the path specified
            # by the previous node.
            #
            # There are O(i^2) pairs at level i, or O(log^2 n) pairs.
            for (x, y) in itertools.product(old_node, repeat=2):
                # Only continue creating the tree if we haven't exceeded n, and
                # only if this pair would produce a number greater than the
                # current maximum number in the addition chain.
                if old_node[-1] < x + y <= n:
                    # Create the new node.
                    new_node = old_node + (x + y, )
                    # Add the new node to the next level of vertices, and add
                    # an edge from the previous node to the new node.
                    V[i + 1].add(new_node)
                    E[i + 1].add((old_node, new_node))
    # The returned graph should have vertex set equal to the union of all
    # vertices at all levels and edge set equal to the union of all edges at
    # all levels.
    V = set(itertools.chain(*V))
    E = set(itertools.chain(*E))
    return (V, E)

def minimum_integer_addition_chain(n):
    # Compute the tree.
    (V, E) = build_tree(N)
    # Find the leaf with the addition chain with the smallest length.
    return min((node for node in V if node[-1] == n), key=lambda x: len(x))

if __name__ == '__main__':
    best = minimum_integer_addition_chain(N)
    print('A shortest integer addition chain for {} is {}.'.format(N, best))