## Computer Science 237 |

**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=2 ^{i}*, then

For example, here is a table of the first few values of
*i* necessary to bring *f ^{i}(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 *f ^{i}(n)* to

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.