[seqfan] Error in the example for A003313

[Rob Arthan]

The example in A003313 "Length of shortest addition chain for n" is incorrect (or, at best, very misleading). It gives an ASCII-art picture of a tree with positive integer node labels and says that a(n) is the depth of the node with label n in the tree.  This is taken from Knuth, but the statement is claiming much more than Knuth does. In fact, it is not possible to extend this tree to include.all values of n. I just conjectured this while thinking about a Project Euler problem and soon found Achim Flammenkamp's nice web page at:

http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html

As he says, it is not possible to construct a tree that includes chains for 43, 77 and 149. To see why this is, let me enumerate the optimal addition chains for these numbers:

1, 2, 3, 5, 10, 20, 23, 43
1, 2, 3, 5, 10, 20, 40, 43
1, 2, 4, 8, 9, 17, 26, 43
1, 2, 4, 8, 9, 17, 34, 43

1, 2, 4, 5, 9, 18, 36, 41, 77
1, 2, 4, 5, 9, 18, 36, 72, 77
1, 2, 4, 8, 9, 17, 34, 43, 77
1, 2, 4, 8, 9, 17, 34, 68, 77

1, 2, 4, 5, 9, 18, 36, 72, 77, 149
1, 2, 4, 5, 9, 18, 36, 72, 144, 149
1, 2, 4, 8, 16, 17, 33, 66, 83, 149
1, 2, 4, 8, 16, 17, 33, 66, 132, 149

The parent relation in the tree corresponds the predecessor relation in the chains and not all combinations of the chains are compatible. E.g., if you choose the first chain for 43 you cannot choose the first chain for 149, because they disagree about the predecessor of 5. Now, the chains for 43 are only compatible with the chains for 77 that include 17 (by considering the predecessors of 5 and 9). But the chains for 77 that include 17 are incompatible with any of the chains for 149 (by considering the predecessors of 9 and 17). So it is not possible to extend the tree to include 43, 77 and 149.

As the ASCII-art tree is quite nice, perhaps it would be best to weaken the claim in the example to say any value of a(n) for n in the picture can be calculated as stated, but that it is not possible to extend the tree indefinitely.

Regards,

Rob.