4.6.3 EVALUATION OF POWERS 449 Theorem B. 1(2A+2B+2C)=A+2, ifA > B > C. (20) Proof. We can, in fact, prove a stronger result that will be of use to us later in this section: A/l addition chains with exactly one small step have one of the following six types (where all steps indicated by . . . represent doublings): Type 1. 1, . . . , 2A, 2A + 2B, . . . , 2A+C+2B+C;A>B>0,C>0. Type 2. 1, . . . , 2A, 2A + 2B, ZA+l + 2B, . . . , 2A+C+1 + ZB-tC; A > B 2 0, c 2 0. Type 3. 1, . . . , 2A, 2A + 2A-1, ZAfl + 2A-1, 2A+2, . . . . 2A+c; A > 0, c 2 2. Type 4. 1, . . . , 2A, 2A +2A-1, 2A+1 +2A, 2A+2, . . . , 2A+C; A > 0, C 2 2. Type 5. 1, . . . , 2A, 2A + 2A-1, . . . , ZAfC + 2A+C-1, 2A+C+1 + 2A+C-2, , 2A+C+D+1 + 2A+C+D–2; A > 0, C > 0, D 2 0. Type 6. 1, . . . , 2A, 2A + 2B, 2A+l, ) _ , C>l . . . , 2A+C.A>B>0 _ . A straightforward hand calculation shows that these six types exhaust all possibilities. (Note that, by the corollary to Theorem A, there are at most three nondoublings when there is one small step; this maximum of three is attained only in sequences of Type 3. All of the above are star chains, except Type 6 whenB 2. 1 (E. de Jonquieres stated without proof in 1894 that I(n) 2 x(n) + 2 when u(n) > 2. The first published demonstration of Theorem B was by A. A. Gioia, M. V. Subbarao, and M. Sugunamma in Duke Math. J. 29 (1962), 481-487.) The calculation of 1(2A + 2B + 2c + aD), when A > B > C > D, is more involved; by the binary method it is at most A + 3, and by the proof of Theorem B it is at least A + 2. The value A + 2 is possible, since we know that the binary method is not optimal when n = 15 or n = 23. The complete behavior when u(n) = 4 can be determined, as we shall now see. Theorem C. If v(n) 2 4 then l(n) 2 x(n) + 3, except in the following cir- cumstances when A > B > C > D and 1(2A + 2B + 2c + 2 ) equals A + 2: Case 1. A-B = C -D. (Example: n = 15.) Case 2. A -B = C -D + 1. (Example: n = 23.) Case 3. A-B = 3, C -D = 1. (Example: n = 39.) Case 4. A-B = 5, B -C = C -D = 1. (Example: n = 135.) Proof. When l(n) = x(n) + 2, there is an addition chain for n having just two small steps; such an addition chain starts out as one of the six types in the proof of Theorem B, followed by a small step, followed by a sequence of nonsmall steps. Let us say that n is special if n = 2A + 2B + 2c + 2O for one of the four
This entry was posted
on Tuesday, July 24th, 2007 at 12:06 pm and is filed under MySQL.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.