88 percent of all integers have a factor under 100

And 92 percent of all (positive) integers have a factor under 1,000. And how many have a factor under 6? Can you guess the answer? Read more to find out.

Clearly, the vast majority of big numbers have small factors. Also, the chance to be a prime becomes incredibly small, the bigger the number. I stumbled upon these problems when looking for new algorithms to factor a product of two large primes (more on this coming soon.) I then decided to find out what the proportion of integers having a factor under n, is.

To answer this question, let's first define p(m) as the proportion of integers that are divisible by one (or more) of the first m prime numbers. One can easily show that 

where the product is over the first m prime numbers. In particular, the proportion of integers with a factor under 6 is p(3) = 1 - (1 - 1/2)(1 - 1/3) (1 - 1/5) = 73%. The above mathematical formula can easily be derived, using arguments similar to those in my article A Beautiful Probability Theorem.  

To answer the more general question about the proportion of integers having a factor under n, one must choose m such that the last prime in the above product is the largest prime number smaller than n. Using the prime number theorem, it is easy to get an approximation for m as n tends to infinity. Also, taking the logarithm of the product, one can finally answer the question using approximations based on the prime number theorem. I will leave it to the reader to find the asymptotic formula and post it here in the comment section below.  

Using the exact formula for p(m), it is also easy to built a table:for the proportion p(n) of positive integers with a factor under n, see table below:

Other Problems Involving Factoring

Here, by divisor, I mean a non-trivial divisor. For instance, the largest divisor of 45 is 15, not 45. Study the following recurrence relationships:

  • f(n+1) is the largest prime factor of 3 f(n) + 1, with f(1) = 1.
  • Same if f(n+1) is defined as the largest prime factor of 2 f(n) + 5, with f(1) = 1.

Are all these functions turning periodic, beyond some n?

What about

  • f(n+1) is the largest divisor of {f(n)}^2 + 1, with f(1) = 1.
  • f(n+1) is the largest divisor of  {f(n)}^2 - 2, with f(1) = 3.

Why is the last function growing so fast? Are prime numbers over-represented among the values of f(n)? Can these functions be used to build large prime numbers? Is it possible that for some n, {f(n)}^2 - 2 (say) does not have a non-trivial divisor, which means that it is a prime number and that f(n+1) does not exist?

Top DSC Resources

Follow us on Twitter: @DataScienceCtrl | @AnalyticBridge

Views: 23170


You need to be a member of Data Science Central to add comments!

Join Data Science Central

Comment by Vincent Granville on April 3, 2017 at 12:35pm

For those wondering how you can even put a distribution on the infinite set of integers, here is the answer: We are dealing with a marked point process, in which the points are the positive integers, and the mark is 1 if a point is divisible by a number less than 100, 0 otherwise. It is then possible to compute the probability for the mark to be either 0 or 1. This is one of the basic distributions associated with a marked point process. 

People may not notice it because in this case, the points (integers) are equally spaced while in most point processes, the points are randomly distributed according to some particular distribution. Only the marks appear as somewhat random here. Note that the number of points is also infinite in most (but not all) examples of point processes. These processes are sometimes called doubly-stochastic in the sense that randomness can occur for the location of the points, for the marks, or both. Here randomness occurs only for the marks. Another way to look at it: Let's consider the points to be truly randomly distributed, with the inter-point distances having an exponential distribution with variance (say) equal to v, as in a Poisson process. Let v tends to zero, then you get points that are equally spaced.

You may also want to read my article on how to define and measure integer densities, with a different, non-probabilistic perspective.

© 2021   TechTarget, Inc.   Powered by

Badges  |  Report an Issue  |  Privacy Policy  |  Terms of Service