Wout12345

Proof that Jazz's clock is O(2^n^(n+1))

Jun 15th, 2015
372
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.73 KB | None | 0 0
  1. 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.
  2.  
  3.  
  4.  
  5. Theorem: f(n) is O(2^n^(n+1))
  6.  
  7. Proof:
  8.  
  9. This is our definition of f:
  10.  
  11. f(n) = p_1 * ... * p_n-1 * p_n with p_i being the i-th prime
  12.  
  13. From here on we will rewrite things to fit Firoozbahkt's conjecture:
  14.  
  15. f(n) = p_1 * ... * p_n-1 * p_n^(1/n)^n
  16. < p_1 * ... * p_n-1 * p_n-1^(1/(n - 1))^n
  17. = p_1 * ... * p_n-1^(1/(n - 1))^(2n - 1)
  18. < p_1 * ... * p_n-2 * p_n-2^(1/(n - 2))^(2n - 1)
  19. = p_1 * ... * p_n-2^(1/(n - 2))^(3n - (1 + 2))
  20.  
  21. As we continue these steps, we could write out the iterations like this (you can check this for yourself):
  22.  
  23. p_1 * ... * p_x^(1/x)^((-x + n + 1)*n - (1 + 2 + 3 + ... + (-x + n)))
  24.  
  25. The final iteration, with everything reduced to the first prime (so x = 1), can therefore be written like this:
  26.  
  27. p_1^(1/1)^(n*n - (1 + 2 + 3 + ... + (n - 1)))
  28. = p_1^(n^2 - n(n - 1)/2)
  29. = p_1^(1/2) * p_1^(n^2 + n)
  30. = sqrt(2) * 2^(n^2 + n)
  31.  
  32. So, in summary, we now know that (if Firoozbahkt's conjecture is true):
  33.  
  34. f(n) < sqrt(2) * 2^(n^2 + n)
  35. f(n) <= c * 2^(n^2 + n)
  36. for all n > 1 with c = sqrt(2)
  37.  
  38. Or in other words, f(n) is O(2^n^(n+1)).
Advertisement
Add Comment
Please, Sign In to add comment