[seqfan] Re: Error in the example for A003313

[franktaw at netscape.net]

I think that's the intended meaning of that comment - that this applies 
for the n in the tree, not that the tree can be indefinitely extended. 
Obviously, it is ambiguous, and should be clarified.

Franklin T. Adams-Watters

-----Original Message-----
From: Rob Arthan <rda at lemma-one.com>

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.



_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/