Computer Science 237
Computer Organization

Williams College
Fall 2006

Lab Bonus: Syracuse Sequences
Due: Monday, November 13, 2006 at 9:00 AM

This is an optional lab assignment. By completing this lab successfully, you can earn up to 20 points added to any other lab grade this semester (not to exceed 100% credit on the lab whose grade is being raised).

Some very simple functions can lead to very complex behavior. Consider, for example, the "3n+1" function, studied by several mathematicians: if n is odd, f(n)=3n+1, otherwise f(n)=n/2. The assignment increases the value for half of the integers, n, and decreases for the other half. Notice that if n=2i, then fi(n)=1 - that is, i repeated applications of f ultimately results in the value 1. There is, in fact, good evidence that for all n >= 1, fi(n)=1 for some i >= 0. This conjecture, called the Collatz Conjecture, or the Syracuse problem, or Kakutani's problem, or Ulam's problem, remains open. The value of the exponent, i, can fluctuate quite a bit.

For example, here is a table of the first few values of i necessary to bring fi(n) to unity:

n i n i n i n i n i
1 0 2 1 3 7 4 2 5 5
6 8 7 16 8 3 9 19 10 6
11 14 12 9 13 9 14 17 15 17
16 4 17 12 18 20 19 20 20 7
21 7 22 15 23 15 24 10 25 23
26 10 27 111 28 18 29 18 30 18
31 106 32 5 33 26 34 13 35 13
36 21 37 21 38 21 39 34 40 8
41 109 42 8 43 29 44 16 45 16
46 16 47 104 48 11 49 24 50 24
51 24 52 11 53 11 54 112 55 112
56 19 57 32 58 19 59 32 60 19
61 19 62 107 63 107 64 6 65 27
66 27 67 27 68 14 69 14 70 14
71 102 72 22 73 115 74 22 75 14
76 22 77 22 78 35 79 35 80 9
81 22 82 110 83 110 84 9 85 9
86 30 87 30 88 17 89 30 90 17
91 92 92 17 93 17 94 105 95 105
96 12 97 118 98 25 99 25 100 25

We can experiment with this function using the following C code: 

    int n;
    int i=0;
    scanf("%d",&n);
    while (n != 1) {
       n = (n&1) ? 3*n+1 : n/2;
    }
    printf("%d\n",i);

For positive, non-zero values of n, this code prints the value of the exponent, i, that brings fi(n) to 1. Notice that it is possible to print zero, and that in general, we know little about whether this code ever halts.

Your (optional) task is to implement this bit of code as a circuit in LogicWorks. This circuit should accept an 8-bit value from two hexadecimal keypads and an initialization signal. After the initialization signal is dropped, the circuit should, over time, compute and display the value of i discussed above, and then stop to display the answer. Since the intermediate values of n can get to be quite large (as large as 13120 for n <= 255), it is best to store these values in 16 unsigned bits. (If you promise never to enter a value larger than 702, you may use a larger input. The maximum i for this range of values occurs for n=649 and the maximum value encountered is 41,524.)

When you have completed this assignment, copy your circuit file to the FreeBSD systems and turn it in. Please name your circuit Syracuse.LW4 and submit it with the usual turnin command.