Probabilities and Expected Value
In 1972, James E. Nymann showed that k integers, chosen independently and uniformly from {1,...,n}, are coprime with probability 1/ζ(k) as n goes to infinity. (See coprime for a derivation.) This result was extended in 1987 to show that the probability that k random integers has greatest common divisor d is d-k/ζ(k).
Using this information, the expected value of the greatest common divisor function can be seen (informally) to not exist when k = 2. In this case the probability that the gcd equals d is d−2/ζ(2), and since ζ(2) = π2/6 we have
This last summation is the harmonic series, which diverges. However, when k ≥ 3, the expected value is well-defined, and by the above argument, it is
For k = 3, this is approximately equal to 1.3684. For k = 4, it is approximately 1.1106.
Read more about this topic: Greatest Common Divisor
Famous quotes containing the word expected:
“What is a country without rabbits and partridges? They are among the most simple and indigenous animal products; ancient and venerable families known to antiquity as to modern times; of the very hue and substance of Nature, nearest allied to leaves and to the ground,—and to one another; it is either winged or it is legged. It is hardly as if you had seen a wild creature when a rabbit or a partridge bursts away, only a natural one, as much to be expected as rustling leaves.”
—Henry David Thoreau (1817–1862)