Lesson 3.18
Hacks
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).
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.
Hacks
Take the two codes above and combine them so one imput gives the output that contains both the hailstone numbers and the number of iterations it takes i = 1. The more efficient the code, the higher your grade will be. (Algorithm Efficency) (.25)
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)