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.” [1]

 

 

  1. 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.

 

  1. 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].

 

  1. 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:

  1. Why do you suppose it takes so long?
  2. 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.



[1] Will My Algorithm Terminate, Peter Winkler, Communications of the ACM, February 2009, 52(2), 104

[2] http://www.cplusplus.com/reference/clibrary/ctime/