Some Exact Number Theory Computations via Probability Mechanisms
Richard Blecksmith, Purushottam W. Laud · American Mathematical Monthly · 1995
1. INTRODUCTION. In this paper we apply stochastic methods to efficiently compute several number theoretic functions. The application of probability to number theory suggests density results. For example, the prime number theorem asserts that the probability that a number chosen between 1 and n is prime is approximately 1/log n. This is, of course, just an asymptotic estimate. Our goal here is to obtain exact results about functions involving the bit patterns of numbers. The results we describe can be generalized to other bases, notably base 10, but we work with base 2 for simplicity and ease of computations. The first problem we address is how to select a random number x between 0 and a fixed bound n, written in binary as