Wout12345

An analysis of the optimal spamming problem

Jun 5th, 2017
345
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 43.30 KB | None | 0 0
  1. 1. Description of the problem
  2.  
  3. Let's say you're Noerdy and you're in math class and you're so bored out of your mind that you grab your phone and you just have to inform Wout about your frustration, because he doesn't have a bachelor test or exams to work on or something. You start with your Skype text field with one character in it, nothing selected and an empty clipboard. How do we reach n characters just using ctrl+A, ctrl+C and ctrl+V (command instead of ctrl for you elitists) with the least number of key presses? Our goal is to find a simple procedure humans could go through in order to construct the optimal solution, like how if we were just interested in the length of the optimal solution we'd want a simple mathematical formula. In this document I'll be discussing both the exact problem, where we try to reach exactly n characters, as well as the excess problem, where we try to reach at least n characters. For convenience, I'll treat this as a game and will often call key presses moves, the amount of key presses cost, ... We'll also assume n > 1 since 0 and 1 are kind of corner cases and can be easily unified with the general procedure later on.
  4.  
  5. P.S.: Let's also assume Noerdy somehow hooked up a keyboard to his phone in math class without the teacher noticing. It's Noerdy, I wouldn't even be surprised.
  6. P.P.S.: I think most programs don't actually do anything when you try to paste an empty selection, however for the sake of consistency I'll assume it does (pasting an empty string, even if that means clearing the selection). It shouldn't really affect the game apart from making n = 0 unreachable from what I can tell. After all, as will be shown later, all it allows us to do is multiply by 0 or not do that, which is never strategical for any n > 1.
  7.  
  8.  
  9.  
  10.  
  11.  
  12. 2. Simplifying the problem
  13.  
  14. Let's first try to create the simplest possible model to represent this problem. We will do this with a state space search. In this section I will prove that the problem can be modelled as a series of multiplications (at any point you can multiply the length of the text field by x, costing you x + 2 moves and all optimal games can be viewed as a sequence of such multiplications). If you aren't interested in a formal proof, you can skip this section since it's fairly intuitive.
  15.  
  16.  
  17.  
  18. 2.1. The state properties
  19.  
  20. Our state at any time consists of three things: the amount of characters in the text field (initially 1), the amount of characters in the clipboard (initially 0) and whether or not the text field is currently selected (initially false). We don't need to consider the cases where only some of the characters in the text field are selected, because there's an invariant which guarantees that after any move either all or no characters in the text field will be selected:
  21.  
  22. Initial case: nothing is selected.
  23. Recursive case:
  24. - ctrl+A: Selects all characters.
  25. - ctrl+C: Deselects all characters.
  26. - ctrl+V: Deselects all characters.
  27.  
  28. Since the position of the cursor only affects where text is pasted, but we only care about the length of the text field or clipboard, not their contents, we don't need to consider the cursor as part of our state. Now let's take a look at each individual move.
  29.  
  30.  
  31.  
  32. 2.2. Merging ctrl+C and ctrl+V
  33.  
  34. First, ctrl+C. It is only useful to use this move if the text field is selected, else the state won't be affected at all but it'll cost you a move. So, in all useful scenarios, it is not useful to use ctrl+A after ctrl+C, since the text field is already selected so the ctrl+A move won't change the state. Pressing ctrl+C again also won't affect the state. The search can also never end here because our goals are constrained by the length of the text field and using ctrl+C will only affect the clipboard. We can therefore conclude that in all useful scenarios you'd want to use ctrl+V right after ctrl+C, so we will consider this to be one move called ctrl+C+V from here on out, with the following effect on the state:
  35. - If the text field is selected, it is copied to the clipboard and deselected. The text field is unaffected.
  36. - If the text field is deselected, it is expanded using the clipboard. The text field stays deselected and the clipboard is unaffected.
  37.  
  38.  
  39.  
  40. 2.3. Merging ctrl+A and ctrl+C+V
  41.  
  42. Ctrl+A is only useful if the text field is deselected. So after this move, it's not useful to perform ctrl+A again. To prove that it is never useful to perform ctrl+V after ctrl+A, we'll have to consider the next invariant: at any point, the clipboard is either empty, or, the game is currently in a state or has been in a state where the clipboard contained as many characters as it currently does, the text field contained as many characters as the current clipboard and the text field was deselected. Note how this invariant is entirely based on the clipboard and the previous states. Therefore, a move which doesn't change the clipboard will not change the invariant from being true to being false, since the clipboard is unaffected and the state history is only expanded.
  43.  
  44. Initial case: the clipboard is empty.
  45. Recursive case:
  46. - ctrl+A: Doesn't change the clipboard.
  47. - ctrl+C+V: If the text field is deselected, the clipboard isn't changed. If the text field is selected, then in the new state the text field will be deselected and the text field and clipboard will contain as many characters as the new clipboard. Therefore, this state fits the constraints set by the invariant.
  48. - ctrl+V: Doesn't change the clipboard.
  49.  
  50. As a result, it is never useful to perform ctrl+V after ctrl+A:
  51. - If the clipboard is currently empty, you're emptying both the text field and the clipboard, meaning that we can never create new characters anymore. Since we assumed n > 1, this is never useful.
  52. - Otherwise, since the text field is selected, both the new text field and clipboard will have the same length as the current clipboard and the new text field will be deselected. The invariant above guarantees that this state already occurred in our state history, meaning we created a cycle in our state space which is simply a waste of moves.
  53.  
  54. We can also never stop the search after ctrl+A, since it only affects the selection, not the text field. Therefore, there's only one move left, meaning that after ctrl+A it's only useful to perform ctrl+C+V. We will replace ctrl+A with the new move ctrl+A+C+V, with the following effect on the state: the text field is deselected, its contents are unaffected and the clipboard now contains the text field.
  55.  
  56.  
  57.  
  58. 2.4. Switching to multiplications
  59.  
  60. Let's recap. By merging moves we have arrived at this new set of moves: ctrl+A+C+V, ctrl+C+V and ctrl+V. Since ctrl+A was the only basic move to select the text field and it can now only be performed when followed by ctrl+V, we can see that in between these higher-level moves the text field is always deselected. Therefore we can ignore this part of our state from now on. As a result, ctrl+C+V has the exact same effect as ctrl+V (since the basic move ctrl+C does not have any effects when the text field is deselected) and since it costs one more basic move to perform, it will never be useful. We're left with two moves now, with the following effects:
  61. - ctrl+A+C+V: the text field is copied to the clipboard.
  62. - ctrl+V: the text field is expanded by the clipboard.
  63.  
  64. This means we can represent each game as a series of two possible moves, like 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1. One could also represent this by counting the length of each chain of 1's. I won't go into the details here, but for example the game described earlier would be represented as: 3 (meaning a 0 followed by two 1's), 1, 1, 6, 2. Here every number x stands for one ctrl+A+C+V followed by x - 1 ctrl+V's. We can represent any optimal game like this since it's not useful to start a game with ctrl+V, as this won't have any effects due to the empty clipboard.
  65.  
  66. Note that in this representation, the effect of each move x is multiplying the length of the text field by x at the cost of x + 2 basic moves. We've arrived at the simplest model for our problem: each optimal game is simply a sequence of multiplications by factors x1, x2, ..., x_m, whereas the cost of such a game is (x1 + 2) + ... + (x_m + 2). Note that these are not ordered tuples but multi-sets, so the ordering of the solution doesn't matter.
  67.  
  68.  
  69.  
  70.  
  71.  
  72. 3. Exact problem
  73.  
  74. The exact problem gets down to merging the prime factors p1, p2, ..., p_l of n into the factors x1, x2, ..., x_m so that x1*...*x_m = n and (x1 + 2) + ... + (x_m + 2) is minimal.
  75.  
  76.  
  77.  
  78. 3.1. Bounds set by factorization
  79.  
  80. Let's take a look at the effect of merging two factors (prime or composite) a and b together. The initial number can be written as n = a*b*c, where c consists of m factors. This means the initial cost is equal to (a + 2) + (b + 2) + c + 2*m. By taking a and b together as one factor, the new cost is (ab + 2) + c + 2*m, meaning the increased cost is:
  81. ((ab + 2) + c + 2*m) - ((a + 2) + (b + 2) + c + 2*m)
  82. = (ab + 2) - (a + 2) + (b + 2)
  83. = ab + 2 - a - 2 - b - 2
  84. = ab - a - b - 2
  85. = (b - 1)*a - b - 2
  86. = (a - 1)*b - a - 2
  87. Note that for a, b > 1 the value of this expression always increases both in function of a and b.
  88.  
  89. This means that there is probably not a simple procedure for humans to produce a solution given some sufficiently large n. Say you're given a large number n which consists of two large primes p and q. Then the only possible optimal solutions such a procedure could produce would be (p, q) or (pq). Using the previous calculations, we know that the increased cost from merging p and q is:
  90.  
  91. pq - p - q - 2
  92.  
  93. We will now prove that this expression will always be positive. Since n should be sufficiently large, it is safe to assume n >= 10. This means that at least p or q is >= 5. Since p and q are prime, they are both larger than or equal to 2. This gives us a lower bound for the gained cost (since it increases both in function of p and q):
  94.  
  95. 5*2 - 5 - 2 - 2 = 1
  96.  
  97. Since this is a positive number, merging p and q will always increase the cost. Therefore, for any n >= 10 consisting of exactly two primes p and q the optimal solution is (p, q). However, this implies solving the RSA problem (https://en.wikipedia.org/wiki/RSA_problem), since a procedure to calculate an optimal solution to this problem would allow us to factor the public key of the RSA algorithm into the two primes making up its private key as well, which is probably computationally difficult.
  98.  
  99.  
  100.  
  101. 3.2 Simple procedure given factorization
  102.  
  103. Yet, we can look at a related problem. After all, a lot of calculator programs have a factorize-operation, meaning that for moderately large n a human could possibly still practically use one of those to obtain the prime factorization. Is there a simple procedure to find all optimal solutions given the prime factorization?
  104.  
  105.  
  106.  
  107. 3.2.1. Optimal merging
  108.  
  109. Let's take a look at the increased cost when going from a and b to ab again. We want this to be negative, so for what values of a, b >= 2 would merging be worth it? Since there aren't many, we can just iterate (increased cost is ab - a - b - 2).
  110. 1) a = 2: increased cost is b - 4, so worth it for any b <= 4. For the time being we'll relax our conditions since we don't want to eliminate co-optimal solutions yet.
  111. 2) a = 3: increased cost is 2b - 5, so worth it for any b < 3.
  112. 3) a = 4: increased cost is 3b - 6, so worth it for b = 2.
  113.  
  114. So from a local point of view, merging is only worth it for the following pairs of factors: (2, 2), (2, 3), (2, 4), (3, 2), (4, 2). Note that these are exactly the same merges as those which can produce the factors 4, 6 and 8, all composite numbers smaller than 9.
  115.  
  116. But who's there to say we aren't missing out on some global minimum by only looking at the increased cost one merge away from current situation? First of all, we can prove that merges with positive increased cost are never worth it. After all, any merge with a positive increased cost would produce a new factor larger than or equal to 9, as shown in the last paragraph. Any of these merges can be undone since these factors are too large to be of any use to merges with non-positive increased cost. Therefore, an optimal solution would never contain one of these merges, since it could be improved by undoing these merges.
  117.  
  118. However, this still gives us freedom to choose how to perform merges with non-positive increased cost. Let's analyze the increased cost of all of these:
  119. (2, 2): 2*2 - 2 - 2 - 2 = -2
  120. (2, 3), (3, 2): 2*3 - 2 - 3 - 2 = -1
  121. (2, 4), (4, 2): 2*4 - 2 - 4 - 2 = 0
  122. For the time being, we'll ignore the (2, 4)-merge, since it only gives us co-optimal solutions which can always be gotten by applying it at the end. After all, it produces a factor of 8, which is too large to be used by any of the other non-positive increased cost merges. So the question simply is: given a prime factorization containing q 2's and r 3's, how to merge these to create the minimal increased cost?
  123.  
  124. In other words, we've arrived at an integer programming problem (yay, that operations research course last year was good for something!). We try to maximize the expression 2x + y with the constraints 2x + y <= q, y <= r and x, y, q, r are non-negative integers. Oh wait, let's not do that since those constraints contain unknown constants and it's been three semesters since I did integer programming ... Really, the problem is so small that we can find all optimal solutions fairly easily through logical reasoning. After all, one (2, 2)-merge will give us the same decreased cost as two (2, 3)-merges. Therefore, what we're trying to maximize is the use of 2's. We can always do this by pairing together 2's and, if q is odd and r >= 1, pair the last 2 together with a 3. Depending on how many 3's are left one can then easily generate all other possible solutions by switching out one (2, 2)-merge with two (2, 3)-merges, provided there are enough 3's.
  125.  
  126.  
  127.  
  128. 3.2.2. Summary
  129.  
  130. That's it! We've figured out a simple procedure to find an optimal solution given the prime factorization of n! Let's recap our steps:
  131. 1) Factorize n. This step should be performed using a calculator to keep the procedure simple for humans. For reasonably small n (the kind of n Skype can handle) this will not prove to be an issue in terms of calculation time.
  132. 2) Merge 2's together into 4's as much as you can. If you're left with one 2 and at least one 3, merge these together into a 6.
  133. 3) This new multi-set represents the multiplications you should apply. So, pick an arbitrary element x from the multi-set, remove it, press ctrl+A, press ctrl+C and press ctrl+V x times.
  134. The minimal cost is the sum all elements of the multi-set and 2 times the size of the multi-set.
  135.  
  136. And if you want to find all optimal solutions:
  137. 1) Factorize n with a calculator.
  138. 2) Merge 2's together into 4's as much as you can. If you're left with one 2 and at least one 3, merge these together into a 6. If there are 3's left, you can choose to switch out any (2, 2)-merge for two (2, 3)-merges. If you're still left with a 2 and at least one 4, you can choose whether to merge these into an 8 or not.
  139. 3) This new multi-set represents the multiplications you should apply. You can choose any element x from the multi-set, remove it, press ctrl+A, press ctrl+C and press ctrl+V x times.
  140. The minimal cost is the sum all elements of the multi-set and 2 times the size of the multi-set.
  141.  
  142. Of course, if n = 0: the minimal solution is unique and is simply ctrl+A followed by ctrl+V. If n = 1, the minimal solution is also unique: do nothing.
  143.  
  144.  
  145.  
  146.  
  147.  
  148. 4. Excess problem
  149.  
  150. In the excess problem, given some n, the goal is to reach a text field with at least n, not necessary exactly n, characters. At this point, the problem gets a lot more complicated. As it turns out, simply following a single power series (like 4) will not give you optimal solutions for all n. For example, if your strategy is to expand by always multiplying by 4, you will reach at least 5 characters after 10 moves, even though you could have reached it after 7 moves if you hadn't bothered copying when you were already at 4 characters. As a result, it's not sufficient to round n up to some power of 4 which can be easily reached in an optimal manner. In this section, we will explore another strategy instead.
  151.  
  152.  
  153.  
  154. 4.1. Computing the first results
  155.  
  156. At this point I hit a dead end for a day or two, so I wrote a Python program (source code at the bottom of this document) and started crunching some numbers. For all n, we want to find an m >= n to minimize cost(m) (I will use the function cost(n) from now on to refer to the minimal cost to reach exactly n characters). To this end, let's define the ordered series S = {m | m is an integer >= 2 and there exists no o > m with cost(o) < cost(m)}. In other words, S contains all m's which can be reached optimally in the excess problem using their exact solutions. Here's the beginning of S with the associated optimal factors (as produced by the algorithm for finding a single optimal solution described above) and minimal cost:
  157.  
  158. m = 2: factors = [2], cost = 4
  159. m = 3: factors = [3], cost = 5
  160. m = 4: factors = [4], cost = 6
  161. m = 5: factors = [5], cost = 7
  162. m = 6: factors = [6], cost = 8
  163. m = 7: factors = [7], cost = 9
  164. m = 8: factors = [2, 4], cost = 10
  165. m = 9: factors = [3, 3], cost = 10
  166. m = 10: factors = [2, 5], cost = 11
  167. m = 12: factors = [3, 4], cost = 11
  168. m = 15: factors = [3, 5], cost = 12
  169. m = 16: factors = [4, 4], cost = 12
  170. m = 18: factors = [3, 6], cost = 13
  171. m = 20: factors = [5, 4], cost = 13
  172. m = 21: factors = [3, 7], cost = 14
  173. m = 24: factors = [4, 6], cost = 14
  174. m = 25: factors = [5, 5], cost = 14
  175. m = 27: factors = [3, 3, 3], cost = 15
  176. m = 28: factors = [7, 4], cost = 15
  177. m = 30: factors = [5, 6], cost = 15
  178. m = 32: factors = [2, 4, 4], cost = 16
  179.  
  180. (You can use the program to calculate higher values, I can go up to 2^20 in less than a minute and the program isn't even optimized whatsoever.) For example, reaching 14 exactly has a minimal cost of 13, but by rounding it up to a higher m (in this case we have two options: 15 and 16, since they have the same minimal cost) we can reduce the minimal cost to 12. For any number, we can get the optimal excess solution by using the exact solution of the nearest m in S larger than the given number. However, we can also round up to a higher m as long as it has the same minimal cost. For this purpose, we will define the ordered series T = {m | m is an integer >= 2 and there exists no o > m with cost(o) <= cost(m)}, the only difference being the comparison of cost(o) and cost(m). This simply filters out all m's with the same minimal cost except for the highest one, since that one is enough to cover all the other ones without losing optimality. At this point we will abandon these co-optimal solutions in order to reduce the complexity of the problem. After all, the goal was to find a simple procedure to find an optimal solution, not necessarily all optimal solutions. Using the same program, I calculated the beginning of T:
  181.  
  182. m = 2: factors = [2], cost = 4
  183. m = 3: factors = [3], cost = 5
  184. m = 4: factors = [4], cost = 6
  185. m = 5: factors = [5], cost = 7
  186. m = 6: factors = [6], cost = 8
  187. m = 7: factors = [7], cost = 9
  188. m = 9: factors = [3, 3], cost = 10
  189. m = 12: factors = [3, 4], cost = 11
  190. m = 16: factors = [4, 4], cost = 12
  191. m = 20: factors = [5, 4], cost = 13
  192. m = 25: factors = [5, 5], cost = 14
  193. m = 30: factors = [5, 6], cost = 15
  194. m = 36: factors = [3, 3, 4], cost = 16
  195. m = 48: factors = [3, 4, 4], cost = 17
  196. m = 64: factors = [4, 4, 4], cost = 18
  197. m = 80: factors = [5, 4, 4], cost = 19
  198. m = 100: factors = [5, 5, 4], cost = 20
  199. m = 125: factors = [5, 5, 5], cost = 21
  200. m = 150: factors = [5, 5, 6], cost = 22
  201. m = 192: factors = [3, 4, 4, 4], cost = 23
  202. m = 256: factors = [4, 4, 4, 4], cost = 24
  203. m = 320: factors = [5, 4, 4, 4], cost = 25
  204. m = 400: factors = [5, 5, 4, 4], cost = 26
  205. m = 500: factors = [5, 5, 5, 4], cost = 27
  206. m = 625: factors = [5, 5, 5, 5], cost = 28
  207. m = 768: factors = [3, 4, 4, 4, 4], cost = 29
  208. m = 1024: factors = [4, 4, 4, 4, 4], cost = 30
  209. m = 1280: factors = [5, 4, 4, 4, 4], cost = 31
  210. m = 1600: factors = [5, 5, 4, 4, 4], cost = 32
  211. m = 2000: factors = [5, 5, 5, 4, 4], cost = 33
  212. m = 2500: factors = [5, 5, 5, 5, 4], cost = 34
  213. m = 3125: factors = [5, 5, 5, 5, 5], cost = 35
  214. m = 4096: factors = [4, 4, 4, 4, 4, 4], cost = 36
  215. m = 5120: factors = [5, 4, 4, 4, 4, 4], cost = 37
  216. m = 6400: factors = [5, 5, 4, 4, 4, 4], cost = 38
  217. m = 8000: factors = [5, 5, 5, 4, 4, 4], cost = 39
  218. m = 10000: factors = [5, 5, 5, 5, 4, 4], cost = 40
  219. m = 12500: factors = [5, 5, 5, 5, 5, 4], cost = 41
  220. m = 16384: factors = [4, 4, 4, 4, 4, 4, 4], cost = 42
  221. m = 20480: factors = [5, 4, 4, 4, 4, 4, 4], cost = 43
  222. m = 25600: factors = [5, 5, 4, 4, 4, 4, 4], cost = 44
  223. m = 32000: factors = [5, 5, 5, 4, 4, 4, 4], cost = 45
  224. m = 40000: factors = [5, 5, 5, 5, 4, 4, 4], cost = 46
  225. m = 50000: factors = [5, 5, 5, 5, 5, 4, 4], cost = 47
  226. m = 65536: factors = [4, 4, 4, 4, 4, 4, 4, 4], cost = 48
  227. m = 81920: factors = [5, 4, 4, 4, 4, 4, 4, 4], cost = 49
  228. m = 102400: factors = [5, 5, 4, 4, 4, 4, 4, 4], cost = 50
  229. m = 128000: factors = [5, 5, 5, 4, 4, 4, 4, 4], cost = 51
  230. m = 160000: factors = [5, 5, 5, 5, 4, 4, 4, 4], cost = 52
  231. m = 200000: factors = [5, 5, 5, 5, 5, 4, 4, 4], cost = 53
  232. m = 262144: factors = [4, 4, 4, 4, 4, 4, 4, 4, 4], cost = 54
  233. m = 327680: factors = [5, 4, 4, 4, 4, 4, 4, 4, 4], cost = 55
  234. m = 409600: factors = [5, 5, 4, 4, 4, 4, 4, 4, 4], cost = 56
  235. m = 512000: factors = [5, 5, 5, 4, 4, 4, 4, 4, 4], cost = 57
  236. m = 640000: factors = [5, 5, 5, 5, 4, 4, 4, 4, 4], cost = 58
  237. m = 800000: factors = [5, 5, 5, 5, 5, 4, 4, 4, 4], cost = 59
  238. m = 1048576: factors = [4, 4, 4, 4, 4, 4, 4, 4, 4, 4], cost = 60
  239.  
  240. As we can see, there seems to be a pattern here, especially from m >= 1024 onwards. Define V = {m | m is an element of T and m < 1024}, W = {m | m is an element of T and m >= 1024} (so that V and W are disjoint and T = union(V, W)), V' = {2, 3, 4, 5, 6, 7, 9, 12, 16, 20, 25, 30, 36, 48, 64, 80, 100, 125, 150, 192, 256, 320, 400, 500, 625, 768} and W' = {5^(cost mod 6) * 4^(floor(cost/6) - (cost mod 6)) | for all natural cost >= 30}. We will now try to prove that V = V' and W = W'.
  241.  
  242.  
  243.  
  244.  
  245. 4.2. Proof that T = union(V', W')
  246.  
  247. 4.2.1. Proof that V = V'
  248.  
  249. V = V' has already been proven by construction, assuming my Python program was correctly implemented. Then again, that seems as reasonable as assuming that I didn't make a mistake in my proofs, so although I could be wrong (feel free to correct me) I'll save myself the hassle of a correctness proof. One could also argue that the program output is unreliable since it only calculates a finite amount of values, whereas in order to prove membership of T we have to check an infinite amount. However, as will be proven in the next section (without relying on this section nor the program output, so it's not circular reasoning, I just wanted to show the pattern before proving it), all powers of 4 are part of T. Since the program output ends on one of such powers, we know that there are no higher m's with a cost below or equal to 60, so the values provided by the output are unaffected.
  250.  
  251.  
  252.  
  253. 4.2.2. Proof that W = W'
  254.  
  255. W and W' form a tougher nut to crack. We will first prove that W is a subset of W' by showing that all numbers outside of W' cannot be part of W. Subsequently, we will use this to demonstrate that there can be no elements from W' missing in W either, meaning that the two sets are equal.
  256.  
  257.  
  258.  
  259. 4.2.2.1. Proof that W is a subset of W'
  260.  
  261. 4.2.2.1.1. Factors above 7
  262.  
  263. We will start by proving that no m with optimal factors containing anything above 7 can be part of W, by showing that any number containing these factors can be overestimated by some larger number while still decreasing the cost. After all, the values in W still have the same cost properties as those in T. Specifically, we will do this by just looking at the factors themselves and analyzing their individual effects on the number and cost. As we already know, the algorithm described in the previous paragraph only produces primes, 4 and 6 as factors, so we only have to consider all primes starting at 11.
  264. 11: Can be overestimated using 4*4, decreasing the cost from 13 to 12. Any number containing this factor can be overestimated by a factor of 16/11 while decreasing the cost by 1.
  265. 13: Also 4*4, decreasing the cost from 15 to 12.
  266. Any prime x > 16: Can be overestimated by 4^ceil(log4(x)), changing the cost from x + 2 to 6*ceil(log4(x)). We can show that this change is always strictly negative.
  267. f(x) = x - 6*log4(x) - 4 is always strictly positive for x >= 17. After all, f(17) = 17 - 6*log4(4*17) - 4 = 13 - 6*2.04373... = 0.73761... is positive and f'(x) = 1 - 6/(ln(4)*x) = (x - 3/ln(2))/x, which we can see is positive for all x >= 17 since it is continuous, only has one zero, namely at 3/ln(2) = 4.32809... < 17 and f'(17) = 0.74541 is positive. Therefore, for x >= 17:
  268. x - 6*log4(x) - 4 > 0
  269. <=> x + 2 > 6*log4(x) + 6
  270. <=> x + 2 > 6*(log4(x) + 1)
  271. => x + 2 > 6*floor(log4(x) + 1) (we only possibly lower the right side)
  272. <=> x + 2 > 6*ceil(log4(x)) (equivalent since x is prime so log_4(x) is never whole)
  273. Therefore, overestimating any prime x > 16 with 4^ceil(log4(x)) will result in a decreased cost, meaning these factors can never be part of an optimal solution of some m in T.
  274.  
  275.  
  276.  
  277. 4.2.2.1.2. Small factors
  278.  
  279. Let's continue by showing that no m >= 1024 with optimal factors containing 2, 3, 6 or 7 can be part of W. At this point these factors are getting so small that we need to group them with other factors in order to prove that they can be improved by other groups of factors. We can do this because of the lower bound on m. Bear in mind that all we need to do is to show that by replacing some factors of m by some factors we can produce a bigger number with lower or equal minimal cost. This bigger number doesn't even need to be part of W itself, which means we can use factors besides 4 and 5 even though we will prove those can't produce an element of W either.
  280.  
  281. 7: Since 7 < 1024, m must at least contain other factors. We know at this point that we only need to consider the factors 2, 3, 4, 5, 6 and 7.
  282. 7*2: Can be overestimated with 4*4, decreasing the cost from 13 to 12.
  283. 7*3: Can be overestimated with 5*5, keeping the cost at 14. Remember that we're trying to disprove membership of W, not S, so as long as the cost doesn't increase we know these factors can't produce an element in T nor W.
  284. 7*4: Use 5*6, cost stays 15.
  285. 7*5: Use 6*6, cost stays 16.
  286. 7*6: Use 3*3*5, cost stays 17.
  287. 7*7: Use 4*4*4, cost stays 18.
  288. 6: Since 6 < 1024, m must at least contain other factors. We know at this point that we only need to consider the factors 2, 3, 4, 5 and 6.
  289. 6*2: Use 5*3, cost stays 12.
  290. 6*3: Use 4*5, cost stays 13.
  291. 6*4: Use 5*5, cost stays 14.
  292. 6*5: Since 6*5 < 1024, m must at least contain other factors. We know at this point that we only need to consider the factors 5 or 6 (since else m would contain both 6 and 2, 3 or 4).
  293. 6*5*6 = 180: Use 3*4*4*4 = 192, cost stays 23.
  294. 6*5*5 = 150: Since 6*5*5 < 1024, m must at least contain other factors. We know at this point that we only need to consider the factor 5.
  295. 6*5*5*5 = 750: Use 3*4*4*4*4 = 768, cost stays 29.
  296. 6*6: Since 6*6 < 1024, m must at least contain other factors. We know at this point that we only need to consider the factor 6.
  297. 6*6*6 = 216: Use 4*4*4*4 = 256, cost stays 24.
  298. 3: Since 3 < 1024, m must at least contain other factors. We know at this point that we only need to consider the factors 2, 3, 4 and 5.
  299. 3*2: These factors never appear in an optimal solution, or similarly, use 7, cost stays 9.
  300. 3*5: Use 4*4, cost stays 12.
  301. 3*3: Since 3*3 < 1024, m must at least contain other factors. We know at this point that we only need to consider the factors 3 and 4.
  302. 3*3*3 = 27: Use 5*6, cost stays 15.
  303. 3*3*4 = 36: Since 3*3*4 < 1024, m must at least contain other factors. We know at this point that we only need to consider the factor 4.
  304. 3*3*4*4 = 144: Use 5*5*6 = 150, cost stays 22.
  305. 3*4: Since 3*4 < 1024, m must at least contain other factors. We know at this point that we only need to consider the factor 4. Repeat this reasoning.
  306. 3*4*4*4*4 = 768: Since 3*4*4*4*4 < 1024, m must at least contain other factors. We know at this point that we only need to consider the factor 4.
  307. 3*4*4*4*4*4 = 3072: Use 5*5*5*5*5 = 3125, cost stays 35.
  308. 2: Since 2 < 1024, m must at least contain other factors. We know at this point that we only need to consider the factors 2, 4 and 5.
  309. 2*2: These factors never appear in an optimal solution, or similarly, use 5, cost decreases from 8 to 7.
  310. 2*4: Use 3*3, cost stays 10.
  311. 2*5: Use 3*4, cost stays 11.
  312.  
  313. We now eliminate the final case, where m contains at least six 5's:
  314.  
  315. 5^6 = 15625: Use 4^7 = 16384, cost stays 42.
  316.  
  317. By eliminating numbers that cannot be in W, all that are left now are the products of some amount of 4's and up to five 5's, which is exactly W'. In other words, no number outside of W' can be part of W, since it would not satisfy one of the constraints above and can somehow be increased without increasing its cost. This means that W is at least a subset of W'. However, we still need to prove that none of these numbers in W' cannot be eliminated by further constraints.
  318.  
  319.  
  320.  
  321. 4.2.2.2. Proof that W must contain all elements of W'
  322.  
  323. For this section, remember that W was previously defined as {m | m is an integer >= 1024 and there exists no o > m with cost(o) <= cost(m)}. We will first show that for every cost c >= 30 there will be at least an m in W so that cost(m) = c. This will imply that every element of W' also needs to be in W, so that all costs >= 30 are covered.
  324.  
  325.  
  326.  
  327. 4.2.2.2.1. Initial case
  328.  
  329. We will show that 1024, with cost(1024) = 30, is part of W. For this, let's take a look at a more general game: instead of being limited to multiplying the current value by some integer x at a cost of x + 2, we are allowed to (starting at value 0) add the value ln(x)/(x + 2) for any integer x > 0. This represents the same problem but allows you to to split up a factor x into x + 2 steps, each of which add ln(x) to the current value (we work logarithmically to keep things simple, another equivalent but different game would involve multiplying by x^(1/(x + 2)) every move, the logarithmic base is also arbitrary). By giving ourselves more freedom, we may create optimal solutions which are impossible in the original game. However, since all moves from the original game can still be performed with the same effects in this game, we know that if an optimal solution in this game is a solution in the original game, it is also an optimal solution in the original game.
  330.  
  331. How to reach the maximal value with some limited cost? Let's figure out the maximum value(s) of ln(x)/(x + 2) with x some integer > 0:
  332. f(x) = ln(x)/(x + 2)
  333. f'(x) = 1/x*(1/(x + 2)) + ln(x)*(-1/(x + 2)^2)
  334. = 1/(x*(x + 2)) - ln(x)/(x + 2)^2
  335. = (1/x - ln(x)/(x + 2))/(x + 2)
  336. = ((x + 2)/(x*(x + 2)) - x*ln(x)/(x*(x + 2)))/(x + 2)
  337. = (x + 2 - x*ln(x))/(x*(x + 2)^2)
  338. = ((1 - ln(x))*x + 2)/(x*(x + 2)^2)
  339.  
  340. We will now prove that for all 1 <= x <= 4 f'(x) is strictly positive and for all x >= 5 f'(x) is strictly negative. Consider the function g(x) = (1 - ln(x))*x + 2. Since x > 0, f'(x) will always have the same sign as g(x).
  341.  
  342. g'(x) = (-1/x)*x + (1 - ln(x)) = -1 + 1 - ln(x) = -ln(x)
  343.  
  344. We consider it known that ln(x) has only one zero (at 1), where it changes from negative to positive. As a result, g'(x) is strictly negative for any x >= 5. This means that g(x) will only decrease from this point onward. Since g(5) = −1.04719... is strictly negative, this means g(x), and therefore also f'(x), is strictly negative for all x >= 5. Through similar reasoning we can deduce that g(x) will never increase for 1 <= x <= 4, but since g(4) = 0.45482..., g(x) (and f'(x)) must be strictly positive for all 1 <= x <= 4. If all these functions confused you, you may want to take a look at this graph to visualize things: http://fooplot.com/#W3sidHlwZSI6MCwiZXEiOiJsbih4KS8oeCsyKSIsImNvbG9yIjoiIzAwMDAwMCJ9LHsidHlwZSI6MCwiZXEiOiIoMS1sbih4KSkqeCsyIiwiY29sb3IiOiIjMDAwMDAwIn0seyJ0eXBlIjowLCJlcSI6Ii1sbih4KSIsImNvbG9yIjoiIzAwMDAwMCJ9LHsidHlwZSI6MTAwMH1d
  345.  
  346. Since for all integer x > 0 f(x) monotonically increases at least until 4 and monotonically decreases from at most 5 (all while being a continuous function for x > 0), all values of f(x) for integer x > 0 will be strictly smaller than either f(4) or f(5). We can check that f(4) = 0.23105... > f(5) = 0.22992..., so f(4) is the maximum of all f(x)'s with integer x > 0.
  347.  
  348. This means that in this new game, the highest number you can reach with a given cost c will always be c*f(4), since this will be greater than any sum of length c containing other f(x)'s, since at least one of these will be smaller than f(4) in order for the sum to be different. As a result, for c = 30, the optimal moves are 30 times ln(4)/6, which is equivalent to multiplying by 4^(1/6) 30 times in our original game. This is allowed, since this is the same as multiplying by 4 five times. In other words, even in our new game there's no higher number than 1024 that can be reached with a cost equal to or lower than 30, so definitely not in our original game either. As a result, 1024 is part of W, with cost 30.
  349.  
  350.  
  351.  
  352. 4.2.2.2.2. Recursive case
  353.  
  354. Assuming that W contains an element m with cost c >= 30, we will prove that W also contains an element with cost c + 1. After all, we know that we can take one of m's optimal factors and increase it by one, giving us a larger number with cost c + 1. If this new number m' isn't part of W, that means that there is some number larger than m' with lower or equal cost. However, since m is part of W there are no numbers > m with cost <= c, and since m' > m, this also holds true for all numbers > m'. Therefore, there could only be numbers with equal cost. This higher number m'' would also either have to be part of W, or be superseded by some other higher number m''' with equal cost, and so on ... Since every number needs to be strictly larger than the previous one, they're all integers and we know that there is an upper bound to the values we can reach for some constant cost c + 1 (after all, you could try all possible series of c + 1 moves, of which there are finitely many and which will all lead to finite values, and take the maximum of these values), this reasoning has to stop at some point. As a result, there must also be some number with cost c + 1 which is in W.
  355.  
  356.  
  357.  
  358. 4.2.2.2.3. Finishing off W = W'
  359.  
  360. Since W can only contain elements of W' (as proven in section 4.2.2.1) and must contain at least one m for each cost(m) >= 30, we know no elements from W' can be missing from W. After all, one can easily see that the elements of W' (which are all >= 1024) have costs ranging from 30 to infinity, in steps of 1, with exactly one value per cost: during every step inside one cycle (consisting of 6 steps), we replace one 5 by a 4, increasing the cost by one and after 5 of these steps, we finish the cycle by replacing these five 5's by six 4's, increasing the cost by 6*(4 + 2) - 5*(5 + 2) = 6*6 - 5*7 = 36 - 35 = 1. This goes on to infinity. If any of these values were missing from W, W would not have an m to cover every cost(m) >= 30. This means that the two sets are equal.
  361.  
  362.  
  363.  
  364. 4.3 A simple procedure for n < 1024
  365.  
  366. For small numbers though, we know this pattern doesn't hold true. Instead, we had our program calculate all the elements of V and their optimal solutions:
  367.  
  368. m = 2: factors = [2], cost = 4
  369. m = 3: factors = [3], cost = 5
  370. m = 4: factors = [4], cost = 6
  371. m = 5: factors = [5], cost = 7
  372. m = 6: factors = [6], cost = 8
  373. m = 7: factors = [7], cost = 9
  374. m = 9: factors = [3, 3], cost = 10
  375. m = 12: factors = [3, 4], cost = 11
  376. m = 16: factors = [4, 4], cost = 12
  377. m = 20: factors = [5, 4], cost = 13
  378. m = 25: factors = [5, 5], cost = 14
  379. m = 30: factors = [5, 6], cost = 15
  380. m = 36: factors = [3, 3, 4], cost = 16
  381. m = 48: factors = [3, 4, 4], cost = 17
  382. m = 64: factors = [4, 4, 4], cost = 18
  383. m = 80: factors = [5, 4, 4], cost = 19
  384. m = 100: factors = [5, 5, 4], cost = 20
  385. m = 125: factors = [5, 5, 5], cost = 21
  386. m = 150: factors = [5, 5, 6], cost = 22
  387. m = 192: factors = [3, 4, 4, 4], cost = 23
  388. m = 256: factors = [4, 4, 4, 4], cost = 24
  389. m = 320: factors = [5, 4, 4, 4], cost = 25
  390. m = 400: factors = [5, 5, 4, 4], cost = 26
  391. m = 500: factors = [5, 5, 5, 4], cost = 27
  392. m = 625: factors = [5, 5, 5, 5], cost = 28
  393. m = 768: factors = [3, 4, 4, 4, 4], cost = 29
  394. m = 1024: factors = [4, 4, 4, 4, 4], cost = 30
  395.  
  396. However, this may still be a bit much to remember for a "simple" procedure. Simply remember the first factors of each "level" (determined by the size of the multi-set of factors): [2], [3, 3], [3, 3, 4], [3, 4, 4, 4], [3, 4, 4, 4, 4], [4, 4, 4, 4, 4] and do the following:
  397. 1) Check which "level" n is on by finding the two multi-sets of factors which bound it. If n is already equal to one of these, you've found an optimal multi-set of factors, skip to step 4.
  398. 2) Start at the lowest multi-set of factors of that level.
  399. 3) Replace the lowest factor f by f + 1. If the product of the new multi-set is smaller than n and you have performed this step less than 5 times (6 times if you're on the level of size 3), repeat this step. If the product of the new multi-set is still smaller than n but you have already performed this step 5 times (6 times if you're on the level of size 3), use the first multi-set of factors from the next level.
  400. 4) The multi-set you're left with represents the optimal solution. So, pick an arbitrary element x from the multi-set, remove it, press ctrl+A, press ctrl+C and press ctrl+V x times.
  401. The minimal cost is the sum of all elements of the multi-set and 2 times the size of the multi-set.
  402.  
  403.  
  404.  
  405. 4.4 A simple procedure for n >= 1024
  406.  
  407. After section 4.2.2, we now know we can optimally overestimate any n >= 1024 using the closest but larger or equal m of the form 4^k * 5^l, with k any integer and l any integer smaller than or equal to five. Let's convert this to a simple procedure. The logarithms can have an arbitrary base.
  408.  
  409. Amount of 5's = ceil(ln(n/(nearest power of 4 smaller than or equal to n))/ln(5/4)) = ceil(ln(n/(4^floor(ln(n)/ln(4))))/ln(5/4)) = ceil((ln(n) - ln(4^floor(ln(n)/ln(4))))/ln(5/4)) = ceil((ln(n) - floor(ln(n)/ln(4))*ln(4))/ln(5/4)) = ceil((ln(n) mod ln(4))/ln(5/4))
  410. Amount of 4's = floor(ln(n)/ln(4)) - amount of 5's = floor(ln(n)/ln(4)) - ceil((ln(n) mod ln(4))/ln(5/4))
  411.  
  412. 1) Repeat floor(ln(n)/ln(4)) - ceil((ln(n) mod ln(4))/ln(5/4)) times: press ctrl+A, press ctrl+C and press ctrl+V 4 times.
  413. 2) Repeat ceil((ln(n) mod ln(4))/ln(5/4)) times: press ctrl+A, press ctrl+C and press ctrl+V 5 times.
  414.  
  415. The minimal cost will be 6*(floor(ln(n)/ln(4)) - ceil((ln(n) mod ln(4))/ln(5/4))) + 7*ceil((ln(n) mod ln(4))/ln(5/4)) = 6*floor(ln(n)/ln(4)) + ceil((ln(n) mod ln(4))/ln(5/4)).
  416.  
  417.  
  418.  
  419.  
  420.  
  421. 5. Credits
  422.  
  423. I wouldn't have thought of this problem nor elaborated on it and as a result solve my first somewhat number-theoretical problems if it wasn't for Noerdy (https://twitter.com/TheNoerdy1221) who suggested it to me, so thanks for that. It's also worth noting that the idea that the exact problem implies the RSA problem comes from Maarten Baert (http://www.maartenbaert.be/).
  424.  
  425.  
  426.  
  427.  
  428.  
  429. 6. Source code
  430.  
  431. Here's the code for the Python (2) program I used to calculate the beginning of S and T. It also has some other functionality. I didn't really mean to publish it, so turning the right parts on/off or understanding how it works may be a bit tedious, however I think it shouldn't be a big problem. The pylab module is only necessary in order to generate graphs.
  432.  
  433. # Calculates the optimal spamming strategy for each n up till and including limit
  434.  
  435. # Imports
  436. from math import sqrt, ceil
  437. from pylab import *
  438.  
  439. # Highest possible value for n, used in prime generation, factorization, ...
  440. limit = 2**20
  441.  
  442. # Prime generator
  443. primes = [2]
  444. for number in xrange(3, int(ceil(sqrt(limit))), 2):
  445. divisible = False
  446. for divisor in primes:
  447. if number%divisor == 0:
  448. divisible = True
  449. break
  450. if divisor**2 >= number:
  451. break
  452. if not divisible:
  453. primes.append(number)
  454.  
  455. def factorize(n):
  456. # Factorizes n, returns a sorted list of prime factors. Doesn't necessarily work if n > limit
  457. prime_factors = []
  458. index = 0
  459. while (index < len(primes)):
  460. prime = primes[index]
  461. if n%prime == 0:
  462. prime_factors.append(prime)
  463. n /= prime
  464. elif prime**2 > n:
  465. break
  466. else:
  467. index += 1
  468. if n > 1:
  469. prime_factors.append(n)
  470. return prime_factors
  471.  
  472. def factorize_test():
  473. # Tests factorize(n)
  474. for n in xrange(2, limit + 1):
  475. prime_factors = factorize(n)
  476. product = 1
  477. for prime in prime_factors:
  478. if prime not in primes and prime < primes[-1]:
  479. print "Prime not in primes: " + str(prime)
  480. product *= prime
  481. if product != n:
  482. print "Factorization didn't multiply correctly! n: %s, value: %s"%(n, product)
  483.  
  484. def calculate_optimal_solution(n):
  485.  
  486. # Calculates and returns the optimal solution for a given n. Doesn't necessarily work if n > limit
  487.  
  488. # Step 1: factorize
  489. factors = factorize(n)
  490.  
  491. # Step 2.1: merge 2's. Keeps 2's and 3's at the front, only adds 4's to the back, so we don't need to search for 2's and 3's
  492. while len(factors) >= 2 and factors[0:2] == [2, 2]:
  493. factors = factors[2:] + [4]
  494.  
  495. # Step 2.2: merge odd 2 together with 3
  496. if len(factors) >= 2 and factors[0:2] == [2, 3]:
  497. factors = factors[2:] + [6]
  498.  
  499. # Calculate total cost and print results
  500. cost = 0
  501. for factor in factors:
  502. cost += factor + 2
  503.  
  504. return (n, factors, cost)
  505.  
  506. def print_optimal_solution(n):
  507. # Calculates and prints the optimal solution for a given n. Doesn't necessarily work if n > limit
  508. print "n = %s: factors = %s, cost = %s"%calculate_optimal_solution(n)
  509.  
  510. def print_optimal_solutions():
  511. # Calculates and prints the optimal solution for all 2 <= n <= limit
  512. for n in xrange(2, limit + 1):
  513. print_optimal_solution(n)
  514.  
  515. def calculate_optimal_solutions_powers():
  516. # Calculates and prints the optimal solution for all powers of 2 from 2 to limit
  517. n = 2
  518. while n <= limit:
  519. print_optimal_solution(n)
  520. n *= 2
  521.  
  522. def powers_check():
  523.  
  524. # Calculates a bunch of stuff
  525.  
  526. # Calculate for all n's
  527. ns = [] # All 2 <= n <= limit
  528. costs = []
  529. excess_ns = [] # All n's in S or T
  530. excess_costs = []
  531. only_calculate_upper_bounds = False # If True, calculates T, otherwise S
  532. for n in xrange(2, limit + 1):
  533. (n, factors, cost) = calculate_optimal_solution(n)
  534. ns.append(n)
  535. costs.append(cost)
  536.  
  537. # Calculate excess costs (so optimal solution for n is exact optimal solution for n or any higher number)
  538. while len(excess_costs) > 0 and excess_costs[-1] >= cost and (only_calculate_upper_bounds or excess_costs[-1] > cost):
  539. excess_ns.pop()
  540. excess_costs.pop()
  541. excess_ns.append(n)
  542. excess_costs.append(cost)
  543.  
  544. # Calculate for powers of 2
  545. power_ns = [] # Powers of 2
  546. power_costs = []
  547. lower_bound_ns = [] # One step below powers of 2
  548. lower_bound_costs = []
  549. n = 2
  550. while n <= limit:
  551. (n, factors, cost) = calculate_optimal_solution(n)
  552.  
  553. # Plot upper bound, useful for excess problem
  554. if n > 2:
  555. # Cover region
  556. power_ns.append(n/2 + 1)
  557. power_costs.append(cost)
  558. power_ns.append(n)
  559. power_costs.append(cost)
  560.  
  561. # Plot lower bound, seems to show asymptotic behavior
  562. lower_bound_ns.append(n)
  563. lower_bound_costs.append(cost)
  564. if n < limit:
  565. # Cover region
  566. lower_bound_ns.append(2*n - 1)
  567. lower_bound_costs.append(cost)
  568.  
  569. n *= 2
  570.  
  571. # Prints S or T
  572. print_excess_ns = True
  573. if print_excess_ns:
  574. for n in excess_ns:
  575. print_optimal_solution(n)
  576.  
  577. # Plots a bunch of stuff
  578. show_plot = False
  579. if show_plot:
  580. plot(ns, costs, "b")
  581. plot(power_ns, power_costs, "g")
  582. plot(excess_ns, excess_costs, "ro")
  583. plot(lower_bound_ns, lower_bound_costs, "r")
  584. show()
Advertisement
Add Comment
Please, Sign In to add comment