6 ms·

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

by stymaar 10y ago

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 ?

idlewords 10y ago
We know the limit is not 100 because of Euclid's proof of the infinitude of primes.
- drdeca 10y ago
  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.
  - fdej 10y ago
    Not just believed, pi(n) ~ n / log(n) is the prime number theorem.
    - drdeca 10y ago
      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.
      - xyzzyz 10y ago
        Riemann hypothesis gives better error estimates for the asymptotics in the prime number theorem.
        drdeca 10y ago
        Ah, alright, thanks!
      - deleted 10y ago
        [deleted]
- CUViper 10y ago
  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.
- recursive 10y ago
  There are infinite perfect squares also, but only 0% of all integers are perfect squares.
  - idlewords 10y ago
    Yet there are just as many perfect squares as integers.
andrepd 10y ago
You can evaluate this for different limits: 88% of numbers have a divisor below 100, 92% below 1000, 50% below 2, etc.
- JoeAltmaier 10y ago
  ...at least 33% have factors <=3
  - saagarjha 10y ago
    2/3, you mean :)
  - samfisher83 10y ago
    50% have 2 as a factor.
daveFNbuck 10y ago
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_reciprocals_of_the_primes 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.

by stymaar 10y ago

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 ?

idlewords 10y ago

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

drdeca 10y ago
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.
- fdej 10y ago
  Not just believed, pi(n) ~ n / log(n) is the prime number theorem.
  - drdeca 10y ago
    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.
    - xyzzyz 10y ago
      Riemann hypothesis gives better error estimates for the asymptotics in the prime number theorem.
      - drdeca 10y ago
        Ah, alright, thanks!
    - deleted 10y ago
      [deleted]
CUViper 10y ago
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.
recursive 10y ago
There are infinite perfect squares also, but only 0% of all integers are perfect squares.
- idlewords 10y ago
  Yet there are just as many perfect squares as integers.

andrepd 10y ago

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

JoeAltmaier 10y ago
...at least 33% have factors <=3
- saagarjha 10y ago
  2/3, you mean :)
- samfisher83 10y ago
  50% have 2 as a factor.

daveFNbuck 10y ago

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_reciprocals_of_the_primes 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.