Transcribed Text
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 ####
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.
'''
Problem 1a
'''
def planner(k):
if k == 0: # Base case: k = 1
return [] # Return empty list
elif k == 1: # Base case: k = 0
return [[1]] # Return [[1]]
queue = [[1]] # Initial list value
done = False # Done flag
while done == False:# Run in a loop
nextQueue = [] # Construct list of next possibilities
for q in queue: # Iterate through the last list of lists
for i in q: # Iterate through each element of the list
lastValue = q[-1] + i # Find new last value
if lastValue == k: # If the last value equals k
done = True # We are done!
nextQueue.append(q + [lastValue]) # Add new list
queue = nextQueue[:] # Set list to next list
result = [] # Construct empty list of result
for q in queue: # Iterate through list of values
if q[-1] == k: # Find matches where last value is k
result.append(q) # Add to result
return result # Return result...