Hacker News Reader

Comment by forinti | Hacker News Reader

This post has a little graph that shows the curve you get when you plot how many integers have factors in the first n primes: http://alquerubim.blogspot.com.br/2016/08/cobertura-dos-n-pr...

View on HN

Do we know if this fonction has a limit different from 100 ? I mean, is there a number 'x'<100 where, for any number 'n' the percentage of all integer having a divisor below 'n' is always < x ?

We know the limit is not 100 because of Euclid's proof of the infinitude of primes.

The primes become more sparse in the integers as you go farther. For most reasonable definitions of the density of composite integers in the integers, the density would be 100%.

Iirc, it is believed that the number of primes less than n is O(n/log(n)), so primes/integers among the first n integers should go as O(1/log(n)), so goes to 0 as n goes to infinity.

Not just believed, pi(n) ~ n / log(n) is the prime number theorem.

I wasn't sure if the proof depended on the Riemann hypothesis or not.

So, I wasn't sure if it had been proven, or just proven given that assumption. So that's why I said that it was believed.

Riemann hypothesis gives better error estimates for the asymptotics in the prime number theorem.

Ah, alright, thanks!

I don't think that tells you anything without comparing to the infinitude of composites too. The fraction of numbers less than n that are prime is roughly 1/logn, which goes to zero in the limit. So I think the limit of numbers with factors less than n as n goes to infinity must indeed be 100%.

That doesn't mean there's an n with 100%, just that there's no smaller limit that some n doesn't exceed.

There are infinite perfect squares also, but only 0% of all integers are perfect squares.

Yet there are just as many perfect squares as integers.

You can evaluate this for different limits: 88% of numbers have a divisor below 100, 92% below 1000, 50% below 2, etc.

...at least 33% have factors <=3

2/3, you mean :)

50% have 2 as a factor.

We can look at this question as asking whether the product of (p-1)/p for all primes p goes to zero. Taking the log, this is the same as asking whether the sum of log((p-1)/p) is unbounded. log((p-1)/p) = log(p-1) - log(p), which is less than -1/p (greater in magnitude).

The sum of the reciprocals of the primes is unbounded (https://en.wikipedia.org/wiki/Divergence_of_the_sum_of_the_r...). So the sum of the logs is less than the negative of the sum of the reciprocals of the primes, it is unbounded as well. Therefore the limit is 100.

Reply on news.ycombinator.com