PROBLEM SET 1: RECURSION INSTRUCTIONS: 1) The programs in Problem...

PROBLEM SET 1: RECURSION INSTRUCTIONS: 1) The programs in Problems 1a-b, and Problem 2 do not need each other to work. 2) All the required material for this problem sheet has been covered in the Lectures and Tutorials. You can find examples in the online notebooks. If you use a book, please cite the reference 3) Problem 1a - TASK 3 require analytical solution (by hand written in Latex). 4) Just open the notebook file on Jupyter/IPython or any IDE that you like and start playing. 4) All code should be done in Python. 5) READ EVERYTHING CAREFULLY. Problem 1: Fastest Exponentiation in the World. In lecture we discussed the following two problems: 1) Finding the smallest number path to get from 1 to 100 using only increment and square. 2) Making a program for fast exponentiation using the mathematical properties of integer powers. It turns out these problems are loosely related. For example: suppose we want to compute . There are several ways to do it. The most obvious would be to do the following: n15 2 This requires 14 multiplications. Two other ways to do it would be the following: Either of these methods require 6 multiplications. There is also an optimal method: This method requires 5 multiplications. It's not possible to do better. Hopefully you can see the similarities to the problem from Lecture 2: How to chain sequences of arithmetical operations to get from one number to another. That is, we have the sequence: It turns out this is not unique. There are also 3 other ways to do the same thing: n × n n × n2 n × n3 n × n4 n × n5 n × n6 n × n7 n × n8 n × n9 n × n10 n × n11 n × n12 n × n13 n × n14 = = = = = = = = = = = = = = n2 n3 n4 n5 n6 n7 n8 n9 n10 n11 n12 n13 n14 n15 n × n n ×2 n2 n ×4 n4 n ×4 n8 n ×2 n12 n × n14 = = = = = = n2 n4 n8 n12 n14 n15 or n × n n × n2 n ×3 n3 n × n6 n ×7 n7 n × n14 = = = = = = n2 n3 n6 n7 n14 n15 n × n n × n2 n ×2 n3 n ×5 n5 n ×5 n10 = = = = = n2 n3 n5 n10 n15 1 → 1 + 1 = 2 → 1 + 2 = 3 → 2 + 3 = 5 → 5 + 5 = 10 → 5 + 10 = 15 1 1 1 → → → 1 + 1 = 2 1 + 1 = 2 1 + 1 = 2 → → → 1 + 2 = 3 1 + 2 = 3 2 + 2 = 4 → → → 3 + 3 = 6 3 + 3 = 6 1 + 4 = 5 → → → 3 + 6 = 9 6 + 6 = 12 5 + 5 = 10 → → → 6 + 9 = 15 3 + 12 = 15 5 + 10 = 15 Problem 1a: For any non-negative integer , create two functions: and For example: These function should give the correct value for any integer up to in less than a few seconds. Hint: There is no known short cut to solving this problem. Make and update a list of lists. Problem 1, TASK 0: Make a Python function called planner(k). This should return a list of the possible sequences. For example: planner(15) should give: [ [1, 2, 3, 5, 10, 15], [1, 2, 3, 6, 9, 15], [1, 2, 3, 6, 12, 15], [1, 2, 4, 5, 10, 15] ]. Hint: This shouldn't be as complicated as it might seem. My planner required about 15 lines of code. In [15]: #### INSERT CODE HERE #### Problem 1, TASK 1:: What are planner(0), planner(1), and planner(2)? In [16]: #### INSERT CODE HERE #### Problem 1a, TASK 2:: What is planner(20)? k m(k) = minimum number of multiplications needed to compute n , k d(k) = number of optimal solutions. m(15) = 5, d(15) = 4 In [17]: #### INSERT CODE HERE #### Problem 1a, TASK 3:: What is planner(k) if is a power of 2? Note: this is not a code question. I want to know the answer for any power of 2. In [18]: #### INSERT COMPLETE SOLUTION HERE #### Problem 1a, TASK 4: Using the results from TASK 1, make the two functions m(k), d(k). In [19]: #### INSERT CODE HERE #### Problem 1a, TASK 5: Make a plots of and for . Make sure to label them nicely. Note: It might take a minute or two to generate all the plans from . If it takes much longer than about 5-10 minutes you might have a problem with your code. In [20]: #### INSERT CODE HERE #### Problem 1a, TASK 6: What is the maximum value of d(k) for ? In [21]: #### INSERT CODE HERE #### Problem 1a, TASK 7: What are m(200) and d(200)? In [22]: #### INSERT CODE HERE #### k m(k) d(k) 0 ≤ k ≤ 150 0 ≤ k ≤ 150 k ≤ 150 Problem 1b: It might seen like using planner(k) is a bit computationally expensive and complicated for something a simple as computing . This is true if is an integer. However, planner doesn't care what is; only k. 1) The symbol could be a number, a function, or a large matrix. Individual multiplication could be much more difficult than with integers. 2) We could also want to do a large number computations of with different values of for the same value of . This might make the overhead associated with the planner less important. nk n n n nk n k For both of these reasons, we might want to make a computational plan, and then execute that plan for specific values of n. This is a strategy used by some very important and advanced software packages. Problem 1b, TASK 0: Make a function that accepts a single list of the form that comes out of planner(k) and computes for that plan. Call this function fasetest_exp(n,plan) For example, in the case of planner(15) [ [1, 2, 3, 5, 10, 15], [1, 2, 3, 6, 9, 15], [1, 2, 3, 6, 12, 15], [1, 2, 4, 5, 10, 15] ]. You could take the first list in this list and call fasetest_exp(3, [1, 2, 3, 5, 10, 15]) This should compute Also make sure your computation behaves well for and . Hints: 1) 2-1=3, 3-2=1, 5-3=2, 10-5=5, 15-10=5 2) Use a dictionary to store past data that you'll need in your computation. 3) My fastest_exp required about 10 lines of code. In [23]: #### INSERT CODE HERE #### In [ ]: Problem 2: Collatz sequences nk 3 × 3 3 × 9 9 × 27 243 × 243 243 × 59049 = = = = = 9 27 243 59049 14348907 k = 0 k = 1 Define the function that acts on positive integers This function has the property More interestingly We can start with any positive integer and iterate For example if , then There is an open conjecture that every iterated sequence eventually gets to 1. No matter what the value of . For our purposes, it's as good as true. It's been checked for all numbers up to very very large values. Please let me know if you find a counterexample. You'll become very popular with a lot of mathematicians. f(n) = ⎧ ⎩ ⎨ ⎪ ⎪ n 2 3n + 1 if n is even if n is odd f(4) = 2, f(2) = 1, f(1) = 4 n0 n = f( ) k+1 nk n0 = 7 f(7) f(22) f(11) f(34) f(17) f(52) f(26) f(13) f(40) f(20) f(10) f(5) f(16) f(8) f(4) f(2) = = = = = = = = = = = = = = = = 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 Problem 2, TASK 0: Define a function called f(n) that computes . I want the result to always be an integer data type. I want 8/2 = 4. Not 8/2 = 4.0. Be careful about this. Hints: 1) It should be straightforward to write this function in 3-6 lines of code. 2) You already have a bunch of values for this that you can test against. In [24]: #### INSERT CODE HERE #### Problem 2, TASK 1: Define a function called collatz(n) that computes the sequence for any starting value and returns the result in a list. For example collatz(7) Should return [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1] Hints: 1) collatz(n) should use f(n); not redefine it. 2) It should be straightforward to write this in about 5-10 lines of code. Use a while loop. In [25]: #### INSERT CODE HERE #### Problem 2, TASK 2: Make a plot of the length of collatz(n) for . For example for length(collatz(n)) = [1, 2, 8, 3, 6, 9, 17, 4, 20, 7] f(n) n = f( ) k+1 nk 1 ≤ n ≤ 500 In [26]: #### INSERT CODE HERE #### Problem 2, TASK 3: Make a Histogram plot of the length of collatz(n) for . Hints: 1) Adjust the number of bins to make the picture look good. Somewhere around 100-300 should work. 2) You should be able to get to without too much trouble. You will be able to go to much larger ranges of if you keep track of old sequences. Remember, once a sequence joins on to a previous one, then we already know the answer. Problem 2, TASK 4: What is 42**42? What is lenght(collatz(42**42))? In [27]: #### INSERT CODE HERE ####