[seqfan] Re: Error in the example for A003313
franktaw at netscape.net
franktaw at netscape.net
Wed Jul 17 06:57:05 CEST 2013
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>
>
> 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/
More information about the SeqFan
mailing list