The hailstone sequence and recursion

The January 1984 issue of Scientific American contained an article on a sequence of numbers known as a hailstone sequence, also known as the Collatz Conjecture, the 3n+1 problem, the Syracuse problem, Hasse’s algorithm, and Kakutani’s problem. It is credited to German mathematician Lothar Collatz in 1937, however Collatz did not publish anything on the conjecture until 1986 [1], stating that he did not publish anything earlier because he could not solve the problem. The Collatz Conjecture states that “starting from any positive integer n, repeated iteration of [the Collatz function] eventually produces the value 1” [2]. This has been shown for every number just shy of 260 [3]. The series is formed in the following manner:

1. Pick a number.
2. If its odd, triple the number and add one.
3. If its even, divide the number by two.

Why is the sequence likened to a hailstone? It is so named because the values are subject to multiple ascents and descents, akin to hailstone formation in a cloud. Also, once the value hits a power of two, it moves towards termination in a rapid manner, as does a hailstone. As a function it can be defined in the following manner:

For example, starting with n = 11, the sequence takes longer to reach 1: 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. In reality, it has no real world application, but it provides an interesting exercise in the structure of recursion.

Recursively, it is also easy to define, because the task of deriving a hailstone series is involved with processing a number a series of times until its value turns to 1. Here is a Fortran program to solve the hailstone sequence recursively:

program collatz
   implicit none
   integer :: h

   write(*,*) "Hailstone seed? "
   read(*,*) h
   call hailstone_r(h)
   write(*,*)

contains

recursive subroutine hailstone_r(n)
   integer, intent(in) :: n

   write(*,"(i4,' ')",advance="no") n
   if (n /= 1) then
      if (mod(n,2) == 1) then
         call hailstone_r(3*n+1)
      else
         call hailstone_r(n/2)
      end if
   end if

end subroutine hailstone_r

end program collatz

Note that the first if statement in the function hailstone_r() terminates the sequence. If this is not performed, the sequence 4, 2, 1 will be repeated infinitely (eventually causing the recursion to crash). Here is the sequence for n=57:

57  172   86   43  130   65  196   98   49  148   
74   37  112   56   28   14    7   22   11   34   
17   52   26   13   40   20   10    5   16    8    
4    2    1

Further reading:

1. Collatz, L., “On the motivation and origin of the (3n+1) problem” (Chinese), J. Qufu Normal University, Natural Science Edition, 3, pp.9-11 (1986)
2. Lagarias, J., “The 3x + 1 problem and its generalizations”, American Math Monthly, 92, pp.3-23 (1985)
3. Roosendaal, E., “On the 3x + 1 problem”, http://www.ericr.nl/wondrous/index.html (2011)