450 ARITHMETIC 4.6.3 cases listed in the theorem. (Web site builder)
450 ARITHMETIC 4.6.3 cases listed in the theorem. We can obtain addition chains of the required form for each special n, as shown in exercise 13; therefore it remains for us to prove that no chain with exactly two small steps contains any elements with V(Q) 2 4 except when a, is special. Let a counterexample chain be an addition chain with two small steps such that V(a,) 2 4, but a, is not special. If counterexample chains exist, let 1 = a0 < al < ... < a7 = n be a counterexample chain of shortest possible length. Then step T is not a small step, since none of the six types in the proof of Theorem B can be followed by a small step with v(n) > 4 except when n is special. Furthermore, step r is not a doubling, otherwise ao, . . . , a7-l would be a shorter counterexample chain; and step T is a star step, otherwise ao, . . . , arP2, a, would be a shorter counterexample chain. Thus ar = a7-1 + (h–k, k 2 2; and x(a,) = x(a,-,) + 1. (21) Let c be the number of carries that occur when aTPl is added to ar-k in the binary number system by Algorithm 4.3.1A. Using the fundamental relation V(&) = v(a,-l) + v(hk) -c, (22) we can prove that step r -1 is not a small step (see exercise 14). Let m = x(a,-1). Since neither r nor r -1 is a small step, c 2 2; and c = 2 can hold only when a,-l 2 2m + 2m-1. Now let us suppose that T - 1 is not a star step. Then r -2 is a small step, and ao, . . . , ar-s, a,-1 is a chain with only one small step; hence v(a,-l) 2 2 and v(a,-2) 5 4. The relation (22) can now hold only if V(a,) = 4, v(a,-1) = 2, k = 2, c = 2, v(a,-2) = 4. From c = 2 we conclude that aTAl = 2m + 2m-1; hence ao, al, . . . , arP3 = 2m-1 + 2m-2 is an addition chain with only one small step, and it must be of Type 1, so a, belongs to Case 3. Thus r -1 is a star step. Now assume that aTPl = 2ta,-k for some t. If v(a,-l) 5 3, then by (22), c = 2, k = 2, and we see that a, must belong to Case 3. On the other hand, if v(a,-1) = 4 then aTYl is special, and it is easy to see by considering each case that a, also belongs to one of the four cases. (Case 4 arises, for example, when a,-1 = 90, ar-k = 45; or aTAl = 120, ar-k = 15.) Therefore we may conclude that a,-l # 2ta,-k for any t. We have proved that aTPl = arP2 + arYq for some q > 2. If k = 2, then q > 2, and ao, al, . . . , ar–2, 2a,-2, 2a7-2 + arPq = a, is a counterexample sequence in which k > 2; therefore we may assume that k > 2. Let us now suppose that x(&-k) = m -1; the case X(&-k) < m -1 may be ruled out by similar arguments, as shown in exercise 14. If k = 4, both T - 2 and T - 3 are small steps; hence aTF4 = 2m-1, and (22) is impossible. Therefore k = 3; step T - 2 is small, v(a,-3) = 2, c = 2, a,-l 2 2m + 2m-1, and v(a,-1) = 4. There must be at least two carries when a+2 is added to a7-l -arms; hence v(a,-2) = 4, and ar-z (being special and 2 farPI) has the form 2m-1 + 2m-2 + 2d+1 + 2d for some d. Now arPl is either 2m + 2m+1 + 2d+ + 2d or 2m + 2m- + 2d+2 + Zd+ , and in both cases arP3 must be 2m-1 + 2m-2, so a7 belongs to Case 3. I