Make a web site - 354 ARITHMETIC 4.5.3 It follows that (47) Here
354 ARITHMETIC 4.5.3 It follows that (47) Here is a table of rn for the same values of n considered above: n = 95 96 97 98 99 100 101 102 103 104 105 7, = 5.4 5.3 5.3 5.6 5.2 5.2 5.4 5.3 5.4 5.3 5.6 n = 996 997 998 999 1000 1001 … 9999 10000 10001 7, = 7.2 7.3 7.3 7.3 7.3 7.4 .** 9.21 9.21 9.22 72,= 49999 50000 50001 … 99999 100000 100001 7, = 10.58 10.57 10.59 … 11.170 11.172 11.172 Clearly 7, is much more well-behaved than T,, and it should be more susceptible to analysis. Inspection of a table of 7, for small 72 reveals some curious anomalies; for example, 750 = 7100 and 760 = ~120. But as n grows, the values of T, behave quite regularly indeed, as the above table indicates, and they show no significant relation to the factorization properties of n. If the reader will plot the values of rn versus Inn on graph paper, for the values of 7, given above, he will see that the values lie very nearly on a straight line, and that the formula T, M 0.843lnn + 1.47 (48) is a very good approximation. We can account for this behavior if we study the regular continued fraction process a little further. Note that in Euclid s algorithm as expressed in (15) we have Since uk+i = vk; therefore if u = uo and V = VOare relatively prime, and if there are t division steps, we have x,x1 . . .X,-l = l/U. Setting U = N and V = m < N, we find that lnXo+lnX1+…+lnXt-r =-1nN. (49) We know the approximate distribution of X0, X1, X2, . . . , so we can use this equation to estimate t = T(N, m) = T(m, N) -1. Returning to the formulas preceding Theorem W, we find that the average value of lnX,, when X0 is a real number uniformly distributed in [ 0, l), is s 0 1 In z F:(z) da: = s 0 1 ln 5 f&) W(l + 4, (50)