Problem Solving: Verifying Conjecture

Learn to write a program that takes a stream of numbers (numbers ending with a delimiter) and finds out the number having a maximum length Collatz sequence.

There are so many mathematical claims which sometimes can be intuitively simulated and validated through computational programs. We will be working on one such example in this lesson.

The Collatz conjecture (3n+1-conjecture)

The Collatz conjecture is a famous mathematical conjecture which says;

  • Take any positive non-zero integer n.

  • If n is an even number, shrink it by dividing it by two, i.e., n = n/2.

  • If it is an odd number, multiply it by three and add 1 to it, i.e., n = 3n+1.

Claim: This change in the value of n is generating a sequence and it will always lead to 1. For example, for n = 3, the generated sequence will be 3, 10, 5, 16, 8, 4, 2, 1. We call 3 to generate the 3n+1 sequence of length 8.

The Collatz conjecture is one of the most amazing conjectures which is yet to be proven mathematically.

Validating the Collat-z conjecture on a range

Let’s create a program that takes a stream of numbers (where the stream will end with -1) as input and calculates which number has the highest Collatz sequence length.

Sample input

5 7 6 -1

Sample output


Explanation: Here is the following sequence generated by each number:

  • Collatz sequence for 5: 5, 16, 8, 4, 2, 1
  • Collatz sequence for 7: 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
  • Collatz sequence for 6: 6, 3, 10, 5, 16, 8, 4, 2, 1

Hence the maximum sequence is generated by 7.

Implementation details

Let’s write a piece of code that, on a specific integer n, generates (changes values in n) a sequence following the rules of even (shrinking step n=n/2) and odd (expanding step n=3*n+1). The sequence stops when n has the value 1.

Create a free account to view this lesson.

By signing up, you agree to Educative's Terms of Service and Privacy Policy