#!/usr/bin/python
#I A008928
#S A008928 1,1,1,2,3,6,10,21,38,77,144,293,563,1131,2205,4434,8711,17466,34506,
#T A008928 69169,137247,274677,546081,1093217,2177556,4356756,8688370,17381926,
#U A008928 34691608,69394626,138578144,277197191,553794526,1107654097,2213527055
#N A008928 Number of increasing sequences of addition chain type with
#          maximal element n.
#o A008928 Python program by Don Reble (djr(AT)nk.ca), 2007 Jan 03


# This function says whether the addition chain "chain"
# can be extended by "next".
def canExtend(chain, next):
    for elem in chain:
        if (next - elem) in chain:
            return True
    return False



# This function counts the addition chain "chain".
# Then it extends the chain in all possible ways (up to MaxN)
# and recurses.
def countAndExtend(chain):
    last = chain[0]             # They're in reverse order, eh?
    ChainQuants[last] += 1      # count the chain
    for next in range(last+1, MaxN+1):      # each potential extension
        if canExtend(chain, next):
            countAndExtend([next] + chain)  # each actual extension



MaxN = 23                       # count chains up to MaxN
                                # It's really slow, if MaxN > 25.
ChainQuants = [0] * (MaxN+1)    # chain quantities
countAndExtend([1])             # compute
del ChainQuants[0]              # remove zeroth element
print ChainQuants