# 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 = 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 = 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)

(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 = 0 hailstone_depth2 = [0 for i in srange(N)] for i in srange(2,N): v = hailstone(i,K) hailstone_depth2[i] = v s[i] = v 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) 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 = 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) == 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.