[seqfan] Re: Error in the example for A003313

[Charles Greathouse]

True. Lexicographically first selection, I suppose.

Charles Greathouse
Analyst/Programmer
Case Western Reserve University


On Wed, Jul 17, 2013 at 12:57 AM, <franktaw at netscape.net> wrote:

> This still doesn't uniquely define the tree. For example, 5 can be added
> under 3 (for the chain 1,2,3,5) or under 4 (for 1,2,4,5). These are equally
> good, to that point. You have to specify how you want to resolve this.
>
>
> Franklin T. Adams-Watters
>
> -----Original Message-----
> From: Charles Greathouse <charles.greathouse at case.edu>
>
> I had a different meaning in mind when I said greedy heuristic. I mean,
> given a tree as in Knuth, add the smallest number which fits in the tree in
> an optimal addition chain, skipping numbers which cannot be added to the
> tree at any position with an optimal addition chain (given the connections
> as they exist).
>
> Charles Greathouse
> Analyst/Programmer
> Case Western Reserve University
>
>
> On Tue, Jul 16, 2013 at 11:03 PM, <franktaw at netscape.net> wrote:
>
>  See
>>
>>
>>  http://codegolf.stackexchange.****com/questions/3177/knuths-****
> power-tree<http://codegolf.**stackexchange.com/questions/**
> 3177/knuths-power-tree<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/
>>
>>
>> ______________________________****_________________
>>
>>
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>>
> ______________________________**_________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
>
> ______________________________**_________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>