Problem Solving: Verifying Conjecture

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

7

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.