Shortest addition chains vs. Knuth's power tree

[Pfoertner, Hugo]

Hugo Pfoertner wrote:

Within the range of Clifft's and Flammenkamp's table I could not find a
difference of 3. I would be glad if someone could check this somehow
surprising result. If my program turns out to be correct, a very bref
and very hard sequence would therefore be:
Smallest number k, for which Knuth's power tree method to compute x^k
produces n additional multiplications when compared to the minimum
possible number of multiplications:

77, 8719, ???

Is there a chance to get a(3) or even more terms?

-------------------------------------


In the meantime Neill Clift sent me an e-mail saying:

<<
I started a search and found a relatively small value for the next term:

2 77 8719 6475341
>>

I then checked my program and found that I had stopped the search too early.
After fixing that I could confirm Neill's result and found a second n for
which Knuth's power tree produces a result deficient by 3:


     6475341          26          29
    13214509          27          30

I'm not shure if the first term "2" should be included, but the remaining 3
terms definitely seem to be an interesting and fundamental sequence.

Hugo