CIS 1.5 Science Section
Brooklyn
College
Professor Langsam
Assignment #2 – Collatz Conjecture
“Possibly
the most notorious algorithm termination puzzle of all time – among mathematicians
anyway – is the Collatz Conjecture, sometimes called the 3x+1 problem (or the
Syracuse problem, Kakutani’s problem, Hasse’s algorithm, or Ulam’s problem).
Start with any positive integer and repeat: If it is even, divide by two; if it
is odd, multiply by 3 and add 1. For example, if you start with 22, you get 11,
34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, …
The
conjecture is that no matter what number you start with, you will eventually
get down to the same cycle 4, 2, 1, repeating over and over.”
- Write a C++ program to verify
the Collatz Conjecture for the numbers 1 to 10. Your program should
consist of a for loop which runs from 1 to 10 which in turn
contains a while loop that prints the numbers generated by the
Collatz algorithm. How will you know when to terminate the while
loop? Hint: if you generate the number 1, by definition you have entered
into the infinitely repeating sequence 4, 2, 1, …. Note: This program
contains no input.
- Using the program you have
developed in Step 1, see how long it might take to verify the Collatz
Conjecture for the numbers 1 to 10000. Warning: Be prepared to wait a long
time. Do NOT produce a hardcopy for this experiment. Investigate the use
of the time function in the C++ ctime library[2].
- Plot the execution time of
your program for limiting values of 10, 50, 100, 500, 1000, 5000, 10000
and 20,000. What kind of curve is produced? (You may want to use Excel to
graph your results.)
Questions:
- Why do you suppose it
takes so long?
- Can a computer be used to
verify whether this algorithm terminates? Can a computer be used to
determine whether any algorithm terminates? Investigate the
“Halting Problem.”
Be
sure your program is clearly documented, well structured and uses meaningful
variables. Along with your program and your results, submit a brief report and
graph that discusses the above questions.