chapter  5
24 Pages

Arrays

In Chapter 3 we introduced the following problem. Let pn be the probability that two integers, chosen uniformly and independently from {1,2, . . . ,n}, are relatively prime. What can we say about pn as n→ ∞? We computed pn for various values of n by direct enumeration. As n approached 105, the program became slow and so we sought another approach. In Chapter 4 we tried a Monte Carlo approach. Although our program enables us

to estimate pn for n equal to one million (or larger), to get decent accuracy we need to run the program for too many iterations. In this chapter we take another approach using Euler’s totient.