Shortest addition chains vs. Knuth's power tree

[Hugo Pfoertner]

SeqFans,

following a suggestion by Paul D Hanna I had computed some rows of
Knuth's power tree as given in TAOCP Vol. 2, 3rd edition, page 464, see
http://www.research.att.com/~njas/sequences/A114622

It is known that the power tree does not always give the minimum number
of multiplications to produce x^n. Knuth says: "But for large enough
values of n the power tree method is not always optimum; the smallest
examples are n=77,154,233."

Searching OEIS produced: "Search: 77,154,233 
I am sorry, but the terms do not match anything in the table."

That there is a increasing number of non-optimal power tree results can
easily be seen from a comparison of
http://www.research.att.com/~njas/sequences/A114623
Number of nodes in row n of the power tree A114622.
1, 1, 2, 3, 5, 9, 15, 26, 43, 78, 134, 238, 415, 731, 1299, 2299, .....
and
http://www.research.att.com/~njas/sequences/A003065
Number of integers with addition chain of length n. 
   1, 2, 3, 5, 9, 15, 26, 44, 78, 136, 246, 432, 772, 1382, 2481,

Those two sequences should have mutual X-refs.

To reproduce the values 77,154,233 and find the next terms the lenghts
of the shortest addition chains are needed. The start of this list is
given in
http://www.research.att.com/~njas/sequences/A003313
A compressed list of the lengths up to 10^24 was computed by Neil Cliftt
and Achim Flammenkamp. A link is given on Achim's web page
http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html

I have included some code to read this list into the program I had made
for the power tree. A comparison of the required number of
multiplications using the power tree and the minimum possible number
from the addition chain computations gives the following results, which
might be candidates for new sequences:

Numbers n such that the smallest possible number of multiplications
required to compute x^n is by 1 less than the number of multiplications
obtained by Knuth's power tree method:
77 154 233 293 308 319 359 367 377 382 423 457 466 551 553 559 571 573
586
616 617 619  623 638 699 713 717 718 734 754 764 813 841 846 849 869 879
905
914 932 1007 1051 1063 1069 1102 1103 1106 1115 1118 1133 1137 1142 1146
1147 1157 1172 1175 1181 1207 1213 1231 1232 1234 1237 1238 1246 1255
1265

Numbers n such that the smallest possible number of multiplications
required to compute x^n is by 2 less than the number of multiplications
obtained by Knuth's power tree method:
8719 17438 28597 34876 54359 56157 57194 57293 59657 60493 67171 69752
71017
71065 75799 78865 100987 108503 108718 110361 112093 112314 112679
113275
114388 114586 115861 119314 119417 120986 133681 133795 134342 138959
139279
139309 139504 140969 141585 142034 142130 144017 148223 157713 157730
157737

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?

Hugo Pfoertner