4.6.3 EVALUATION OF POWERS 453 (Abyss web server) Finally, once the
4.6.3 EVALUATION OF POWERS 453 Finally, once the j and k have been selected for each of the non- ministeps, there are fewer than r2 (33) 0 t ways to choose the j and the k for the ministeps: We select t distinct pairs (jl, kl), . . . , (jt, kt) of indices in the range 0 < kh < j, < r, in fewer than (33) ways. Then for each ministep i, in turn, we use a pair of indices (jh, kh) such that a) jh < i; b) aj, f ok,, is as small as possible among the pairs not already used for smaller ministeps i; c) ai = a$, + ak,, satisfies the definition of ministep. If no such pair (jh, kh) exists, we get no addition chain; on the other hand, any addition chain with ministeps in the designated places must be selected in one of these ways, so (33) is an upper bound on the possibilities. Thus the total number of possible addition chains satisfying (26) is bounded by (31) times (32) times (33), summed over all relevant s, t, U, and U. The proof of Theorem E can now be completed by means of a rather standard estimation of these functions (exercise 18). 1 Corollary. The value of l(n) is asymptotically A(n) + A(n)l for almost all 72. More precisely, there is a function f(n) such that f(n) --+ 0 as n --+ oo, and Pr( (l(n) -A(n) -A(n)/U(n)( 2 f(n)A(n)/AA(n)) = 0. (34) (See Section 3.5 for the definition of this probability Pr .) Proof. The upper bound (25) shows that (34) holds without the absolute value signs. The lower bound comes from Theorem E, if we let f(n) decrease to zero slowly enough so that, when f(n) 2 E, the value N is so large that at most EN values n 5 N have l(n) 5 A(n) + (1 -e)A(n)/AA(n). 1 Star chains. Optimistic people find it reasonable to suppose that I(n) = l*(n); given an addition chain of minimal length l(n), it appears hard to believe that we cannot find one of the same length that satisfies the (apparently mild) star condition. But in 1958 Walter Hansen proved the remarkable theorem that, for certain large values of n, the value of I(n) is definitely less than l*(n), and he also proved several related theorems that we shall now investigate. Hansen s theorems begin with an investigation of the detailed structure of a star chain. This structure is given in terms of other sequences and sets constructed from the given chain. Let n = 2e0 + 2e1 + . . . + 2et, eo > el > . .. > et 2 0, and let 1 = a0 < al < … < a, = n be a star chain for n. If there are d doublings in this chain, we define the auxiliary sequence (35)