All You Need to Know About Hailstone Sequence in Python

Lets us first understand what a sequence is in the hailstone sequence python. A sequence is an ordered series of numbers that follows a particular pattern. A sequence can be something as simple as a series of odd numbers. A hailstone sequence is a series of numbers that increase and decrease while following a pattern and eventually end when a repeating pattern is found.

Contents

Introduction to Hailstone Sequence

The Hailstone sequence is also known as The Collatz Conjecture. It was a problem proposed by mathematician L. Collatz. It is known as the hailstone sequence because the sequence resembles the pattern of formation of hailstones. Hailstones get blown up by the winds in the cloud, come down when they form ice pellets, and again get blown by the winds. Similarly, the sequence increases and decreases its value alternatively. Thus, according to the sequence, we may start with any whole number but will always end up with the sequence of 4, 2, 1.

We start with a given number, ‘N..’ If the number N is even, we will divide it by 2. Otherwise, if N is odd, multiply N by 3 and add 1 to it (3*N + 1). Thus, irrespective of the number we start with, the sequence will never be infinite and always come to an end.

Let us understand the hailstone sequence by taking an example.

Example of Hailstone Sequence

Let us taking N = 5. Since N is odd, We will perform (3*N + 1) = (3*5 + 1) = 16

Now, 16 is even, so we will divide it by 2 = 16/2 = 8.

We will follow the same pattern for the entire series.

8 is even, so 8/2 = 4 4 is even, so 4/2 = 2 2 is even, so 2/2 = 1 1 is odd, so (3*1 + 2) = 4. Now, here as you can see, the sequence is repeating itself. It generated 4 again. So the sequence stops here.

Therefore, the sequence for N = 5 is 5, 16, 8, 4, 2, 1

Let us take another example of N = 6

6 is even, so 6/2 = 3 3 is odd, so (3*3 + 1) = 10 10 is even, so 10/2 = 5 5 is odd, so (3*5 + 1) = 16 16 is even, so 16/2 = 8 8 is even, so 8/2 = 4 4 is even, so 4/2 = 2 2 is even, so 2/2 = 1 1 is odd, so (3*1 + 1) = 4.

The hailstone sequence for N = 6 is 6, 3, 10, 5, 16, 8, 4, 2, 1

As seen, for n = 6 too, the sequence is ending with 4, 2, 1 and is finite.

Computing the Sequence

Let us write a program in python to calculate the hailstone sequence. We will try to implement it both, recursively and non-recursively. The sequence would be generated by taking the initial number of the sequence from the user as an input. The output would be the hailstone sequence in python generated along with the number of steps taken to find the entire sequence.

Without Recursion(while loop)

First, we will define a function named hailstone().

def hailstone(n):
  hailstone_list = []
  hailstone_list.append(int(n))
  while n != 1:
    if n % 2 == 0:
      n = n/2
      hailstone_list.append(int(n))
    else:
      n = 3*n + 1
      hailstone_list.append(int(n))
  return hailstone_list

It will accept one argument n – which is the beginning number of the sequence and will return a list. There will be a while loop that will stop the execution if n becomes 1. We have a list named hailstone_list which will store the sequence. If n is even, n would be divided by 2 else it will be multiplied by 3 and then 1 will be added to it. The numbers would be appended to the list.

n = int(input("Enter n:"))
hailstone_list = []
hailstone_list = hailstone(n)
print("Hailstone Sequence for n = {} is : {}".format(n, hailstone_list)) 
print("Number of steps is : ",len(hailstone_list))

Here, n would be taken as input from the user. We call hailstone function by passing n as the argument and store the return value inside an empty list hailstone_list. Then the print statements will print the hailstone sequence and the number of steps.

Enter n:7

Hailstone Sequence for n = 7 is : [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

Number of steps is :  17

Here also the sequence has terminated with 4, 2, 1.

Also, Read | Understanding Collatz Sequence in Python

With Recursion

Now, we will be implementing the hailstone sequence in python with the help of recursion. If n is one, we will return the hailstone_list. If n is an even number, we shall call the hailstone() function by recursion and pass n/2 as the argument. Else if n is an even number, we shall call hailstone() function by recursion but pass (3*n + 1) as the argument to the function.

hailstone_list = []
def hailstone(n):
  hailstone_list.append(int(n))
  if n == 1:
    return hailstone_list
  while n != 1:
    if n % 2 == 0:
      return hailstone(int(n/2))
    else:
      return hailstone(int(3*n + 1))

n = int(input("Enter n:"))
hailstone_list = []
hailstone_list = hailstone(n)
print("Hailstone Sequence for n = {} is : {}".format(n, hailstone_list)) 
print("Number of steps is : ",len(hailstone_list))

The output for different values of n is:

N = 7:

Enter n:7
Hailstone Sequence for n = 7 is : [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
Number of steps is :  17

N = 6:

Enter n:6
Hailstone Sequence for n = 6 is : [6, 3, 10, 5, 16, 8, 4, 2, 1]
Number of steps is :  9

Even for large values of n, the sequence shall always end with 1.

Enter n:19840

Hailstone Sequence for n = 19840 is : [19840, 9920, 4960, 2480, 1240, 620, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]

Number of steps is :  93

FAQ’s

Q. What is the longest hailstone sequence?

A. The longest hailstone sequence is for the number 77031 whose length is 351.

Enter n:77031

Hailstone Sequence for n = 77031 is : [77031, 231094, 115547, 346642, 173321, 519964, 259982, 129991, 389974, 194987, 584962, 292481, 877444, 438722, 219361, 658084, 329042, 164521, 493564, 246782, 123391, 370174, 185087, 555262, 277631, 832894, 416447, 1249342, 624671, 1874014, 937007, 2811022, 1405511, 4216534, 2108267, 6324802, 3162401, 9487204, 4743602, 2371801, 7115404, 3557702, 1778851, 5336554, 2668277, 8004832, 4002416, 2001208, 1000604, 500302, 250151, 750454, 375227, 1125682, 562841, 1688524, 844262, 422131, 1266394, 633197, 1899592, 949796, 474898, 237449, 712348, 356174, 178087, 534262, 267131, 801394, 400697, 1202092, 601046, 300523, 901570, 450785, 1352356, 676178, 338089, 1014268, 507134, 253567, 760702, 380351, 1141054, 570527, 1711582, 855791, 2567374, 1283687, 3851062, 1925531, 5776594, 2888297, 8664892, 4332446, 2166223, 6498670, 3249335, 9748006, 4874003, 14622010, 7311005, 21933016, 10966508, 5483254, 2741627, 8224882, 4112441, 12337324, 6168662, 3084331, 9252994, 4626497, 13879492, 6939746, 3469873, 10409620, 5204810, 2602405, 7807216, 3903608, 1951804, 975902, 487951, 1463854, 731927, 2195782, 1097891, 3293674, 1646837, 4940512, 2470256, 1235128, 617564, 308782, 154391, 463174, 231587, 694762, 347381, 1042144, 521072, 260536, 130268, 65134, 32567, 97702, 48851, 146554, 73277, 219832, 109916, 54958, 27479, 82438, 41219, 123658, 61829, 185488, 92744, 46372, 23186, 11593, 34780, 17390, 8695, 26086, 13043, 39130, 19565, 58696, 29348, 14674, 7337, 22012, 11006, 5503, 16510, 8255, 24766, 12383, 37150, 18575, 55726, 27863, 83590, 41795, 125386, 62693, 188080, 94040, 47020, 23510, 11755, 35266, 17633, 52900, 26450, 13225, 39676, 19838, 9919, 29758, 14879, 44638, 22319, 66958, 33479, 100438, 50219, 150658, 75329, 225988, 112994, 56497, 169492, 84746, 42373, 127120, 63560, 31780, 15890, 7945, 23836, 11918, 5959, 17878, 8939, 26818, 13409, 40228, 20114, 10057, 30172, 15086, 7543, 22630, 11315, 33946, 16973, 50920, 25460, 12730, 6365, 19096, 9548, 4774, 2387, 7162, 3581, 10744, 5372, 2686, 1343, 4030, 2015, 6046, 3023, 9070, 4535, 13606, 6803, 20410, 10205, 30616, 15308, 7654, 3827, 11482, 5741, 17224, 8612, 4306, 2153, 6460, 3230, 1615, 4846, 2423, 7270, 3635, 10906, 5453, 16360, 8180, 4090, 2045, 6136, 3068, 1534, 767, 2302, 1151, 3454, 1727, 5182, 2591, 7774, 3887, 11662, 5831, 17494, 8747, 26242, 13121, 39364, 19682, 9841, 29524, 14762, 7381, 22144, 11072, 5536, 2768, 1384, 692, 346, 173, 520, 260, 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]

Number of steps is :  351

Q. Is the hailstone sequence solved?

A. Hailstone sequence has been checked for two to the sixtieth power numbers (2^60). All the sequences generated up to that number has turned out to be a finite sequence ending with the same pattern – 4, 2, 1.

That was all about hailstone sequence in python. If you have any questions or thoughts to share, let us know in the comments.

Till then, Happy Learning!