[seqfan] Re: Error in the example for A003313

[franktaw at netscape.net]

See

http://codegolf.stackexchange.com/questions/3177/knuths-power-tree

This tree, which uses a greedy heuristic (there isn't a unique greedy 
heuristic for this problem) generates a tree (the Power Tree) which 
provides something reasonably close to optimal addition chains for all 
n, but not actually optimal for all. (If I remember correctly, 74 is 
the first exception). A list of those numbers whose position in this 
tree does not correspond to an optimal addition tree for it would be a 
good addition to the database.

A related question, on A008057: "Smallest sum of an addition chain for 
2n+1." Does anyone have access to the reference there -

H. Zantema, Minimizing sums of addition chains, J. Algorithms, 12 
(1991), 281-307. -

Does he prove that for 2n, you always get a minimal sum by generating 
the chain for n and then adding a doubling step? This is a question I 
have wondered about for some time.

Franklin T. Adams-Watters

-----Original Message-----
From: Charles Greathouse <charles.greathouse at case.edu>

There are different ways to extend the tree. I suppose a sequence for 
the
tree using the greedy heuristic wouldn't be out of order, though.

Charles Greathouse
Analyst/Programmer
Case Western Reserve University

On Tue, Jul 16, 2013 at 6:58 PM, Max Alekseyev <maxale at gmail.com> wrote:

> On Tue, Jul 16, 2013 at 6:25 PM, Rob Arthan <rda at lemma-one.com> wrote:
> > 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.
>
> What exactly does Knuth state about this tree?
>
> > In fact, it is not possible to extend this tree to include.all 
values of
> n.
>
> Then it would make sense to add the sequence (if it is not yet in
> OEIS) of those n that appear in this tree as well as the sequence of
> those n that are missing in the tree.
>
> Regards,
> Max
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>

_______________________________________________

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