[seqfan] Re: Error in the example for A003313

[Rob Arthan]

Knuth gives an explicit rule for constructing the "power tree". 1 is the root of the tree (Vol. 2., Sec. 4.6.3, Ex. 5). When all nodes of depth k have been constructed, the nodes at depth k+1 are constructed working from left to right. If the path from the root to n is a_1 = 1, a_2, …., a_k -= n, the children of n are obtained from the list n + a_1, n + a_2, …, n + a_k = 2n by deleting entries that have already been put in the tree.  

I see now that Knuth's Ex. 12 on this topic is to prove that a tree of optimal additional chains cannot be extended indefinitely to include all positive integers. To my surprise he rates this as a simple exercise (M10). It turns out that the proof he has in mind is simple given a harder fact that he has already proved. This proof doesn't give a good bound on the smallest N (namely 149) such that a tree giving optimal addition chains for all n with 1 <= n <= N cannot be constructed.

Regards,

Rob.

On 17 Jul 2013, at 06:03, Charles Greathouse <charles.greathouse at case.edu> wrote:

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