UPPER BOUND ON P1,000,000
It might naively be thought that since the prime numbers are "random" that there is no way to know for sure how large, say, the nth prime number is. Turns out however that this is false. We can bound the nth prime number from above and below, and if we aren't picky about how precise those bounds are, we can do it with very elementary methods. For googological reasons, the bad upperbounds are more interesting than the bad lower bounds.
Recall the proof of the infinitude of primes. A nice upshot of this proof not often brought up is that it is a constructive proof that can be used in theory to bound the nth prime number. The bounds it creates however are really really preposterously bad!!! But this can be rather amusing from a googological point of view.
The basic idea is that we can take the main thrust of the proof to create an upperbound for the next prime number, give a list of consecutive primes, or their upperbounds.
Assume we have a consecutive list of primes, p1,p2,...,p(n)
Take the product of all these primes and add 1:
p1*p2*...*p(n)+1
Call this M. If no primes exist between p(n) and M then we only need to check divisibility by p1 through p(n) to prove that M is prime. However M can not be divided by p1 through p(n) since we will always get a remainder of 1. The only way M can not be prime is if it is divisible by some prime, p(*), that is greater than p(n) but less than M. Therefore the next prime is at most M.
In otherwords, given p1,p2,...,p(n) we conclude that p(n+1) <= M.
Call this the bounding lemma.
The upshot of this is that we can guarantee a sequence of numbers that grows faster than the sequence of primes. Call this sequence s1,s2,..., and let the sequence begin with a list of the smallest known consecutive primes beginning with the smallest.
It's not difficult to find small primes, but we really don't need a huge list to get started. To get my massive bound I'll begin with just the first two prime numbers: 2,3. 2 is prime because there is no number between 1 and 2 to divide it by, and 3 is prime because 2 is the only number between 1 and 3 and it leaves remainder 1.
By our bonding lemma, p3 <= 2*3+1 = 7
Now we know for a fact that p3=5 and therefore this is an overestimate, but that's okay, as you'll see in a moment.
Our lemma also means that:
p4 <= p1*p2*p3+1
The problem is we haven't actually generated p3, but it doesn't matter because:
p1*p2*p3+1 <= p1*p2*7+1
And so we will be able to iteratively create (worse and worse) bounds on the nth prime number. This produces a sequence of numbers (bounds)
p3 <= 7
p4 <= 43
p5 <= 1807
p6 <= 3,263,443
p7 <= 10,650,056,950,807
...
but we have a bit of a snag because this sequence does not admit a nice simple closed form. We next try to upperbound s(n), getting a potentially even worse upperbound. Our sequence is defined as follows:
s(1) = 2 , s(2) = 3
s(n+1) = s(1)*s(2)*...*s(n)+1
Now we use a bit of mathematical trickery:
s(n+1)-1 = s(1)*s(2)*...*s(n)
s(n+2) = s(1)*s(2)*...*s(n)*s(n+1)+1
By making the substitution with the red text with the blue text we get:
s(n+2) = (s(n+1)-1)s(n+1)+1
This implies:
s(n+1) = (s(n)-1)s(n)+1 = s(n)^2-s(n)+1 = s(n)^2+1-s(n)
We can note that that 1-s(n) must be negative since every member of the sequence is larger or equal to a prime number, and all prime numbers are greater than 1. Therefore:
s(n)^2+1-s(n) < s(n)^2
and
s(n+1) < s(n)^2
So the next member of the sequence is definitely smaller than the square of the previous member of the sequence. We use this to get our final upperbound:
s3 = 7
s4 < 7^2
s5 < (s4)^2 < (7^2)^2 = 7^4
s6 < (s5)^2 < (7^4)^2 = 7^8 = 7^(2^3)
s7 < (s6)^2 < (7^8)^2 = 7^16 = 7^(2^4)
...
:: s(n) < 7^2^(n-3) : n>3
Since p(n) <= s(n) < 7^2^(n-3)
we conclude:
p(n) < 7^2^(n-3) : n>3
Substituting a million in gives us our bound for the millionth prime number:
p(1,000,000) < 7^2^999,997
This bound is absurdly massive! The actual value of p(1,000,000) is just 15,485,863. This is kind of like how Graham's Number is just a really bad upperbound on a solution to a particular problem in ramsey theory.
7^2^999,997 can be written in standard base 10 form by computing the following:
10^10^(999,997*log(2)+log(log(7)))
which works out to about...
10^10^301,029.019481
This number is bigger than a googolplex, bigger than a googolplexigong, bigger than gargoogolplexigong, thrargoogolplexigong, gargoogolgong-plexed, or even thrargoogolgong-plexed, but smaller than milliduplexion and fzmilliplexion.