The “3n + 1 algorithm” works as follows. Start with any number n. If n is even, divide it...

The “3n + 1 algorithm” works as follows. Start with any number n. If n is even, divide it by 2. If n is odd, replace it with 3n + 1. Repeat. So, for example, if we start with 5, we get the list of numbers

5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, . . . ,

and if we start with 7, we get

7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, . . . .

Notice that if we ever get to 1 the list just continues to repeat with 4, 2, 1’s. In general, one of the following two possibilities will occur:1

(i) We may end up repeating some number a that appeared earlier in our list, in which case the block of numbers between the two a’s will repeat indefinitely. In this case we say that the algorithm terminates at the last nonrepeated value, and the number of distinct entries in the list is called the length of the algorithm. For example, the algorithm terminates at 1 for both 5 and 7. The length of the algorithm for 5 is 6, and the length of the algorithm for 7 is 17.

(ii) We may never repeat the same number, in which case we say that the algorithm does not terminate. 

(a) Find the length and terminating value of the 3n+1 algorithm for each of the following starting values of n:

(i) n = 21

 (ii) n = 13

 (iii) n = 31

(b) Do some further experimentation and try to decide whether the 3n + 1 algorithm always terminates and, if so, at what value(s) it terminates.

---

(c) Assuming that the algorithm terminates at 1, let L(n) be the length of the algorithm for starting value n. For example, L(5) = 6 and L(7) = 17. Show that if n = 8k+4 with k ≥ 1, then L(n) = L(n+1). [Hint. What does the algorithm do to the starting values 8k + 4 and 8k + 5?]

---

(d) Show that if n = 128k + 28 then L(n) = L(n + 1) = L(n + 2).

---

(e) Find some other conditions, similar to those in (c) and (d), for which consecutive values of n have the same length. (It might be helpful to begin by using the next exercise to accumulate some data.) 

1 There is, of course, a third possibility. We may get tired of computing and just stop working, in which case one might say that the algorithm terminates due to exhaustion of the computer!