Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Disclaimer: This follows from another proof about the same function f(n), effectively indicating an O(n!) lower bound, which can be found here: http://pastebin.com/bdRyH9ci In summary, f(n) is the product of the first n prime numbers. Also, it's important to note this is not an absolute proof. Even if I didn't make any mistakes, I'm using Firoozbahkt's conjecture (https://en.wikipedia.org/wiki/Firoozbakht's_conjecture) which is unproven at the time of writing, which states that p_n^(1/n) < p_n-1^(1/(n - 1)). However, it looks like credible checks have been done for primes up to 18 digits long, which to me makes the conjecture reliable enough to explore the possibility of it being true.
- Theorem: f(n) is O(2^n^(n+1))
- Proof:
- This is our definition of f:
- f(n) = p_1 * ... * p_n-1 * p_n with p_i being the i-th prime
- From here on we will rewrite things to fit Firoozbahkt's conjecture:
- f(n) = p_1 * ... * p_n-1 * p_n^(1/n)^n
- < p_1 * ... * p_n-1 * p_n-1^(1/(n - 1))^n
- = p_1 * ... * p_n-1^(1/(n - 1))^(2n - 1)
- < p_1 * ... * p_n-2 * p_n-2^(1/(n - 2))^(2n - 1)
- = p_1 * ... * p_n-2^(1/(n - 2))^(3n - (1 + 2))
- As we continue these steps, we could write out the iterations like this (you can check this for yourself):
- p_1 * ... * p_x^(1/x)^((-x + n + 1)*n - (1 + 2 + 3 + ... + (-x + n)))
- The final iteration, with everything reduced to the first prime (so x = 1), can therefore be written like this:
- p_1^(1/1)^(n*n - (1 + 2 + 3 + ... + (n - 1)))
- = p_1^(n^2 - n(n - 1)/2)
- = p_1^(1/2) * p_1^(n^2 + n)
- = sqrt(2) * 2^(n^2 + n)
- So, in summary, we now know that (if Firoozbahkt's conjecture is true):
- f(n) < sqrt(2) * 2^(n^2 + n)
- f(n) <= c * 2^(n^2 + n)
- for all n > 1 with c = sqrt(2)
- Or in other words, f(n) is O(2^n^(n+1)).
Advertisement
Add Comment
Please, Sign In to add comment