Math 3600 2014.09.10 HW

2634 days ago by bburkho

MATH 3600 Fall 2014

HW Due Friday September 10 in Class

Name: 

Edit the text blocks of this worksheet, and insert appropriate code where

indicated, and execute the code.  Write up a conclusion at the end of the

worksheet indicating what you have found.   

In the following execution block, enter the definition of the function $f$ which takes

$n$ to $n/2$ if $n$ is even, and $3n+1$ if $n$ is odd.   

Obtain a new exectution block below it, and evalute $f(10)$ and $f(5)$.

 

def f(n): if n.is_integer(): if is_even(n): n = n/2 else: n = 3*n+1 return n 
       
f(10) 
       
5
5
f(5) 
       
16
16

In the execution block below enter the code set $N$ to 1001 and to create a

list s[] of length $N$, in which $s[n]$ is the number of steps or iterations of $f$ it

takes to reach 1.  This should be the code we developed at the beginning of last  week.   

Obtain a new execution block below it, and print the values of $s[n]$ for $n<20$

using the command

      print(s[1:20])

You should check that the values are correct for small values of $n$.

N = 10001 s = [-1 for i in range(N)] s[1] = 0 for n in srange(2,N): #so we update the number we are looking at k = n #make an empty list which will contain the numbers in the sequence iterates = [] #when s[k] == -1 this mean this number has not been in the sequence before #k>N-1 handles the last one while k > N-1 or s[k] == -1: #each time it gets to a number in the sequence add it to the list iterates.append(k) #do the necessary operation at the end of the loop k = f(k) #everytime the sequence reaches a number it has already been to #get the number of iterations it took for that number to get to the cycle j = s[k] #reverse the direction of the list iterates.reverse() #now this goes through each value in the iterates list and assigns #the number of steps it took to get to that value in the s[] list for m in iterates: j += 1 if m <N: s[m] = j 
       
print(s[1:20]) 
       
[0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20]
[0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20]

In the execution block below, enter the code for a function hailstone($n$): this function

should compute the number of iterations directly given input n, keeping track of the largest

value seen so far.  Given input $n$ it should output a pair [steps, maxval], the number of 

steps taken, and the maximum value seen starting at $n$.

In a new execution block below, compute hailstone(6): it should return the pair [8,16].


def hailstone(x,depth): maximum = x count = 0 counter = 0 while x !=1: if x >= depth: counter += 1 count += 1 if is_even(x): x = x/2 else: x = 3*x+1 if x > maximum: maximum = x return [count,maximum,counter] 
       
hailstone(6,20) 
       
[8, 16, 0]
[8, 16, 0]

Insert the code to compute the list  hailstone_depth1 of how often each value $k\leq K$ is taken 

as $s[n]$ for $1 \leq n \leq N$.  This is the code we developed Monday this week.


To compute how long sage takes to compute a series of commands, we precede them

with

t=cputime()

bunch of sage commands

time_taken= cputime(t)

print(time_taken)


For $N=1,000, 10,000, 100,000$, compute how long it takes to

a) compute the first $N$ values of $s$, and

b) compute hailstone_depth1.

If your code is fast enough, compute for $N$=1,000,000 as well.

#this doesn't work but its close t=cputime() N = 100001 s = [-1 for i in srange(N)] hailstone_depth1 = [0 for i in srange(N)] depth = 0 K=20 s[1] = 0 for n in srange(2,N): k = n b = n iterates = [] while k > N-1 or s[k] == -1: iterates.append(k) if k >= K: for y in iterates: if y < N: hailstone_depth1[y] += 1 k = f(k) j = s[k] iterates.reverse() for m in iterates: j += 1 if m <N: s[m] = j print(hailstone_depth1[1:20]) time_taken= cputime(t) print(time_taken) 
       
[0, 0, 0, 0, 0, 0, 6, 0, 1, 0, 5, 0, 2, 0, 8, 0, 4, 0, 4]
9.633535
[0, 0, 0, 0, 0, 0, 6, 0, 1, 0, 5, 0, 2, 0, 8, 0, 4, 0, 4]
9.633535

N = 1000: .108984

N = 10000: .931859

N = 100000: 9.633535

It may not have gotten the depths correct but it still proves that the list is way faster!

After computing these, create a text block below and record the times taken.       

In the execution block below, input the code to compute hailstone_depth2, the same

list computed using the function hailstone(n).  Note that in order to obtain the number of

steps taken you will need to compute

hailstone(6)[0]

(which will return 8) rather than using hailstone(6), which returns [8,16]).     

 

Again, for $N=1,000, 10,000, 100,000$, compute how long it takes to

 

a) compute the first $N$ values of $s$, and

 

b) compute hailstone_depth2.

 

If your code is fast enough, compute for $N$=1,000,000 as well.

 

Create a new text block below the output to record your findings.

def depth(x): t=cputime() N = x K = 20 s = [-1 for i in srange(N)] s[1] = 0 hailstone_depth2 = [0 for i in srange(N)] for i in srange(2,N): v = hailstone(i,K) hailstone_depth2[i] = v[2] s[i] = v[0] time_taken= cputime(t) print(time_taken) 
       
depth(1000) 
       
1.064838
1.064838
depth(10000) 
       
15.298674
15.298674
depth(100000) 
       
194.722398
194.722398

N=1000: 1.064838 s

N=10000: 15.298674 s

N=100000: 194.722398 s

Now use hailstone(n)[1] to test whether $n$ is a champion, that is, if it is larger than

all subsequent iterations of $f$ starting at $n$.  Create a list champs of all champions

less than $10,000$.  Also create a list number_of_champs in which the element

number_of_champs[i] is the number of champions between 100*i+1 and  100*(i+1).

Plot number_of_champs.  

N = 10000 s = [-1 for i in range(N)] s[1] = 0 champions = [0 for i in range(N)] number_of_champs = [0 for i in range(N/100)] for i in range(2,N): if hailstone(i,20)[1] == i: champions[i] = 1 for n in range(0,N/100): number_of_champs[n] = sum(champions[100*n+1:100*(n+1)]) #no idea why this refuses to plot so I will just comment it out #list_plot(number_of_champs) print(number_of_champs) 
       
[18, 16, 15, 15, 12, 12, 12, 12, 10, 15, 11, 10, 14, 8, 13, 6, 14, 6,
14, 11, 5, 13, 10, 7, 11, 8, 7, 7, 13, 11, 6, 6, 14, 11, 8, 7, 10, 9, 9,
12, 3, 7, 10, 12, 13, 8, 8, 6, 13, 8, 12, 8, 10, 5, 9, 8, 8, 13, 9, 15,
6, 8, 8, 5, 14, 11, 5, 15, 9, 7, 11, 3, 13, 6, 6, 10, 11, 9, 13, 10, 5,
8, 5, 9, 5, 15, 8, 11, 9, 13, 9, 10, 12, 16, 14, 13, 14, 16, 14, 16]
[18, 16, 15, 15, 12, 12, 12, 12, 10, 15, 11, 10, 14, 8, 13, 6, 14, 6, 14, 11, 5, 13, 10, 7, 11, 8, 7, 7, 13, 11, 6, 6, 14, 11, 8, 7, 10, 9, 9, 12, 3, 7, 10, 12, 13, 8, 8, 6, 13, 8, 12, 8, 10, 5, 9, 8, 8, 13, 9, 15, 6, 8, 8, 5, 14, 11, 5, 15, 9, 7, 11, 3, 13, 6, 6, 10, 11, 9, 13, 10, 5, 8, 5, 9, 5, 15, 8, 11, 9, 13, 9, 10, 12, 16, 14, 13, 14, 16, 14, 16]

Create one final text block to summarise your findings in the whole worksheet.     

The goal of this assignment was to explore the Hailstone Conjecture. We define a function with input $k$ and if $k$ is odd apply $3*x+1$ while if $k$ is even apply $x/2$. With this function defined we continually call the function until it returns 1. This means that the sequence is terminated and applying the function will only loop around the sequence $4,2,1,4,2,1,...$ We initially did this by building a list which worked by only ever visiting any given number once and then did it by doing the full hailstone sequence starting from any input number. Next we took a look at the number of times a number in the sequence was higher than a given value $K$ for each integer from 1 to 100000. This was also done in different ways with the first utilizing a list and the second just calls the $hailstone(x)$ function that does the whole sequence for an individual number as well as finding the number of times in the sequence $k$ was greater than $K$. Lastly we looked at "champions" where the integer that begins the sequence was the largest one in the sequence and plotted their frequency per hundred integers up to 10000.