[Solved] Hailstone Sequence in Python (With or Without Recursion)

In this tutorial, you will learn what is hailstone sequence, how to write a Python program to find the hailstone sequence with and without recursion.

Let’s start with the basic algorithm to find the hailstone sequence.

Hailstone Sequence Algorithm

• Take a number (says ‘n’) as an input.
• Print the value of ‘n’.
• while n != 1
  a) Print the value of ‘n’.
  b) If ‘n’ is odd, calculate the next number as n*3+1.
  c) If ‘n’ is even, calculate the next number as n/2.

Example:

Input : 10
Output (Hailstone Sequence): 10 -> 5 -> 16 -> 8 -> 4 -> 2 ->1

Input : 17
Output (Hailstone Sequence): 17 -> 52 -> 26 -> 13 -> 40 -> 20 ->10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

If you plot the graph for hailstone sequences for 10, 11, 12, 13, 14 and 15, it looks like below.

(I will share the code for piloting the graph at end of this tutorial.)

Hailstone Sequence Python Program using while Loop

We are using Python while loop to solve this problem.

Python Program:

def hailstone_seq(start):
  list_out = []
  while start > 1:
    list_out.append(int(start))
    if start%2 == 1:
      start = int(start*3+1)
    else:
      start = int(start/2)
  list_out.append(1)
  return list_out
 
if __name__ == "__main__":
  n = input("Enter the number:")
  if n.isnumeric():
    n = int(n)
    list_out = hailstone_seq(n)
    print("Hailstone Sequence: ", list_out)
  else:
    print("Invalid input.")

def hailstone_seq(start):

  list_out = []

  while start > 1:

    list_out.append(int(start))

    if start%2 == 1:

      start = int(start*3+1)

    else:

      start = int(start/2)

  list_out.append(1)

  return list_out

if __name__ == "__main__":

  n = input("Enter the number:")

  if n.isnumeric():

    n = int(n)

    list_out = hailstone_seq(n)

    print("Hailstone Sequence: ", list_out)

  else:

    print("Invalid input.")

Output:

Enter the number: 10
Hailstone Sequence: [10, 5, 16, 8, 4, 2, 1]

When you take the user input, check if the user input value is numeric or not. You can check it with the isnumeric() string method.

Other parts of the code are self-explanatory.

Hailstone Sequence Python Program with Recursion

Hope you are familiar with the recursion programming concepts.

Python Program:

def hailstone_seq_rec(start, list_out=[]):

  #base condition
  if start == 1:
    list_out.append(1)
    return list_out

  list_out.append(int(start))

  if start%2 == 1:
    return hailstone_seq_rec(start*3+1, list_out)
  else:
    return hailstone_seq_rec(start/2, list_out)

if __name__ == "__main__":
  n = input("Enter the number:")
  if n.isnumeric():
    n = int(n)
    list_out = hailstone_seq_rec(n)
    print("Hailstone Sequence: ", list_out)
  else:
    print("Invalid input.")

def hailstone_seq_rec(start, list_out=[]):

  #base condition

  if start == 1:

    list_out.append(1)

    return list_out

  list_out.append(int(start))

  if start%2 == 1:

    return hailstone_seq_rec(start*3+1, list_out)

  else:

    return hailstone_seq_rec(start/2, list_out)

if __name__ == "__main__":

  n = input("Enter the number:")

  if n.isnumeric():

    n = int(n)

    list_out = hailstone_seq_rec(n)

    print("Hailstone Sequence: ", list_out)

  else:

    print("Invalid input.")

Output:

Enter the number: 15
Hailstone Sequence: [15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]

Find the Length of the Hailstone Sequence

You can find the length of the hailstone sequence simply by finding the length of the list having all the hailstone sequence numbers.

If our aim is to find only the length of the sequence, it is not efficient to store all hailstone sequence values. Instead of that, we calculate the length.

The same code we used to find the hailstone sequence can be used to calculate the length with a few lines of changes in code.

Python Program: Without using recursion (while loop)

def hailstone_seq_len(start):
  len_seq = 0

  while start > 1:
    len_seq = len_seq+1
    if start%2 == 1:
      start = int(start*3+1)
    else:
      start = int(start/2)

  return len_seq+1
 
if __name__ == "__main__":
  n = input("Enter the number:")
  if n.isnumeric():
    n = int(n)
    len_seq = hailstone_seq_len(n)
    print("Length of Hailstone Sequence = ", len_seq)
  else:
    print("Invalid input.")

def hailstone_seq_len(start):

  len_seq = 0

  while start > 1:

    len_seq = len_seq+1

    if start%2 == 1:

      start = int(start*3+1)

    else:

      start = int(start/2)

  return len_seq+1

if __name__ == "__main__":

  n = input("Enter the number:")

  if n.isnumeric():

    n = int(n)

    len_seq = hailstone_seq_len(n)

    print("Length of Hailstone Sequence = ", len_seq)

  else:

    print("Invalid input.")

Output:

Enter the number:10
Length of Hailstone Sequence = 7

Python Program: Using recursion

def hailstone_seq_rec_len(start, len_seq=0):

  #base condition
  if start == 1:
    return len_seq+1

  len_seq =len_seq+1

  if start%2 == 1:
    return hailstone_seq_rec_len(start*3+1, len_seq)
  else:
    return hailstone_seq_rec_len(start/2, len_seq)

if __name__ == "__main__":
  n = input("Enter the number:")
  if n.isnumeric():
    n = int(n)
    len_seq = hailstone_seq_rec_len(n)
    print("Length of the hailstone sequence = ", len_seq)
  else:
    print("Invalid input.")

def hailstone_seq_rec_len(start, len_seq=0):

  #base condition

  if start == 1:

    return len_seq+1

  len_seq =len_seq+1

  if start%2 == 1:

    return hailstone_seq_rec_len(start*3+1, len_seq)

  else:

    return hailstone_seq_rec_len(start/2, len_seq)

if __name__ == "__main__":

  n = input("Enter the number:")

  if n.isnumeric():

    n = int(n)

    len_seq = hailstone_seq_rec_len(n)

    print("Length of the hailstone sequence = ", len_seq)

  else:

    print("Invalid input.")

Output:

Enter the number:15
Length of the hailstone sequence = 18

Find the Maximum Length of Hailstone Sequence for the Range of Given Numbers

Problem statement: Write a program hailstones.py that prints all hailstone sequences with starting numbers from 1 to n and prints the number that has the longest hailstone sequence.

You have to find the seed having the maximum length of the hailstone sequence for the hailstone sequences for all the numbers in the range of given numbers.

Algorithm:

• Take two numbers as input (says a, b).
• Find a hailstone sequence length of all the values ranging from a to b.
• Return maximum length out of all the lengths of hailstone sequences.

Python Program:

def hailstone_seq_len(start):
  len_seq = 0

  while start > 1:
    len_seq = len_seq+1
    if start%2 == 1:
      start = int(start*3+1)
    else:
      start = int(start/2)

  return len_seq+1
 
if __name__ == "__main__":
  a = input("Enter the number a:")
  b = input("Enter the number b:")
  max_len = 0
  max_seed = 0
  if a.isnumeric() and b.isnumeric():
    a = int(a)
    b = int(b)
    for i in range(a, b+1):
      len_temp = hailstone_seq_len(i)
      if len_temp > max_len:
        max_len = len_temp
        max_seed = i
    print("Max length of the Hailstone Sequence is %d for seed %d." %(max_len, max_seed))

  else:
    print("Invalid input.")

def hailstone_seq_len(start):

  len_seq = 0

  while start > 1:

    len_seq = len_seq+1

    if start%2 == 1:

      start = int(start*3+1)

    else:

      start = int(start/2)

  return len_seq+1

if __name__ == "__main__":

  a = input("Enter the number a:")

  b = input("Enter the number b:")

  max_len = 0

  max_seed = 0

  if a.isnumeric() and b.isnumeric():

    a = int(a)

    b = int(b)

    for i in range(a, b+1):

      len_temp = hailstone_seq_len(i)

      if len_temp > max_len:

        max_len = len_temp

        max_seed = i

    print("Max length of the Hailstone Sequence is %d for seed %d." %(max_len, max_seed))

  else:

    print("Invalid input.")

Output:

Enter the number a: 10
Enter the number b: 15
Max length of the Hailstone Sequence is 18 for seed 14.

When I attended an interview with NVIDIA, they asked me to optimize it further.

We can use a dynamic programming approach to optimize this problem.

Let’s look at the hailstone sequence for 10 and 11.

[10, 5, 16, 8, 4, 2, 1] 
[11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

Here the total iteration to calculate hailstone sequence length will be 22.

7 (length of hailstone sequence for 10) + 15 (length of hailstone sequence for 11)= 22

How can we optimize it?

Observe the sequence for 10 and 11. The hailstone sequence for 10 is a subset of the hailstone sequence for 11.

• Calculate the length of the hailstone sequence for 10. (The number of iterations required is 7).
• Store the length in the hailstone sequence for 10 in the dictionary (says ‘hs_len_dict’).
• Calculate the length of the hailstone sequence for 11. This can be calculated by finding the light of the hailstone sequence to 10 (The number of Iteration requires is 8) plus the length of the hailstone sequence for 10 (from the dictionary).
• So the total iterations required for calculating the length of the hailstone sequence for 10 and 11 is 15 (7+8).

With this optimization, we have saved the number of iterations from 22 to 15.

Python Program with Optimization:

hs_len_dict = {}
 
itr = 0
 
def hailstone_seq_len(start):
  global itr
  len_seq = 0
  
  while start > 1:
    itr = itr+1

    if start in hs_len_dict:
      return hs_len_dict[start]+len_seq
  
    len_seq = len_seq+1
    if start%2 == 1:
      start = int(start*3+1)
    else:
      start = int(start/2)
  
  return len_seq+1
  
if __name__ == "__main__":
  a = input("Enter the number a:")
  b = input("Enter the number b:")
  max_len = 0
  max_seed = 0
  if a.isnumeric() and b.isnumeric():
    a = int(a)
    b = int(b)
    for i in range(a, b+1):
      len_temp = hailstone_seq_len(i)
      hs_len_dict[i] = len_temp
        
      if len_temp > max_len:
        max_len = len_temp
        max_seed = i
    print("Max lenght of the Hailstone Sequence is %d for seed %d" %(max_len, max_seed))
  
  else:
    print("Invalid input.")

  print("Number of iteration: ", itr)

hs_len_dict = {}

itr = 0

def hailstone_seq_len(start):

  global itr

  len_seq = 0

  while start > 1:

    itr = itr+1

    if start in hs_len_dict:

      return hs_len_dict[start]+len_seq

    len_seq = len_seq+1

    if start%2 == 1:

      start = int(start*3+1)

    else:

      start = int(start/2)

  return len_seq+1

if __name__ == "__main__":

  a = input("Enter the number a:")

  b = input("Enter the number b:")

  max_len = 0

  max_seed = 0

  if a.isnumeric() and b.isnumeric():

    a = int(a)

    b = int(b)

    for i in range(a, b+1):

      len_temp = hailstone_seq_len(i)

      hs_len_dict[i] = len_temp

      if len_temp > max_len:

        max_len = len_temp

        max_seed = i

    print("Max lenght of the Hailstone Sequence is %d for seed %d" %(max_len, max_seed))

  else:

    print("Invalid input.")

  print("Number of iteration: ", itr)

Output:

The final output of the optimized code will be the same, but the process is optimized. The number of iterations required has dropped from 72 to 39.

Enter the number a:
Enter the number b:
Max length of the Hailstone Sequence is 18 for seed 14
Number of iteration: 39

You can also further optimize this program by calculating the square root of the number. (Hint: If the given number is a square of two, the length of the Hailstone Sequence is the square root of that number.)

Plot Hailstone Sequence in Graph

We are using matplotlob library for plotting the graph. It is one of the most used Data Science Python libraries used for graph plots.

If you don’t have matplotlib library installed, you can install it using pip tool. Here is the command.

pip install matplotlib

Let’s plot the graph for hailstone sequences for 10 to 15.

Python Program:

from matplotlib import pyplot as plt
 
def hailstone_seq(start):
  list_out = []
  while start > 1:
    list_out.append(int(start))
    if start%2 == 1:
      start = int(start*3+1)
    else:
      start = int(start/2)
  list_out.append(1)
  return list_out
 
if __name__ == "__main__":
  a = 10
  b = 15
  for i in range(a, b+1):
    list_out = hailstone_seq(i)
    plt.plot(list_out, label='HS for %d'%i)
    plt.legend()
  plt.show()

from matplotlib import pyplot as plt

def hailstone_seq(start):

  list_out = []

  while start > 1:

    list_out.append(int(start))

    if start%2 == 1:

      start = int(start*3+1)

    else:

      start = int(start/2)

  list_out.append(1)

  return list_out

if __name__ == "__main__":

  a = 10

  b = 15

  for i in range(a, b+1):

    list_out = hailstone_seq(i)

    plt.plot(list_out, label='HS for %d'%i)

    plt.legend()

  plt.show()

Output:

Hailstone Sequence in Python is a very interesting and common problem of sequencing.

This problem has been asked in many interviews for different companies.

If you have any questions regarding the hailstone sequence problem, let’s discuss it in the comment.

Aniruddha Chaudhari

I am a Python enthusiast who loves Linux and Vim. I hold a Master of Computer Science degree from NIT Trichy and have 10 years of experience in the IT industry, focusing on the Software Development Lifecycle from Requirements Gathering, Design, Development to Deployment. I have worked at IBM, Ericsson, and NetApp, and I share my knowledge on CSEstack.org.