Unit 3.17-3.18 Group Lesson Period 4
Jupyter Notebook for the rest of the class to follow along with.
- Hailstone numbers
- Number of iterations
- Vocab
- Unit 3, Section 17: Algorithm Efficiency - Kush & Yasha
def collatz(i):
while i > 1:
print(i, end=' ')
if (i % 2):
# i is odd
i = 3*i + 1
else:
# i is even
i = i//2
print(1, end='')
i = int(input('Enter i: '))
print('Sequence: ', end='')
collatz(i)
def collatz(i):
while i != 1:
if i % 2 > 0:
i =((3 * i) + 1)
list_.append(i)
else:
i = (i / 2)
list_.append(i)
return list_
print('Please enter a number: ', end='')
while True:
try:
i = int(input())
list_ = [i]
break
except ValueError:
print('Invaid selection, try again: ', end='')
l = collatz(i)
print('')
print('Number of iterations:', len(l) - 1)
Vocab
Collatz
The Collatz conjecture is one of the most famous unsolved problems in mathematics. The conjecture asks whether repeating two simple arithmetic operations will eventually transform every positive integer into 1.
Hailstone numbers
The sequence of integers generated by Collatz conjecture are called Hailstone Numbers. Examples:Input : N = 7 Output : Hailstone Numbers: 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 No.> ### Iteration The action or a process of iterating or repeating:such as. : a procedure in which repetition of a sequence of operations yields results successively closer to a desired result.
Undecidable problems
An undecidable problem is one that should give a "yes" or "no" answer, but yet no algorithm exists that can answer correctly on all inputs.
Unsolvable problems
An unsolvable problem is one for which no algorithm can ever be written to find the solution.
Additional information
A problem posed by L. Collatz in 1937, also called the 3x+1 mapping, 3n+1 problem, Hasse's algorithm, Kakutani's problem, Syracuse algorithm, Syracuse problem, Thwaites conjecture, and Ulam's problem (Lagarias 1985). Thwaites (1996) has offered a £1000 reward for resolving the conjecture. Let a_0 be an integer. Then one form of Collatz problem asks if iterating
always returns to 1 for positive a_0. (If negative numbers are included, there are four known cycles (excluding the trivial 0 cycle): (4, 2, 1), (-2, -1), (-5, -14, -7, -20, -10), and (-17, -50, -25, -74, -37, -110, -55, -164, -82, -41, -122, -61, -182, -91, -272, -136, -68, -34).)
The members of the sequence produced by the Collatz are sometimes known as hailstone numbers. Conway proved that the original Collatz problem has no nontrivial cycles of length <400. Lagarias (1985) showed that there are no nontrivial cycles with length <275000. Conway (1972) also proved that Collatz-type problems can be formally undecidable. Kurtz and Simon (2007) proved that a natural generalization of the Collatz problem is undecidable; unfortunately, this proof cannot be applied to the original Collatz problem.
The Collatz algorithm has been tested and found to always reach 1 for all numbers <=19·2^(58) approx 5.48×10^(18) (Oliveira e Silva 2008), improving the earlier results of 10^(15) (Vardi 1991, p. 129) and 5.6×10^(13) (Leavens and Vermeulen 1992). Because of the difficulty in solving this problem, Erdős commented that "mathematics is not yet ready for such problems" (Lagarias 1985).
The numbers of steps required for the algorithm to reach 1 for a_0=1, 2, ... are 0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, ... (OEIS A006577; illustrated above). Of these, the numbers of tripling steps are 0, 0, 2, 0, 1, 2, 5, 0, 6, ... (OEIS A006667), and the number of halving steps are 0, 1, 5, 2, 4, 6, 11, 3, 13, ... (OEIS A006666). The smallest starting values of a_0 that yields a Collatz sequence containing n=1, 2, ... are 1, 2, 3, 3, 3, 6, 7, 3, 9, 3, 7, 12, 7, 9, 15, 3, 7, 18, 19, ... (OEIS A070167).
The Collatz problem can be implemented as an 8-register machine (Wolfram 2002, p. 100), quasi-cellular automaton (Cloney et al. 1987, Bruschi 2005), or 6-color one-dimensional quasi-cellular automaton with local rules but which wraps first and last digits around (Zeleny). In general, the difficulty in constructing true local-rule cellular automata arises from the necessity of a carry operation when multiplying by 3 which, in the worst case, can extend the entire length of the base-b representation of digits (and thus require propagating information at faster than the CA's speed of light).
Unit 3, Section 17: Algorithm Efficiency - Kush & Yasha
What is Algorithm Efficiency?
Algorithmic efficiency is an aspect of algorithmic programming that measures the number of steps needed to solve a problem. For instance, If I wanted to create a sorting algorithm that sorts numbers the numbers [2,4,5,1,3]from least to greatest, rather than having an algorithm that compares itself to the next number and swaps accordingly it would be more efficient if you had a program that scans through all the numbers and checks whether a number is smaller or bigger than the rest than and sorts accordingly. Both of the algorithms had the same objective, but one runs more efficiently than the other.
def inefficient_sort(numbers):
# loop over the numbers
for i in range(len(numbers)):
# find the minimum number in the unsorted part of the list
min_index = i
for j in range(i+1, len(numbers)):
if numbers[j] < numbers[min_index]:
min_index = j
# swap the minimum number with the first unsorted number
numbers[i], numbers[min_index] = numbers[min_index], numbers[i]
# return the sorted list
return numbers
# test the algorithm
print(inefficient_sort([2, 4, 5, 1, 3])) # should print [1, 2, 3, 4, 5]
This algorithm uses a nested loop to find the minimum number in the unsorted part of the list and then swaps it with the first unsorted number. This is an inefficient way to sort a list.
def efficient_sort(numbers):
# loop over the numbers
for i in range(len(numbers)):
# find the minimum number in the unsorted part of the list
min_index = i
for j in range(i+1, len(numbers)):
if numbers[j] < numbers[min_index]:
min_index = j
# swap the minimum number with the first unsorted number
numbers[i], numbers[min_index] = numbers[min_index], numbers[i]
# return the sorted list
return numbers
# test the algorithm
print(efficient_sort([2, 4, 5, 1, 3])) # should print [1, 2, 3, 4, 5]
The difference in this algorithm is that it uses a nested loop to find the minimum number in the unsorted part of the list and then swaps it with the first unsorted number.
How do we know if an algorithm is efficient or not?
In the last section, we were talking about a sorting algorithm and we discussed two ways that we could sort the numbers in the order from least to greatest. The reason the second one ran faster than the first one is because scanning all of them is quicker than scanning one by one. An algorithm’s efficiency is determined through formal or mathematical reasoning. My reasoning was more formal than mathematical.
How can you use algorithms to better your life: Mini activity
Just for a second, think about all the tasks in your life that would work so much better automated. The sky's the limit. For an activity, write down or take a mental note of a task that you encounter in your day to day life, and think of ways where you can automate that task. An example of this would be me creating an algorithm for my morning routine.
tasks = ["wake up", "eat breakfast", "brush teeth", "go to school"]
def complete_tasks(tasks):
for task in tasks:
# code to complete each task goes here
if task == "wake up":
print("Waking up now!")
elif task == "eat breakfast":
print("Eating breakfast now!")
elif task == "go to school":
print("Going to school now!")
# and so on for each task in the list
# call the function to complete the tasks
complete_tasks(tasks)
Taking a heuristic approach to problems P1
Sometimes when a problem has too many possibilities, a heuristic approach would be taken. let's use planes as an example. Imagine you were a musician on tour. You have shows in New Zealand, United States, Canada, and Russia. Well, what would be the shortest flight route so you can arrive at those destinations as fast as possible? You start in the United States.
Taking a heuristic approach to problems P2
Well, since there are multiple possibilities, I chose to pick the countries closest to each other. The reason I chose this algorithm in particular is that it made the most sense. I had to start at United States, but then I went on to Canada, Russia, New Zealand, and then back to the United States.
Hacks/assignment
- Write 2 algorithms to sort a list of numbers from greatest to least. Detail exactly what your algorithm does in your fastpages. No coding in this step
- Explain why one algorithm is more efficient than another using mathematical and/or formal reasoning
- use variables, if statements, and loops to program your algorithm and upload to jupyter notebooks/ fastpages