Here is my cheating solution that runs in near constant time! (And no, I did not hard code all the results)

The program actually gets the shortest possible chain, so only one input argument is taken. The result for 12345678:

[1, 2, 3, 6, 9, 18, 36, 39, 75, 150, 225, 375, 750, 1500, 3000, 6000, 12000, 24000, 48000, 48225, 96450, 192900, 385800, 771600, 1543200, 3086400, 6172800, 6172839, 12345678]

And the code (Python 3):

import sys
import requests
from bs4 import BeautifulSoup


def getChainHTML(n):
    params = {'index': n, 'cpu': 'fast', 'send': 'Show'}
    url = 'http://wwwhomes.uni-bielefeld.de/cgi-bin/cgiwrap/achim/'\
          'script_lookup_ac?para=FIXED'
    return requests.post(url, data=params)


def parseChainHTML(html):
    chain = []
    soup = BeautifulSoup(html.text)
    for line in str(soup.pre.string).split('\n'):
        parts = line.split()
        # format of a line with a chain link:
        # <id>[...] <link>
        # so there are always at least two elements in the split
        if len(parts) > 1:
            chain.append(int(parts[-1]))

    return chain


if __name__ == "__main__":
    if len(sys.argv) != 2:
        print("Usage: python", sys.argv[0], "<number>")
    else:
        html  = getChainHTML(int(sys.argv[2]))
        chain = parseChainHTML(html)
        print(chain)

Onto the part where I actually contribute to the conversation:

This website has quite a bit of information on addition chains as well as quite an extensive list of reference material. It also contains an input form to calculate the shortest chain for any given number < 2^27, which I shamelessly use in the above code.

So anyone wanting to have a deeper look at the topic of this challenge might find the above site a good starting point.