Hailstone sequence

Revision as of 00:03, 8 March 2010 by rosettacode>Paddy3118 (New task and Python solution. (second time lucky))
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

The Hailstone sequence of numbers can be generated from a starting positive integer, n by:

  • If n is 1 then the sequence ends.
  • If n is even then the next n of the sequence = n/2
  • If n is odd then the next n of the sequence = (3 * n) + 1
Task
Hailstone sequence
You are encouraged to solve this task according to the task description, using any language you may know.

The (unproven), Collatz conjecture is that the hailstone sequence for any starting number always terminates.

The task is to:

  1. Create a routine to generate the hailstone sequence for a number.
  2. Use the routine to show that the hailstone sequence for the number 27 has 112 elements starting with 27, 82, 41, 124 and ending with 8, 4, 2, 1
  3. Show the number less than 100,000 which has the longest hailstone sequence together with that sequences length.
    (But don't show the actual sequence)!

Python

<lang python>def hailstone(n):

   seq = [n]
   while n>1:
       n = 3*n + 1 if n & 1 else n//2
       seq.append(n)
   return seq

if __name__ == '__main__':

   h = hailstone(27)
   assert len(h)==112 and h[:4]==[27, 82, 41, 124] and h[-4:]==[8, 4, 2, 1]
   print("Maximum length %i was found for hailstone(%i) for numbers <100,000" %
         max((len(hailstone(i)), i) for i in range(1,100000)))</lang>

Sample Output

Maximum length 351 was found for hailstone(77031) for numbers <100,000