Photoshop web design - 458 ARITHMETIC 4.6.3 Some conjectures. Although it was
458 ARITHMETIC 4.6.3 Some conjectures. Although it was reasonable to guess at first glance that I(n) = l*(n), we have now seen that this is false. Another plausible conjecture [first made by A. Goulard, and supposedly proved by E. de JonquiBres in l lnterm. des Math. 2 (1895), 125-1261 is that 1(2n) = I(n) + 1; a doubling step is so efficient, it seems unlikely that there could be any shorter chain for 2n than to add a doubling step to the shortest chain for n. But computer calculations show that this conjecture also fails, since 1(191) = 1(382) = 11. (A star chain of length 11 for 382 is not hard to find; e.g., 1, 2, 4, 5, 9, 14, 23, 46, 92, 184, 198, 382. The number 191 is minimal such that I(n) = 11, and it seems to be very difficult to prove by hand that 1(191) > 10; the computer s proof of this fact, using a backtrack method that will be sketched in Section 7.2.2, involved a detailed examination of 948 cases.) The smallest four values of n such that l(2n) = l(n) are n = 191, 701, 743, 1111; E. G. Thurber proved in Pacific J. Math. 49 (1973), 229-242, that the third of these is a member of an infinite family of such n, namely 23 . 2k + 7 for all k 2 5. It seems reasonable to conjecture that l(2n) 2 I(n), but even this may be false. Kevin R. Hebb has shown that l(n) -I(mn) can get arbitrarily large, for all fixed integers m not a power of 2 [Notices Amer. Math. Sot. 21 (1974), A-2941. The smallest case in which l(mn) < l(n) is 1((213 + 1)/3) = 15. Let C(T) be the smallest value of n such that l(n) = r. It seems to be most difficult to compute l(n) for these values of n. We have the following table: r c(r) r c(r) r c(r) 1 2 7 29 13 607 2 3 8 47 14 1087 3 5 9 71 15 1903 4 7 10 127 16 3583 5 11 11 191 17 6271 6 19 12 379 18 11231 For r 5 11, the value of c(r) is approximately equal to c(r -1) + c(r -2), and this fact led to speculation by several people that c(r) grows like the function @ ; but the result of Theorem D (with n = c(r)) implies that r/lgc(r) + 1 as n + co. [See E. G. Thurber, Duke Math. J. 40 (1973), 907-913, for more detailed information about the growth of c(r).] Several people had conjectured at one time that c(r) would always be a prime number; but ~(15) = 11.173 and ~(18) = 11 . 1021. Perhaps no conjecture about addition chains is safe! Tabulated values of l(n) show that this function is surprisingly smooth; for example, l(n) = 13 for all n in the range 1125 5 n 5 1148. The computer calculations show that a table of I(n) may be prepared for all n < 1000 by using the formula l(n) = min(l(n -1) + 1,1) -6, (48) where 1 = 0;) if n is prime, otherwise 1 = l(p) + l(n/p) if p is the smallest prime dividing n; and S = 1 for n in Table 1, S = 0 otherwise.