Discussion Room : IDC101

Collatz conjecture

Collatz conjecture

by Dr. Amit Kulshrestha -
Number of replies: 8

Collatz conjecture is an unsolved problem in mathematics. It states the following.

"You start with an integer of your choice. You divide it by 2 if this integer is even, else you multiply it by 3 and add 1. Do the same with the outcome of this. Keep doing this.  Eventually you get 1."

For example, if our chosen integer is 13, then we get the following sequence as a result of iteration suggested above.

13 --> 40 --> 20 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1

Let us call it Collatz sequence for 13. While a mathematical proof for Collatz conjecture has not yet been obtained, computers have checked its correctness till 87 x 2**60. What is equally interesting is the number of steps it takes for an integer to reach 1. We shall call it the length of Collatz sequence. For example, this length is 9, if we start with 13.

Now, with that as background, I pose the following challenge.

Use your Python skills to find a Collatz sequence of really large length.

In reply to Dr. Amit Kulshrestha

Collatz conjecture

by Sourav S . -

The Collatz conjecture has always fascinated me as it is one of the easiest things to understand (basic algebra) but not prove. Some mathematicians even say math is not ready for such complex problems. It is not among the millenium prize problems though. But still Paul Erdos promised to pay you if you prove it (It's not about the money and fame though (taking Perelmann as an inspiration)).


This video by numberphile is really good,

Collatz conjecture: https://www.youtube.com/watch?v=5mFpVDpKX70


And check out an artwork made on it (again numberphile),

Collatz conjecture art: https://www.youtube.com/watch?v=LqKpkdRRLZw&vl=en


And for people interested in art... I also suggest this one about the Mandelbrot set (numberphile),

Math-art-Mandelbrot set: https://www.youtube.com/watch?v=NGMRB4O922I



In reply to Dr. Amit Kulshrestha

Collatz conjecture

by Sourav S . -

I wrote a primitive program and found that the number 84,00,511 takes the most number of steps (i.e 685 steps) under 10^7 (one crore). The processing time for this output was around 15-20 mins with an average hardware...


I have ideas to make the program more efficient and with the amendments, I believe it can hit more than 10^10 in a very decent short amount of processing time...

In reply to Sourav S .

Re: Collatz conjecture

by Dr. Amit Kulshrestha -

That sounds good Sourav.

Please share the Python code of your program.

I encourage everyone to think about it.


In reply to Dr. Amit Kulshrestha

Re: Collatz conjecture

by Sourav S . -

I've attached two files. 


One returns the number which takes the maximum number of steps and the number of steps it takes.


The other one gives the entire path of the number to reach 1.


I've given a maximum no. of iterations limit which is like a safety cut-off value as initially the number of steps were unknown to me and I didn't want my PC to get crazy. Give it a value of 1000 under the limit 10^7.


Careful with using these programs as they require heavy computational power which may cause your PC to hang. Experiment with these programs with a small range at first.


Suggest ideas for improvement.

Thanks.


In reply to Sourav S .

Re: Collatz conjecture

by Dr. Amit Kulshrestha -

I appreciate Sourav for writing program for Collatz conjecture, and sharing it in this forum.

Here are some good practices:

  1. When you share program, ensure that its input and output are clearly mentioned.
  2. There are comments the at every step, so that people follow the logic that makes the program work.

Let me give you an example.

# This program finds the sum of digits of a given integer. 
# For example, sum of digits of 2018 is : 2 + 0 + 1 + 8 = 11.

def sumofdigits(n):     # We are writing a function that would return the sum of digits of n.
     nstr = str(n)      # Convert n into a string.
     sum = 0            # Let us start storing the sum of digits in a variable called sum.
     for i in range(len(nstr)):        # Run over all digits,
         sum = sum + int(nstr[i])      # And keep adding their contribution to sum.
     return sum                        # When done, return sum

# Now we use the function defined above to obtain an input from user and then print sum of its digits.

n = input("Enter the number whose sum of digits you wish to print: ") # Ask user for input. 
print "Sum of digits of", n, "is :", sumofdigits(n) # Use function sumofdigits to print sum of digits.

That way your code is much readable and could be understood and enjoyed by others.
In reply to Sourav S .

Re: Collatz conjecture

by Abineet Parichha . -

I believe you must have thought of improving its efficiency, nevertheless these are my suggestions. If you have already thought of them, just ignore.

1. The lists q and l will take up a large amount of processing time and memory as they store each and every number and the no. of steps as per collatz sequence. On top of it, there are the functions max() and index() that you have applied upon the big list. Instead you might prefer to use two variables, one to store the number, with greatest no. of steps as per collatz sequence and another to store the no, of steps.


2. You can use file handling to store the data obtained in one run of the program. Then reload the saved data next time you run the program and thus, continue from where you left off. This will save your processing time quite a bit as you wont have to restart from the beginning. Also, you can achieve this if you enter the initial values yourself into a,q,l..... however, that will indeed be a tedious task!

In reply to Dr. Amit Kulshrestha

Re: Collatz conjecture

by Kapil Paranjape -

A perhaps weaker question is whether this map eventually loops.

We can explain this better as follows. Let x_0=n and define x_{k+1} = x_{k}/2 if x_k is even and x_{k+1}=3x_k+1 if x_k is odd. We can now ask if this map "loops". In other words, is there always a pair of natural numbers p and q>0 so that x_{p+q}=x_p? It is not obvious that this question is the same as the Collatz sequence question.

In fact, we can define more general maps as follows. Fix a "base" b. Starting with x_0=n we put x_{k+1}=x_k/b if x is divisible by b; other wise, let r be the remainder of x_k on division by b and put x_{k+1}=(b+1)*x_k+(b-r). Note that in the second case x_{k+1} is divisible by b. So every two steps x_{k+2} is at most about (b+1)/b times x_k. We can ask the same question about this map.

Write a program to find "loops".