Global AI and Data Science

 View Only

88 percent of all integers have a factor under 100

By Moloy De posted Thu March 04, 2021 08:36 PM

  
The vast majority of big numbers have small factors. Also, the chance to be a prime becomes incredibly small, the bigger the number.  92 percent of all positive integers have a factor under 1,000. And how many have a factor under 6?

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 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 be derived using arguments.

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. 

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:
Here, by divisor, I mean a non-trivial divisor. For instance, the largest divisor of 45 is 15, not 45. One can study the following recurrence relationships:
1. f(n+1) is the largest prime factor of 3 f(n) + 1, with f(1) = 1.
2. 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

1. f(n+1) is the largest divisor of {f(n)}^2 + 1, with f(1) = 1.
2. 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?

QUESTION I : Can there be a function f such that f(n) is the n-th prime?
QUESTION II : How difficult is factorizing large numbers?

REFERENCE : Data Science Central Blog by Vincent Granville
#GlobalAIandDataScience
#GlobalDataScience
0 comments
2 views

Permalink