[seqfan] Re: Error in the example for A003313

[franktaw at netscape.net]

Thanks; that answers my question right in the abstract (affirmatively).

Franklin T. Adams-Watters

-----Original Message-----
From: allouche <allouche at math.jussieu.fr>

Hi

There is a free available preprint of Zantema's paper at
http://igitur-archive.library.uu.nl/math/2006-1214-202352/zantema_89_minimizing_sums.pdf

best wishes
jp


franktaw at netscape.net a écrit :

> 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/
>
>  _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/



_______________________________________________

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