Wout12345

Proof that Jazz's clock is not O(n!)

Jun 14th, 2015
376
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.59 KB | None | 0 0
  1. This post is split up into two parts. Part 1 is Minecraft-related as this is actually about proving something about this Minecraft contraption made by RedstoneJazz (https://youtu.be/hS1_-xlTYh8). It is simply some background to get into it. The second part is purely mathematical and proves that the product of the first n primes is not O(n!). Part 1 is really basic and probably quite uninteresting, however, I wrote it as to have what I'd consider a solid basis that we're actually tackling the right problem here.
  2.  
  3.  
  4.  
  5. Part 1:
  6.  
  7. This is just converting the problem from Minecraft to mathematics. Background: on The redstone quarry podcast #27, Sharir and I had a short discussion about RedstoneJazz's "Pre-1.5 Universe death clock", which has a cycle time of over a googol years (video: https://youtu.be/hS1_-xlTYh8). The design is based on a series of clocks, which each have a cycle time which can be expressed in prime numbers relative to each other. The full clock triggers whenever all clocks sync up. This is simply the least common multiple of all individual cycle times, by definition basically (I don't think I can/should prove this, this is simply a conversion to mathematical language). For example, a clock consisting out of clocks with cycle times 2, 3 and 5 seconds will send out a pulse every 30 seconds (you can check this for yourself).
  8.  
  9. As this problem deals with a generalized version of Jazz's clock, we need to write this least common multiple out in a bit more of a generalized fashion. For this I will prove a pretty basic property about LCM's. In my opinion, this is quite intuitive, however, I tried hard and think I managed to find a proof which is simply based on definitions and the fundamental theorem of arithmetic.
  10.  
  11.  
  12.  
  13. Lemma 1: The LCM of a series of different prime numbers is the product of all numbers in the series.
  14.  
  15. Proof:
  16.  
  17. If the series only contains one prime, that prime is its own LCM and the lemma is proven.
  18.  
  19. If not, take the LCM of the series. As the series contains two elements or more, it cannot be prime, as it is divisible by more than one element (and no element is one). The fundamental theorem of arithmetic states that, as the LCM is not prime, it's equal to the product of a unique (unordered) series of prime numbers. We call this series or set P. However, by definition the LCM must also be divisible by every prime in the original series. Therefore the LCM can be written as p * c for every prime p in the original series. Following from the fundamental theorem of arithmetic, once more, we know that c is either a prime or a product of primes. Therefore p * c is the product of a series of primes. As the theorem states, the set of prime factors of the LCM is unique, so as p * c = LCM, we know that p * c is the product of the same series of primes. Therefore, every prime p from the original series is part of P.
  20.  
  21. Assume P contains elements which are not part of the original series. Therefore, the LCM = (product of all elements of the original series) * c, with c being the product of these other elements. However, as the product of all elements of the original series is divisible by every element (after all, it can be written as prime * (all other primes)), it is also a common multiple of the series. This leads to a contradiction, as c > 1, implying that the LCM is in fact not the smallest common multiple. Therefore, P = the original series and LCM = the product of all primes of the original series.
  22.  
  23.  
  24.  
  25. With this generalization, we can say things about a "Jazz clock" with a given number of clocks (we only use consecutive primes, starting at 2, as part of the definition). We can finally define the function of the cycle time (in some arbitrary unit, I don't know the exact in-game time this turns out to be in reality, but this is irrelevant to the proof) of a Jazz-clock consisting of n sub-clocks as the product of the first n primes. Now, let's get into the interesting stuff: math.
  26.  
  27.  
  28.  
  29. Part 2: f(n) is not O(n!) with f(n) = p_1 * p_2 * p_3 * ... * p_n with p_i being the i-th prime.
  30.  
  31. Proof:
  32.  
  33. Assume f(n) is O(n!). From the definition of big O-notation, we now know that:
  34.  
  35. f(n) <= c * n!
  36. for some strictly positive real c, for all natural n larger than some natural N
  37.  
  38. We work both sides out for the first steps. As the above should hold for any n larger than a given N, we can always find an n large enough so that these first steps "are actually there":
  39.  
  40. 2 * 3 * 5 * 7 * 11 * 13 * 17 * ... * p_n <= c * 2 * 3 * 4 * 5 * 6 * 7 * ... * n
  41. (11/5) * (13/6) * (17/7) * ... * (p_n/n) <= c * 2 * 3 * 4 /(2 * 3 * 5) = 4/5 * c < c
  42. (11/5) * (13/6) * ... * (p_n/n) < c
  43.  
  44. Let's look at these fractions on the left, writing them as (p_i/i). We will prove by induction that these fractions are larger than 2 for any i larger than 4.
  45. Base case: i = 5. 11/5 = 5.5 > 2, so the lemma is true.
  46. Induction step: First, note that p_i+1 >= p_i + 2, or in other words, any prime is at least two removed from the previous prime, as we don't include the lower primes (as primes > 2 cannot be even, there cannot be two adjacent ones). We also know from the induction hypothesis that p_i > 2i. Therefore, p_i+1 > 2i + 2 = 2(i + 1), or, p_i+1/(i + 1) > 2.
  47.  
  48. As all of these fractions are larger than two, we can also say that (11/5) * (13/6) * ... * (p_n/n) > 2^(n - 4). Going back to our original inequalities, we can conclude the following:
  49.  
  50. 2^(n - 4) < c
  51. for some strictly positive real c, for all natural n larger than some natural N
  52.  
  53. However, if we take an n > max(N, log2(c) + 4), the above does not hold true. Therefore, our initial assumption was wrong, so f(n) is not O(n!).
  54.  
  55.  
  56. (Imagine neat end-of-proof block here.)
Advertisement
Add Comment
Please, Sign In to add comment