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

Home > Numbers
Which is the biggest? (Posted on 2017-01-02) Difficulty: 2 of 5
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?
Rationalize your conclusion.

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution 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       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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information