4.5.3 ANALYSIS OF EUCLID S ALGORITHM (Web hosting faq) 355 where in(z)
4.5.3 ANALYSIS OF EUCLID S ALGORITHM 355 where in(z) is defined in (31). Now fn(x)= & + own), (51) using the facts we have derived earlier (see exercise 23); hence the average value of lnX, is very well approximated by 1 lnx O ueAu -dx=-2-du In s0 1+x In2 s0 l+e-U = -A c (-l) +l lW uemkU du k>l =-A lAff-L.+& -… ( =-A 1+;+;+…-2 ;+I-+$+ . . . ( ( >> =- & 1+;+;+*– ( > = -7r2/(12 In 2). By (49) we therefore expect to have the approximate formula –t7r2/(121n2) z -1nN; that is, t should be approximately equal to ((12ln 2)/7r2) In N. This constant (12 In 2)/T2 = 0.842765913. . . agrees perfectly with the empirical formula (48) obtained earlier, so we have good reason to believe that the formula 12ln2 7n Fz F Inn+ 1.47 (52) indicates the true asymptotic behavior of r12 as n + co. If we assume that (52) is valid, we obtain the formula 12ln2 T nM-Inn -zh(d)/d + 1.47, (53) IT2 dn > where A(d) is von Mangoldt s function defined by the rules if n = p for p prime and r 2 1; otherwise. (54)