CS19002 Programming and Data Structures Laboratory Spring 2010, Section 5

Assignment 1

Start with a positive integer n. If n is even, divide it by 2, else replace n by 3n+1. Repeat until we obtain the value 1 in the sequence. The 3x+1 conjecture says that we eventually reach 1 irrespective of what initial value of n we start with.

Different initial values of n lead to different numbers of iterations of the loop before hitting the value 1. For example, if we start with n=3, we get a sequence 3,10,5,16,8,4,2,1 using 7 iterations. If we start with 7, we need 16 iterations, since the sequence is now 7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1.

You are given a bound B. Your task is to locate that particular value of n in the range 1<=n<=B for which the number of iterations is maximum. Once this integer n is located, you print n, the corresponding number of iterations, and finally the sequence associated with n.

If the bound is 10, then the output of your program would look like:

   Maximum number of iterations = 19 for n = 9.
   The sequence is:
           9       28       14        7       22       11       34       17
          52       26       13       40       20       10        5       16
           8        4        2        1

Report the output of your program for the bound 100,000.

Lab Home Submission Site My Home