Hailstone sequence
Hailstone sequence
You are encouraged to solve this task according to the task description, using any language you may know.
You are encouraged to solve this task according to the task description, using any language you may know.
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
The (unproven), Collatz conjecture is that the hailstone sequence for any starting number always terminates.
The task is to:
- Create a routine to generate the hailstone sequence for a number.
- Use the routine to show that the hailstone sequence for the number 27 has 112 elements starting with
27, 82, 41, 124
and ending with8, 4, 2, 1
- 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