[seqfan] Re: Error in the example for A003313

Charles Greathouse charles.greathouse at case.edu
Wed Jul 17 05:41:39 CEST 2013


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>
>
> 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/
>



More information about the SeqFan mailing list