Upper Bounds for Prime Numbers/Result 2
Theorem
Let $p: \N \to \N$ be the prime enumeration function.
Then $\forall n \in \N$, the value of $\map p n$ is bounded above.
In particular:
- $\forall n \in \N: \map p n \le \paren {p \paren {n - 1} }^{n - 1} + 1$
Proof
Let us write $p_n = \map p n$.
Let us take $N = p_1 p_2 \cdots p_n + 1$.
By the same argument as in Euclid's Theorem, we have that either $N$ is prime, or it is not.
If $N$ is prime, then either $N = p_{n + 1}$ or not, in which case $N > p_{n + 1}$.
In the second case, $N$ has a prime factor not in $\set {p_1, p_2, \ldots, p_n}$
Therefore it must have a prime factor greater than any of $\set {p_1, p_2, \ldots, p_n}$.
In any case, the next prime after $p_n$ can be no greater than $p_1 p_2 \cdots p_n + 1$.
Hence the result.
$\blacksquare$
Note
It can be seen that the limit found is wildly extravagantly large.
However, it is an easily established result, and it has its uses.