All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Which is the biggest? (Posted on 2017-01-02)
Consider:
NPR1(n) =number of primes below 10n
NPR2(n)= number of primes with at most n digits
NPR3(n)= number of distinct prime divisors below (10n)!

For a given n, which of the above is the biggest?

 No Solution Yet Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution | Comment 1 of 2
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       11   10      36288002   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

 Search: Search body:
Forums (0)