Consider:
NPR1(n) =number of primes below 10
n
NPR2(n)= number of primes with at most n digits
NPR3(n)= number of distinct prime divisors below (10
n)!
For a given n, which of the above is the biggest?
Rationalize your conclusion.
The number of primes below any given power of ten is larger than the number below a smaller power of ten.
A number with at most n digits is less than 10^n, but can be as high as 10^n - 1. So the only number missing from the set where the numbers are less than or equal to 10^n is the actual 10^n. So numbers with at most n digits are the same as the numbers below 10^n--they're the same set, and contain the same primes (especially as 10^n itself isn't prime anyway). So NPR1(n) and NPR2(n) are the same.
In most cases (10^n)! is hugely bigger than 10^n:
n 10^n (10^n)!
0 1 1
1 10 3628800
2 100 a number of 158 digits
...
So in the case of n=0, none of the sets contain any primes, but from then on NPR3(n) contains vastly more numbers, and with them, vastly more primes.
To add to the rigor, bringing this to D2 level:
The prime number theorem gives the asymptotic relation of number of primes to the limiting size of the number:
p(x) ~= x/ln(x)
The Stirling approximation to n! is sqrt(2*pi*n)*(n/e)^n
But here what we're factorialing is 10^n:
f ~= sqrt(2*pi*10^n)*(10^n / e)^(10^n)
while the number of primes approximates f / ln(f), while is much more huge than 10^n / (n*ln(10)), just as f is much more huge than 10^n.
|
|
Posted by Charlie
on 2017-01-02 10:43:01 |
solution
